zrt的NOIP信心赛

~~好！很简单！非常简单！简单到T1又爆零了！~~

A 扫雷游戏

题意：有三种炸弹，爆炸范围不一样，给出炸弹位置，求(m imes n) 中每个位置被炸弹覆盖的数量

模拟 m和n不要写反要注意数组越界问题

码：

#include<bits/stdc++.h>
using namespace std;
const int N=521;

int n,m,f[N][N];

char rd(){                       
    int re=0;
    char ch=getchar();
    while ((ch<'A'||ch>'C')&&ch!='o') ch=getchar();
    return ch;
}

int main(){
	
	cin>>m>>n;
	
	char k;
	memset(f,0,sizeof f);
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			k=rd();
			if(k=='A'){
				f[i][j]++;
				if(i-1>0) f[i-1][j]++;
				if(j-1>0) f[i][j-1]++;
				if(i+1<=m) f[i+1][j]++;
				if(j+1<=n) f[i][j+1]++;
			}else if(k=='B'){
				f[i][j]++;
				if(i-1>0) f[i-1][j]++;
				if(j-1>0) f[i][j-1]++;
				if(i+1<=m) f[i+1][j]++;
				if(j+1<=n) f[i][j+1]++;
				if(i-1>0&&j-1>0) f[i-1][j-1]++;
				if(j-1>0&&i+1<=m) f[i+1][j-1]++;
				if(i+1<=m&&j+1<=n) f[i+1][j+1]++;
				if(j+1<=n&&i-1>0) f[i-1][j+1]++;
			}else if(k=='C'){
				f[i][j]++;
				if(i-1>0) f[i-1][j]++;
				if(j-1>0) f[i][j-1]++;
				if(i+1<=m) f[i+1][j]++;
				if(j+1<=n) f[i][j+1]++;
				if(i-1>0&&j-1>0) f[i-1][j-1]++;
				if(j-1>0&&i+1<=m) f[i+1][j-1]++;
				if(i+1<=m&&j+1<=n) f[i+1][j+1]++;
				if(j+1<=n&&i-1>0) f[i-1][j+1]++;
				if(i-2>0) f[i-2][j]++;
				if(j-2>0) f[i][j-2]++;
				if(i+2<=m) f[i+2][j]++;
				if(j+2<=n) f[i][j+2]++;
			}
		}
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)
			printf("%d ",f[i][j]);
		printf("
");
	}
	
	return 0;
}

B 三维gcd

题意：给出一个(n)个数的序列，求其中任选三个数gcd的最大值

法一：把每个数的所有因子求出来并记录某个数在因子中出现的次数（除(1)），扫一遍求最大的数量大于等于(3)的因子即答案，如果没有大于等于(3)的，输出(1)

复杂度是(O(nsqrt{n}))

法二：从(a_i)最大值扫到(1)，把每个值当因子，查询它的倍数在序列中的出现情况，若该数倍数在序列里出现次数大于(3)，则为答案

复杂度是(O(nlogn))

mua：

#include<bits/stdc++.h>
using namespace std;
const int N=500010,M=1000010;

int cnt=0,n,sum[M],maxn;

void work(int x){
	sum[x]++;
	for(int i=2;i<=x/i;i++){
		if(x%i==0){
			sum[i]++;
			sum[x/i]++;
		}
	}
}

int rd(){                       
    int re=0;
    char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9'){ 
        re=re*10+ch-'0'; 
        ch=getchar();
    }
    return re;
}

int main(){
	
	cin>>n;
	
	if(n<3){printf("0");;return 0;}
	
	for(int i=1;i<=n;i++){
		int k;
		k=rd();
		work(k);
		maxn=(k>=maxn)?k:maxn;
	}
	
	int ans=1;
	
	for(int i=2;i<=maxn;i++){
		ans=sum[i]>=3?i:ans;
	}
	
	printf("%d",ans);
	
	return 0;
}

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;

int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}

int n;
int a[1000005];
int cnt[1000005];

const int MAXN = 1000000;
const LL mod = 998244353;

int mx;
LL anscnt;
LL sum;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}

	for(int i=MAXN;i>=1;i--){
		int tot = 0;
		for(int j=1;i*1LL*j<=MAXN;j++){
			tot += cnt[i*j];
		}
		if(tot>=3){
			printf("%d
",i);
            return 0;
		}
	}
    
	cout<<mx<<endl;
	return 0;
}

C 关押罪犯

~~不是并查集是DP~~

题意：给出一个无向图，要把点分成(ans)组，使得每组内的边数不超过(k)，求(ans)的最小值

状压DP

因为(n)很小所以可以状压

先预处理出每种情况是否可行

然后再把每种可能的情况枚举子集进行DP

转移方程是：

[f[S]=min(f[S],f[S-S']+1) ]

其中(S)代表一种状态，(S')代表(S)的一个子集

代码里有注释

码：

#include<bits/stdc++.h>
using namespace std;
const int N=25;

int n,m,k;

int g[N][N];

bool ok[1<<N];
int f[1<<N];

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		x--;y--;
		g[x][y]=g[y][x]=1;
	}
	for(int s=0;s<1<<n;s++){
		int tmp=0;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(g[i][j]&&((s>>i)&1)&&((s>>j)&1)) tmp++;//计组内边数
			}
		}
		if(tmp<=k) ok[s]=1;//判断情况成不成立
	}
	f[0]=0;
	
	for(int s=1;s<1<<n;s++){
		f[s]=n;
		for(int s2=s;s2>0;s2=(s2-1)&s){//这个的功能是枚举s的所有子集 可以手玩一下
			if(ok[s2]){
				f[s]=min(f[s],f[s-s2]+1);//状态转移方程
			}
		}
	}
	
	printf("%d
",f[(1<<n)-1]);//全集
	return 0;
}