2022-4-14携程笔试

2022-4-14携程笔试

Tans 2,975 2022-04-14

2022-4-14携程笔试

1. 打印‘U’字符（模拟）

模拟即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n ;
	cin >> n;
	for(int i = 1; i <= 4 * n; i++){
		string row = "";
		if(i <= 3 * n) row = string(n, '*') + string(n, '.');
		else row = string(i-3*n, '.') +string(n, '*') + string(4*n-i, '.');
		string rev = row;
		reverse(rev.begin(), rev.end());
		cout << row << rev << endl;
	}
	return 0;
}

2. 找出不同颜色相同值位置的不同情况

这里统计每个数值的两种颜色状况即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string colors;
	cin >> n;
	vector<int> nums(n, 0);
	for(int i = 0; i < n; i++) cin >> nums[i];
	cin >> colors;
	unordered_map<int, pair<int,int>> mp;
	for(int i = 0; i < n; i++){
		if(colors[i] == 'R') mp[nums[i]].first++;
		else mp[nums[i]].second++;
	}
	long long ans = 0;
	for(auto &it : mp) ans += it.second.first * it.second.second;
	cout << ans;
	
	return 0;
}

3.交换相邻字符使得无连续重复字符

判断1和0的个数分别是odd, ever，如果abs(odd-ever) > 1，那么一定不满足。但是题目中说的是前提满足。因此无需判断，那么对字符串长度分为两种情况：

  1. 长度是偶数

    • 10101010....类型
    • 0101010....类型

  2. 长度是奇数

    • 101010101...类型
    • 0101010...类型

交换位置的时候，只需构造出上述可能的字符串，这里从第一位1或0以此遍历，然后让原来字符串对应位置和构造字符串的相对应位置的距离就是贡献。举个例子：

111000-->101010，这里我们移动1

  • 第一位1,下标为0，对应构造串的下标为0, 无需移动，贡献为 0
  • 第二位1,下标为1，对应构造串的下标为2, 贡献为 2-1=1
  • 第三位1,下标为2，对应构造串的下标为4, 贡献为 4-2=2

所以需要移动3次即可，我们移动0也是同理，两者是等价的。

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	int len = s.size(), a = 0, b = 0;
	long long ans = 0;
	vector<int> zeros, ones;
	for(int i = 0; i < len; i++){
		if(s[i] == '0') zeros.push_back(i);
		else ones.push_back(i);
	}
	a = zeros.size(), b = ones.size();
	if(len % 2){
		if(b > a) for(int i = 0, j = 0; i < len and j < b; i+=2, j++) ans += abs(i - ones[j]);
		if(a > b) for(int i = 0, j = 0; i < len and j < a; i+=2, j++) ans += abs(i - zeros[j]);
	}else{
		int n1 = 0, n2 = 0;
		for(int i = 0, j = 0; i < len and j < a; i+=2, j++) n1 += abs(i - zeros[j]);
		for(int i = 0, j = 0; i < len and j < b; i+=2, j++) n2 += abs(i - ones[j]);
		ans = min(n1, n2);
	}
	cout << ans;	
	return 0;
}

4. 和为9的倍数的子序列个数

注意9的倍数一个重要性质：各个位的和必定是9的倍数

因此，我们使用类似dp的方法，dp[i][j]表示以下标i元素结尾的子序列，并且子序列各个位值之和 对9 取模结果为j的数量。这里使用map实现交替。

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin >> s;
	int mod = 1e9+7;
    //nmp：相当于dp[1][j]    omp:相当于dp[0][j]
	unordered_map<int,long long> nmp, omp;
	for(auto &ch : s){
		nmp = omp;
		for(auto it : omp){
			int carry = (it.first + ch - '0') % 9;
			nmp[carry] = (it.second + nmp[carry]) % mod;
		}
		nmp[(ch-'0')%9]++;
		omp = nmp;
     }
	cout << nmp[0] % mod;
	return 0;
}

此题就是用到了9的倍数性质，归根到底就是 寻找给定序列中 和为 9的倍数的 子序列 个数问题。就是求满足一定条件的子序列个数问题。可以google一下搜索相关题目。

喜欢的小伙伴还请点个赞哦~

笔试