6.14训练日记

床睡得还不是很习惯,起晚了点. 12点开始训练(未吃饭),先打开cf逛一逛.

一 :C. Manipulating History(思维)

链接 题意:一开始你有一个长度为1的字符串.第i次操作中,可以把 t 2 i − 1 t_{2i-1} t2i−1​替换成 t 2 i t_{2i} t2i​.然而现在给你的是一堆 t i t_i ti​,和最终得到的字符串 S S S.问你最开始的字符串是哪个?保证这个答案是唯一的. 思路:非常重要的观察,一开始只有一个字母,我们也只需要找到这个字母就可以.让我们思考一下,我们需要把长度为1最开始的字符串逐个替换得到这个最终字符串S. s->S1->S2->…S 当S的长度为1时,又由于答案是唯一的,肯定是逐个字符替换,每个非答案的字母出现了偶数次,只有一个字母出现了奇数次.那个就是最终的答案(除了最后一个) 比如说长度为1,n=4 a b b c,c 那么答案就一定是a. a->b,b->c这样变化,然后最后的c会重复出现在n+1个 当S长度不是1的时候,情况是类似的.当某个字母中间需要替换(或者最后)时,它一定会导致偶数次的出现情况.又因为答案是唯一的,所以答案是出现次数为奇数次的字母. 代码:

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		map cnt;
		for(int i=1;i>s;
			for(auto x : s) cnt[x]++;
		}
		for(auto [x,y]:cnt){
			if(y%2==1){
				coutn>>k;
		vector a(n+1,0);
		ll sum=0;
		for(int i=1;i>a[i],sum+=a[i];
		if(n==k){
			cout>k;
		ll sum = 0;
		vector a(n+1,0);
		for(int i=1;i>a[i];sum+=a[i];
		}
		if(k>=n){
			cout