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.
思路：統(tǒng)計所有字母出現(xiàn)的次數(shù)，個數(shù)為奇數(shù)的就是最終結(jié)果。
因為每個串，他被替換的時候會給出它，然后它在替換前也是有的，
所以每次替換操作得到的結(jié)果都會是偶數(shù)。
//不要轉(zhuǎn)成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個數(shù)，每個位置代表初始時，當前位置有多少個蘑菇，每單位時間每個位置都會長出來1個蘑菇，
問，在給定時間k內(nèi)，最多能獲得多少蘑菇？
如果k >= n， 那么就先待在初始位置，等到剛好能全摘完所有蘑菇的時間，再去進行移動。
如果k < n, 那么就找出來最大連續(xù)子串。#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
