NOIp 2015 day1 解题报告

T1 神奇的幻方

按照题意模拟即可。

T2 信息传递

也是很水的一道题。有两种方法可以做。第一种是tarjan来求最小环,这个代码量略大。另外一种就是利用改版并查集,father数组存的是最远的祖先。具体实现看代码


#include<bits/stdc++.h>
using namespace std;
int f[200010],d[200010],n,minn,last;
int find(int x){
	if (f[x]!=x){
		int tmp=f[x];
		f[x]=find(f[x]);
		d[x]+=d[tmp];
	}
	return f[x];
}
int main(){
	freopen("message.in","r",stdin);
 	freopen("message.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++) f[i]=i;
	minn=0x7f7f7f7f;
	for (int i=1;i<=n;i++) {
		int t;
		cin>>t;
		int x=find(i),y=find(t);
		if (x!=y) f[x]=y,d[i]=d[t]+1;
		  else minn=min(minn,d[i]+d[t]+1);
	}
	cout<<minn;
	return 0;
}

T3 斗地主

这题挺有意思的,写完后发现会了很多斗地主技巧。首先一个显而易见的事实:有顺子时打顺子不一定是最优的,比如说我有一副 3 4 5 6 6 7 7 8 9 10,如果要打最长的顺子,这套牌要分三次才能打完。于是乎,我们只能暴力枚举了。另外其实还需要考虑其他的细节,但是这一题是随机数据,所以不加这些细节也能AC。如果要更高端的解法请移步这一题。


#include<bits/stdc++.h>
using namespace std;
int t,n,a[20],ans;
void dfs(int x){
	if (x>ans) return;
int s1,s2,s3,s4;
    s1=s2=s3=s4=0;
    for(int i=1;i<=14;i++)//统计单牌与对子
    {
     if(a[i]==1) s1++;
     if(a[i]==2) s2++;
    }
    for(int i=1;i<=14;i++)//四带的牌
    if(a[i]==4) 
    { 
     s4++;
     if(s1>=2) s1-=2;
     else if(s2>=2) s2-=2;
     else if(s2>=1) s2--;
    }
    for(int i=1;i<=14;i++)//三带的牌
    if(a[i]==3)
    {
        s3++;    
        if(s1>=1) s1--;
        else if(s2>=1) s2--;
    }
    ans=min(ans,x+s1+s2+s3+s4);//手中没牌,更新方案
    
	//以下枚举顺子 
	int j;
	for(int i=1;i<=8;i++){
		for (j=i;j<=12;j++){
			a[j]--;
			if (a[j]<0) break;
			if(j-i>=4) dfs(x+1);
		}
		if (j>=13) j--;
		while (j>=i) a[j--]++;
	}
	for (int i=1;i<=10;i++){
		for(j=i;i<=12;j++){
			a[j]-=2;
			if(a[j]<0) break;
			if(j-i>=2) dfs(x+1);
		}
		if (j>=13) j--;
		while (j>=i) a[j--]+=2;
	}
	for (int i=1;i<=11;i++){
		for(j=i;i<=12;j++){
			a[j]-=3;
			if(a[j]<0) break;
			if(j-i>=1) dfs(x+1);
		}
		if (j>=13) j--;
		while (j>=i) a[j--]+=3;
	}
	
}

int main(){
	freopen("landlords.in","r",stdin);
 	freopen("landlords.out","w",stdout);
	cin>>t>>n;
	for(int i=1;i<=t;i++){
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			int x,y;
			cin>>x>>y;
			if (x==0) a[14]++;
			if (x==1) a[12]++;
			if (x==2) a[13]++;
			if (x>=3) a[x-2]++;
		}
		ans=0x7f7f7f;
		dfs(0);
		cout<<ans<<endl;
	}
	return 0;
} 

以上

发表评论

电子邮件地址不会被公开。 必填项已用*标注