求余来咯（枚举）

思路

由于$n，a[i]$较小，所以我们考虑枚举所有可能的答案$k$。

对于每一个$k$来说，用所有数字都进行求余，得到求余的和，同时记录最小值。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=3e4+10; 
int a[tt],cnt[tt];

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];
		for(int j=l;j<=r;j++){
			cnt[j]+=a[i]%j;
		}
	}
	int min_n=0x3f3f3f3f;
	int ans=0;
	for(int i=l;i<=r;i++){
		if(cnt[i]<min_n){
			min_n=cnt[i];
			ans=i;
		}
	}
	cout <<ans;
	return 0;
}

乘法考验（数学）

思路

对题面进行转化，得到我们最终输出的答案$res$满足：$ans$是$res*a$的因子。

也就是说对于$ans$来说，一部分是由$res$贡献的，另一部分是由$a$贡献的，两个数字乘起来得到$ans$。

所以考虑$ans$和$a$的最大公因数，这个最大公因数就是$a$对$ans$的贡献。那么剩余的因数需要$ans$来贡献，所以用$ans$除以这个最大公因数就知道$res$的值了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int gcd(int a,int b){
	if(a%b==0){
		return b;
	}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 ans=1;
		for(int i=1;i<=k;i++){
			ans*=10;
		}
		cout <<ans/gcd(ans,a)<<endl;
	}
	return 0;
}

回文树（树）

思路没想到的原因

当时没有想到合适的去储存二叉树的方法。

思路

首先我们要知道，如何用数组去储存二叉树：

假设当前节点的下标为$i$，那么它的左节点的下标为$2*i$，右节点的下标为$2*i+1$。

这样，我们就可以用数组去模拟、存储二叉树。

还要注意怎样去判断这个字符串是否是回文的，就是最多只能有一种字符出现的次数为奇数。

我们可以统计每个节点作为根节点的树里所有字符出现的次数，最终再来判断是否满足题目的要求。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=2e5+10;
int n,q;
char tree[tt];
int cnt[tt][110],flag[tt];
int res=0;

void dfs(int i){
	cnt[i][tree[i]-'a']++;
	if(i*2<=n){
		dfs(i*2);
		for(int j=0;j<26;j++){
			cnt[i][j]+=cnt[i*2][j];
		}
	}
	if(i*2+1<=n){
		dfs(i*2+1);
		for(int j=0;j<26;j++){
			cnt[i][j]+=cnt[i*2+1][j];
		}
	}
}

bool check(int i){
	int ans=0;
	for(int j=0;j<26;j++){
		ans+=cnt[i][j]%2;
	}
	return ans<=1;
}

void up(int x,int last,int z){
	while(x>0){
		cnt[x][z-'a']++;
		cnt[x][last-'a']++;
		if(check(x)){
			if(!flag[x]){
				res++;
			}
			flag[x]=1;
		}else{
			if(flag[x]){
				res--;
			}
			flag[x]=0;
		}
		x/=2;
	}
}

void solve(){
	res=0;
	for(int i=1;i<=n;i++){
		if(check(i)){
			res++;
			flag[i]=1;
		}
	}
	cout <<res<<endl;
}

signed main(){
	cin >>n>>q;
	for(int i=1;i<=n;i++){
		cin >>tree[i];
	}
	dfs(1);
	solve();
	while(q--){
		int x;
		char z;
		cin >>x>>z;
		up(x,tree[x],z);
		tree[x]=z;
		cout <<res<<endl;
	}
	return 0;
}

构造题（数学）

待更新……

谢谢