A

除500和对500取模即可，但是这个余数是1-500的，并不是0-499，所以直接取模会在边界情况出错，需要特判一下

void solve(){
	cin>>n;
	int x=n/500;
	char c='A'+x;
	int y=n%500;
	
	if(y){
		cout<<c;
		string s=to_string(y);
		while(s.size()<3)s='0'+s;
		cout<<s;
	}
	else{
		c--;
		cout<<c<<"500";
	}
}

B

模拟，吧目标串的字符放到一个集合里，然后看猜的串里的字符是不是在这个集合里即可

void solve(){
	string s,t;
	cin>>s>>t;
	string ans;
	set<char>st;
	for(char c:s)st.insert(c);
	
	n=s.size();
	int cnt=0;
	rep(i,0,n-1){
		if(t[i]==s[i]){
			ans+='g';
			cnt++;
		}
		else if(st.count(t[i])){
			ans+='y';
		}
		else{
			ans+='r';
		}
	}
	cout<<ans<<'\n';
	if(cnt==n)cout<<"congratulations";
	else cout<<"defeat";
}

C

容斥。满足两个条件之一的数组成的数列的个数，实际上就是5结尾的个数+加起来是3的个数-同时是5结尾且加起来是3的个数。当然这题周期比较小，也可以打表，把每个周期的列出来，然后判断再第几个周期，是周期里的第几个。

void solve(){
	cin>>k;
	vi a={3,5,9,15,21,25,27};
	int ans=(k-1)/7*30+a[(k-1)%7];
	cout<<ans<<'\n';
}

D

经典博弈dp

短期主义者的行为模式是固定的，没有选择的余地，那么我们知道双方都最优策略下的结果，实际上只要考虑长期主义者的最优情况即可。

然后注意到只能在两侧取，且，显然可以用一个的区间dp来做，长期主义者每次可以在两头选一个取，我们不知道什么策略是最优的，那就dp然后对这两种情况取max即可。然后这种回合制的dp我一般喜欢写记搜

void solve(){
	cin>>n;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	vvi dp0(n+1,vi(n+1));
	vvi dp1(n+1,vi(n+1));
	auto &&dfs=[&](auto &&dfs,int l,int r,bool round)->int{
		if(l>r)return 0;
		if(l==r){
			if(round==1){
				return a[l];
			}
			else{
				return 0;
			}
		}
		if(round){
			if(dp1[l][r])return dp1[l][r];
			int res=max(dfs(dfs,l+1,r,0)+a[l],dfs(dfs,l,r-1,0)+a[r]);
			return dp1[l][r]=res;
		}
		else{
			if(dp0[l][r])return dp0[l][r];
			int res;
			if(a[l]>a[r]){
				res=dfs(dfs,l+1,r,1);
			}
			else if(a[l]<a[r]){
				res=dfs(dfs,l,r-1,1);
			}
			else{
				res=dfs(dfs,l+1,r,1);
			}
			return dp0[l][r]=res;
		}
	};
	int res=dfs(dfs,1,n,0);
	int sum=0;
	rep(i,1,n)sum+=a[i];
	cout<<sum-res<<' '<<res;
}

E

经典区间dp

可以交换下标模k同余的元素，或者值模k同余的元素，问能不能变成升序的。这类交换问题的思路一般就是把能交换的元素放进一个集合，然后把每个集合都排序然后回填，看最后数组是不是有序的。

但这题的问题在于我们有两种并查集，那一个朴素的想法就是把在这两种规则下，所有能合并的元素都合并。但这实际上是不对的，因为如果你先按值交换，下标可能就变了，原本你可以按下标交换的元素现在可能不能交换了。具体可以看样例4，出题人还是很友好，给了这个样例，否则估计很难想到

所以正确做法是，先把按下标交换操作完了，然后接下来再开始按值交换

void solve(){
	cin>>n>>k;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	vi f(n+1);
	rep(i,1,n)f[i]=i;
	auto &&find=[&](auto &&find,int x)->int{
		if(f[x]==x)return x;
		return f[x]=find(find,f[x]);
	};
	rep(i,1,n){
		if(i+k>n)break;
		int fx=find(find,i),fy=find(find,i+k);
		f[fx]=fy;
	}
	map<int,vi>mp;
	rep(i,1,n){
		mp[find(find,i)].push_back(i);
	}
	for(auto &[k,v]:mp){
		vi b;
		for(int x:v){
			b.push_back(a[x]);
		}
		sort(b.begin(),b.end());
		int len=b.size();
		rep(i,0,len-1){
			a[v[i]]=b[i];
		}
	}
	mp.clear();
	rep(i,1,n)f[i]=i;
	map<int,int>pos;
	rep(i,1,n){
		pos[a[i]]=i;
	}
	rep(i,1,n){
		if(pos.count(a[i]+k)){
			int fx=find(find,i),fy=find(find,pos[a[i]+k]);
			f[fx]=fy;
		}
	}
	rep(i,1,n){
		mp[find(find,i)].push_back(i);
	}
	for(auto &[k,v]:mp){
		vi b;
		for(int x:v){
			b.push_back(a[x]);
		}
		sort(b.begin(),b.end());
		int len=b.size();
		rep(i,0,len-1){
			a[v[i]]=b[i];
		}
	}
	//rep(i,1,n)cout<<a[i]<<' ';
	rep(i,1,n-1){
		if(a[i]>a[i+1]){
			cout<<"No";
			return;
		}
	}
	cout<<"Yes";
}

F

贪心+前缀和枚举子数组

一段子数组的积模P不能是x，P是质数，这需要我们枚举所有子数组，在数据不支持的情况下，枚举子数组最好的方式就是前缀和+。

然后我们可以修改一些元素为任意值，需要让任意子数组的积都不是x，且需要最小化操作次数，问最后的数组。

首先如果x是0，我们至少需要把所有x都变成非0，然后变完之后可以发现任意子数组积都不会是0，因为剩下非0元素乘起来模P为0的话，需要他们乘起来是P，但是P是质数，几个非零数乘起来不可能得到P

如果x不是0，首先如果出现0，那么左端点在这个位置左侧，右端点在这个位置右侧的子数组乘起来一定是0，不可能等于x了，那么右端点在右侧的子数组，就不用考虑左端点在左侧的情况了，我们可以把map清空，相当于从0后面一位重新开始。然后如果遇到存在某个子数组乘起来是x，贪心的思路是立即把当前位置置0，至于这样为啥是操作次数最少的，不太好证，但它确实是对的

void solve(){
	int p,x;
	cin>>n>>p>>x;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	if(x==0){
		rep(i,1,n){
			if(a[i]==0){
				a[i]=1;
			}
		}
	}
	else{
		x=inv(x,p);
		map<int,int>mp;
		mp[1]=1;
		int pre=1;
		rep(i,1,n){
			pre=pre*a[i]%p;
			if(a[i]==0){
				mp.clear();
				mp[1]=1;
				pre=1;
			}
			else if(mp.count(pre*x%p)){
				a[i]=0;
				mp.clear();
				pre=1;
				mp[1]=1;
			}
			mp[pre]++;
		}
	}
	rep(i,1,n)cout<<a[i]<<' ';
}