NOIP2015提高组复赛day1解析

1.

 解析：

送分题，按题意模拟即可

代码：

#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;
const int N = 39+7;
int a[N][N],n;
map<int,pair<int,int> >mp;
int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
	memset(a,0,sizeof(a));
	cin>>n;
	a[1][(n+1)/2]=1;
	mp[1]=make_pair(1,(n+1)/2);
	for(int i=2;i<=n*n;i++){
		pair<int,int> k=mp[i-1];
		if(k.x==1&&k.y!=n){
			a[n][k.y+1]=i;
			mp[i]=make_pair(n,k.y+1);
		}else if(k.y==n&&k.x!=1){
			a[k.x-1][1]=i;
			mp[i]=make_pair(k.x-1,1);
		}else if(k.x==1&&k.y==n){
			a[k.x+1][k.y]=i;
			mp[i]=make_pair(k.x+1,k.y);
		}else{
			if(!a[k.x-1][k.y+1]){
				a[k.x-1][k.y+1]=i;
				mp[i]=make_pair(k.x-1,k.y+1);
			}else{
				a[k.x+1][k.y]=i;
				mp[i]=make_pair(k.x+1,k.y);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

2.

 解析：
这道题通过模拟数据可以发现，本题可转化为求图内最小环的长度，数据不大，可以直接dfs

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+39+7;
int n,a[N],vis[N],num[N],ans=1e9;
void dfs(int x,int step){
	if(vis[x])return;
	if(num[x]){
		ans=min(ans,step-num[x]);
		vis[x]=1;
	}
	num[x]=step;
	dfs(a[x],step+1);
	num[x]=0;
	vis[x]=1;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0);
	cout<<ans;
	return 0;
}

3.

 解析：

这道题可以每次预处理cnt和p数组，用来搜索使用，然后写一个爆搜，枚举这几种情况，就可以非常快的过掉这道题

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 39+7;
int n,T,cnt[N],p[N],ans;
int find(){
	memset(cnt,0,sizeof(cnt));
	int x=0;
	for(int i=0;i<15;i++)cnt[p[i]]++;
	while(cnt[4]){
		cnt[4]--;x++;
		if(cnt[2]>=2)cnt[2]-=2;
		else if(cnt[1]>=2)cnt[1]-=2;
	}
	while(cnt[3]){
		cnt[3]--;x++;
		if(cnt[2])cnt[2]--;
		else if(cnt[1])cnt[1]--;
	}
	if(p[0]&&p[1]&&cnt[1]>=2)x--;
	return x+cnt[1]+cnt[2];
}
void dfs(int x){
	if(x>ans)return;
	int tmp=find();
	if(x+tmp<ans)ans=x+tmp;
	for(int i=3;i<=14;i++){
		int j=i;
		while(p[j]&&j<15){
			p[j]--;
			if(j-i+1>=5)dfs(x+1);
			j++;
		}
		while(j>i)p[--j]++;
	}
	for(int i=3;i<=14;i++){
		int j=i;
		while(p[j]>=2&&j<15){
			p[j]-=2;
			if(j-i+1>=3)dfs(x+1);
			j++;
		}
		while(j>i)p[--j]+=2;
	}
	for(int i=3;i<=14;i++){
		int j=i;
		while(p[j]>=3&&j<15){
			p[j]-=3;
			if(j-i+1>=2)dfs(x+1);
			j++;
		}
		while(j>i)p[--j]+=3;
	}
}
int main(){
	cin>>T>>n;
	while(T--){
		ans=n;
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++){
			int x,y;cin>>x>>y;
			if(!x)p[y-1]++;
			else if(x==1)p[14]++;
			else p[x]++;
		}
		dfs(0);
		cout<<ans<<'\n';
	}
	return 0;
}