A. 求余来咯

这几天的题让我怀疑是不是对运算有什么深仇大恨

枚举。

因为本题的数据都很小水到家了，所以我们可以枚举一个可能的答案$i$，将$a$数组里的所有数字都进行求余，再用$sum$求和，最会取最大值$ans$即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[3010];
signed main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	int n,l,r;
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0,mn=1e9;
	for(int i=l;i<=r;i++){
		int sum=0;
		for(int j=1;j<=n;j++) sum+=a[j]%i;
		if(sum<mn) mn=sum,ans=i;
	}
	cout<<ans;
	return 0;
}

B. 乘法考验

数学（最大公因数）。

我们首先可以将题意进行转化，那么$Q$个$0$就是答案$ans×a$的因子。

那么对于$Q$来说，$k$个$0$有一部分由$a÷$去，有有一部分由$ans÷$去。

那么$a$的贡献又是什么呢？当然就是$gcd(Q,a)$啦！

由此，我们可得答案就是$Q/gcd(Q,a)$！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
signed main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int a,k;
		cin>>a>>k;
		int sum=1;
		while(k--) sum*=10;
		cout<<sum/gcd(sum,a)<<endl;
	}
	return 0;
}

C. 回文树

因为写完前面两题之后，就专攻第四题了，没有时间腾出来写第三题，所以就没有写这道题目；下一次一定要合理分配时间，每道题目都要有时间写！！！

模拟。

我们都知道，一个集合它至多只能有一个字母出现的次数是奇数。

所以我们可以枚举统计每个节点都作为根节点的子树每个字符出现的字母个数。

但是！怎么做是会超时的！所以，我们可以从每一组改变的字母下手。

我们很容易就可以发现，一个字母改变，都只会让以这个节点为根节点的其他的节点为根节点的答案改变。

所以我们可以用一个数组来记录每次一每个节点为根节点的答案。

如果这个节点改变了以这个节点为根节点的其他的节点为根节点的答案的话：

• 若减少了，答案减$1$。
• 若增加了，答案加$1$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char a[N];
int st[N],b[N][30],res,n,q;
void dfs(int i){
	b[i][a[i]-'a']++;
	if(i*2<=n){
		dfs(i*2);
		for(int j=0;j<26;j++) b[i][j]+=b[i*2][j];
	}
	if(i*2+1<=n){
		dfs(i*2+1);
		for(int j=0;j<26;j++) b[i][j]+=b[i*2+1][j];
	}
}
bool check(int i){
	int sum=0;
	for(int j=0;j<26;j++) sum+=(b[i][j]%2);
	return sum<=1;
}
void gb(int x, char d, char c){
	while(x){
		b[x][c-'a']++;
		b[x][d-'a']--;
		if(check(x)){
			if(!st[x]) res++;
			st[x]=1;
		}
		else{
			if(st[x]==1) res--;
			st[x]=0;
		}
		x/=2;
	}
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1);
	for(int i=1;i<=n;i++){
		if(check(i)){
			res++;
			st[i]=1;
		}
	}
	cout<<res<<endl;
	while(q--){
		int x;
		char c;
		cin>>x>>c;
		gb(x,a[x],c);
		a[x]=c;
		cout<<res<<endl;
	}
	return 0;
}