NHOI2022总结

全过程：

T1：看到“质约数”时有点懵，但转念一想：“可能跟公约数有点相似”，便随便打了个代码交上去
T2：貌似是暴力枚举，打的代码感觉会爆，但是一时想不出优化方案，先交了
T3（原）：这题跟以前某道贪心题好像啊，不过做到一半突然换题，有点破防
T4（现）：这题……随便打个暴力吧
T5：第一个印象就是递归。一开始想的有点复杂，做了很久，不过最后用剪枝优化过掉了（听说有dp解法）
T6：这是啥啊……果断打样例
T7：打样例

结果：

T1:50
T2:10（好像）
T3:40
T4:50
T5:11
T6:0
fAKe

正解：

T1：

虽说“正整数n本身算不算自己的质约数”有点纠结，不过还是AC了
仔细思考，就能发现正整数n的质约数必然小于等于正整数n，所以只用枚举到n就行
关于质数，打个筛法表就OK了
难度评价：入门
代码：

#include <iostream>
#include <cmath>
using namespace std;
const int MAXN=1e6+35;
int n,b[MAXN];
void primeList(){
	b[0]=1;
	b[1]=1;
	for(int i=2;i<=sqrt(MAXN);i++){
		if(b[i]==0){
			for(int j=i+i;j<=MAXN;j+=i) b[j]=1;
		}
	}
}
int main(){
	cin>>n;
	primeList();
	for(int i=1;i<=n;i++){
		if(!b[i]&&n%i==0) cout<<i<<' ';
	}
	return 0;
}

T2：

作为暴力忠实的粉丝，我一开始想的就是暴力
直接无脑循环！！！
所以我一开始是这样打的：

#include <iostream>
using namespace std;
int n,w,a[3535],ans;
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=w;i++){
		bool zzx=false;
		for(int j=1;j<=n;j++){
			if(i==a[j]){
				zzx=true;
				break;
			}
		} 
		if(zzx){
			ans++;
			continue;
		}
		for(int j=1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if(i==a[j]+a[k]){
					zzx=true;
					break;
				}
			}
		} 
		if(zzx){
			ans++;
			continue;
		}
		for(int j=1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				for(int l=k+1;l<=n;l++){
					if(i==a[j]+a[k]+a[l]){
						zzx=true;
						break;
					}
				}
			}
		} 
		if(zzx) ans++;
	}
	cout<<ans;
	return 0;
}

评测机：10分
代码很冗长，10分很正常
赛后我把代码总结了一下：

#include <iostream>
using namespace std;
const int MAXN=1e6+35;
int n,w,a[3535],ans,b[MAXN];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=w;i++){
		for(int j=1;j<=n;j++){
			if(i==a[j]&&!b[i]) ans++,b[i]=1;
			for(int k=j+1;k<=n;k++){
				if(i==a[j]+a[k]&&!b[i]) ans++,b[i]=1;
				for(int l=k+1;l<=n;l++){
					if(i==a[j]+a[k]+a[l]&&!b[i]) ans++,b[i]=1;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

评测机：20分超时
我百思不得其解，最后被一位神犇的题解所点拨
他是这么写的：

因为数据n≤300，容易想到三重爆枚i,j,k,i≠j,j≠k,i≠k,开一个桶b并令b[a[i]+a[j]+a[k]=true即可
——wzr神犇

当时看到“桶”豁然开朗
虽然严格上来说，他没写完，但是思路是正确的
三重循环，不断枚举，使b[a[i]+a[j]+a[k]]=true,b[a[i]+a[j]]=true,b[a[i]]=true即可
上代码：

#include <iostream>
using namespace std;
const int MAXN=1e9+35;
int n,w,a[3535],ans;
bool b[MAXN];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=j+1;k<=n;k++)
				b[a[i]+a[j]+a[k]]=true;
			b[a[i]+a[j]]=true;
		}
		b[a[i]]=true;
	}
	for(int i=0;i<=w;i++)
	if(b[i]) ans++;
 	cout<<ans;
	return 0;
}

难度评价：普及-

T3（新）：

PS:此题为更改后的T3