拼多多20220903笔试题解【部分】
1.字符串转换，每次可将字符串中的一种字母减一，求不超过k次的字典序最小的装换
2.左右横跳，求每个下标跳出去的步数
3.将#变为字母，求S和T最大覆盖的情况，如果有多个S，求字典序最小的答案
4.分班考试期望得分
1.要字典序最小，那么就从头往尾计算，记录每种字符可以转换到的最小字符，注意，一开始要先统计不超过k次所能计算到的最长部分，比如ekyv，发现ek都可以变到a，于是先考虑ek，次数先减去ek中的最大变换值，再对后面的字符串进行处理
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while(T--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
unordered_map<char, char>mp;
for(char c = 'a'; c <= 'z'; c++) mp[c] = c;
int index = 0;
int max_ = 0;
for(int i = 0; i < n; i++) {
if(s[i] - 'a' <= k) {
index++;
max_ = max(max_, s[i] - 'a');//记录前面能减的那一部分，比如ekyv中的ek部分，最大是k
}
else break;
}
k -= max_;
for(int i = 0; i < index; i++) {
for(char c = 'a'; c <= s[i]; c++) mp[c] = 'a';
}
for(int i = index; i < n && k > 0; i++) {
s[i] = mp[s[i]];
int x = s[i] - 'a';
x = min(x, k);
k -= x;
for(int j = 0; j < x; j++) {
char c = s[i] - j;
mp[c] = (char)(s[i] - x);
}
}
for(int i = 0; i < n; i++) {
s[i] = mp[s[i]];
}
cout << s << endl;
}
return 0;
} #include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
vector<char>s(n);
vector<long long>a(n);
for(int i = 0; i < n; i++) {
cin >> s[i] >> a[i];
}
vector<long long>ans(n);
for(int i = 0; i < n; i++) {
if(ans[i] != 0) continue;
vector<int>path;
unordered_map<int, bool>vis;//是否走过该点，判断是否成环
int now = i;
long long step = 0;
while(true) {
// cout << "now: " << now << endl;
step++;
path.push_back(now);
vis[now] = true;
if(s[now] == 'L') now -= a[now];
else now += a[now];
if(now < 0 || now >= n) break;
if(vis[now]) {
step = -1;
break;
}
if(ans[now] != 0) {
if(ans[now] == -1) step = -1;
else step += ans[now];//这个点有答案，直接加上
break;
}
}
for(int j = 0; j < path.size(); j++) {
// cout << path[j] << endl;
if(step == -1) ans[path[j]] = -1;
else ans[path[j]] = step - j;
}
}
for(int i = 0; i < n; i++) {
if(i < n - 1) cout << ans[i] << ' ';
else cout << ans[i] << endl;
}
}
return 0;
} #include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int n = s.size();
if(s.size() < t.size()) {
int index = 1;
while(true) {//调试用的，最后没错，说明后台数据里没有s小于t的情况
index = index + 23;
}
cout << s << endl;
return 0;
}
vector<int>count1(26);
vector<int>count2(26);
int count3 = 0;
for(int i = 0; i < s.size(); i++) {
if(s[i] != '#') count1[s[i] - 'a']++;
else count3++;
}
for(int i = 0; i < t.size(); i++) {
count2[t[i] - 'a']++;
}
int num = 0;//先看看s可以组成多少个完整的T，并减去这么多个T
for(int i = 0; i < 26; i++) {
if(count2[i]) num = min(count1[i] / count2[i], num);
}
for(int i = 0; i < 26; i++) {
count1[i] -= num * count2[i];
}
string ans;
while(count3 > 0) {
bool flag = true;
int temp_count3 = count3;
vector<int>need(26);
for(int i = 0; i < 26; i++) {
if(count1[i] >= count2[i]) {//该字符可以由s组成
count1[i] -= count2[i];
} else if(count3 >= count2[i] - count1[i]) {//s不够了，由#来凑
count3 -= count2[i] - count1[i];
need[i] = count2[i] - count1[i];
count1[i] = 0;//这里忘记减了，卡了好久。。
} else {
flag = false;
}
}
if(!flag) {
count3 = temp_count3;
break;
}
for(int i = 0; i < 26; i++) {
while(need[i]--) {
ans.push_back((char)(i + 'a'));
}
}
}
while(count3--) {
ans.push_back('z');
}
sort(ans.begin(), ans.end());
int index = ans.size() - 1;
for(int i = 0; i < n; i++) {
if(s[i] == '#') {
s[i] = ans[index--];
}
}
cout << s << endl;
return 0;
} 4.第三题忘记减了，卡了好久，第四题就处理了下数据，求思路
牛皮
