社区讨论

帮忙看看(thanks)

P2668[NOIP 2015 提高组] 斗地主参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo1b3zii
此快照首次捕获于
2023/10/22 18:09
2 年前
此快照最后确认于
2023/11/02 18:27
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int n,ans=0,f[15],res,tmp;

inline bool ok(int l,int r,int num)
{
	for(int i=l;i<=r;i++) if(f[i]<num) return false;
	return true;
}

inline void erase(int l,int r,int num)
{
	for(int i=l;i<=r;i++) f[i]-=num;
	return;
}

inline void recover(int l,int r,int num)
{
	for(int i=l;i<=r;i++) f[i]+=num;
	return;
}

void dfs(int f[],int m)
{
	if(m==0){
		tmp=min(tmp,res);
		cout<<tmp;
		return;
	}
	//cout<<m<<" "<<res<<endl;
	if(res>=tmp) return;
	for(int i=1;i<=9;i++)
		for(int j=i+4;j<=13;j++)
		{
			if(ok(i,j,1)){
				erase(i,j,1); res++;
				dfs(f,m-(j-i+1));
				recover(i,j,1); res--;
			}
			else break;
		}
	for(int i=1;i<=11;i++)
		for(int j=i+2;j<=13;j++)
		{
			if(ok(i,j,2)){
				erase(i,j,2); res++;
				dfs(f,m-2*(j-i+1));
				recover(i,j,2); res--;
			}
			else break;
		}
	for(int i=1;i<=12;i++)
		for(int j=i+1;j<=13;j++)
		{
			if(ok(i,j,3)){
				erase(i,j,3); res++;
				dfs(f,m-3*(j-i+1));
				recover(i,j,3); res--;
			}
			else break;
		}
	 for(int i=1;i<=13;i++)
	 {
		 if(f[i]==4)
		 {
			 f[i]=0;
			 m-=4;
			 if(m>=2)
			 {
				 for(int j=1;j<=13;j++)
				 for(int k=j;k<=13;k++)
				 {
					 if(f[j]==0) break;
					 if(f[k]==0) continue;
					 f[j]--; f[k]--;
					 m-=2; res++;
					 dfs(f,m);
					 m+=2; res--;
					 f[j]++; f[k]++;
				 }
			 }
			 res++;
			 dfs(f,m);
			 res--;
			 f[i]=4;
		 }
	 }
	 for(int i=1;i<=13;i++)
	 {
		 if(f[i]==3)
		 {
			 f[i]=0;
			 m-=3;
			 if(m>=1)
			 {
				 for(int j=1;j<=13;j++)
				 {
					 if(f[j]==0) continue;
					 f[j]--;
					 m-=1; res++;
					 dfs(f,m);
					 m+=1; res--;
					 f[j]++;
				 }
			 }
			 if(m>=2)
			 {
				 for(int j=1;j<=13;j++)
				 for(int k=j;k<=13;k++)
				 {
					 if(f[j]==0) break;
					 if(f[k]==0) continue;
					 f[j]--; f[k]--;
					 m-=2; res++;
					 dfs(f,m);
					 m+=2; res--;
					 f[j]++; f[k]++;
				 }
			 }
			 res++;
			 dfs(f,m);
			 res--;
			 f[i]=3;
		 }
	 }
	 for(int i=1;i<=13;i++)
	 {
		 if(f[i]==2){
			 f[i]-=2; res++;
			 dfs(f,m-2);
			 f[i]+=2; res--;
		 }
	 }
	 for(int i=1;i<=13;i++)
	 {
		 if(f[i]==1){
			 f[i]-=1; res++;
			 dfs(f,m-1);
			 f[i]+=1; res--;
		 }
	 }
	return ;
}

void putls()
{
	memset(f,0,sizeof(f));
	int p1,p2,tot=0,m;
	for(int i=1;i<=n;i++)
	{
		cin>>p1>>p2;
		if(p1==0){
			ans=1; tot++;
		}
		else{
			if(p1>2) p1-=2;
			else p1=11+p1;
			f[p1]++;
		}
	}
	m=n-tot;
	dfs(f,m);
	cout<<tmp+ans<<endl;
	return;
}

int main()
{
	freopen("sutardays.in","r",stdin);
	freopen("sutardays.out","w",stdout);
	int T,m;
	cin>>T>>n;
	while(T--){
		tmp=10010;
		res=0;
		putls();
		/*for(int i=1;i<=13;i++) cout<<i<<" "<<f[i]<<endl;
		cout<<ans;*/
	}
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...