cf796部分题解
C. Manipulating History
题意：给出一些字符串，有原始串（只含一个字符的串）、被替换的串、替换串、
最终串（最后一行），求原始串。
2
a
ab
b
cd
acd
Initially s is "a".
In the first operation, Keine chooses "a", and replaces it with "ab". s becomes "ab".
In the second operation, Keine chooses "b", and replaces it with "cd". s becomes "acd".
So the final string is "acd", and t=["a", "ab", "b", "cd"] before being shuffled.
思路：统计所有字母出现的次数，个数为奇数的就是最终结果。
因为每个串，他被替换的时候会给出它，然后它在替换前也是有的，
所以每次替换操作得到的结果都会是偶数。
//不要转成0-25，不然会超时
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 210;
const int M = 1e5 + 10;
int t, n, k, cnt;
int a[N];
string st;
vector<int> vet;
map<string, int> mp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t --){
cin >> n;
memset(a, 0, sizeof a);
for(int i = 1; i <= 2 * n + 1; i ++){
string st;
cin >> st;
for(int j = 0; j < st.size(); j++){
int x = (int)(st[j]);
a[x] ++;
}
}
for(int i = 0; i < 200; i ++){
if(a[i] % 2 == 1){
char ch = (char)(i);
cout << ch << endl;
break;
}
}
}
return 0;
}
D. The Enchanted Forest
题意：给n个数，每个位置代表初始时，当前位置有多少个蘑菇，每单位时间每个位置都会长出来1个蘑菇，
问，在给定时间k内，最多能获得多少蘑菇？
如果k >= n， 那么就先待在初始位置，等到刚好能全摘完所有蘑菇的时间，再去进行移动。
如果k < n, 那么就找出来最大连续子串。#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int t, n, k;
int sum[N], a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t --){
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] = a[i - 1] + a[i];
}
int ans = 0;
if(k >= n){
ans = a[n];
ans += (k - n) * n;
for(int i = 0; i <n; i++) ans += i;
}
else{
for(int i = k; i <= n; i++){
ans = max(a[i] - a[i - k], ans);
}
for(int i = 1; i < k; i++) ans += i;
}
cout << ans << endl;
}
return 0;
}
链接：https://www.dianjilingqu.com/616312.html
