CF1427F Boring Card Game

Description

Solution

• 居然是一道贪心/构造题。
• 首先不考虑轮流选择的，那么显然我们可以把能够删的删去，不断重复。实际上这个也可以写成栈的形式。
• 现在再来考虑一下轮流选择的时候，如果我们用栈的形式，显然可以贪心地构造一棵树出来，只需要每一次选择叶子并保证剩下至少一个属于后手的根即可。
• 可以证明的是，由于个数是一样的，并且保证至少有一个属于后手的根（即有解），讨论一下即可知道选择叶子一定是可行的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1205
using namespace std;

int n,i,j,k,a[maxn],bz[maxn],du[maxn],used[maxn],res;
int d[maxn][3],id[maxn],c[maxn],p[maxn][3],tot,w,fa[maxn];

int main(){
	scanf("%d",&n);
	for(i=1;i<=3*n;i++) scanf("%d",&k),a[k]=1;
	for(i=1;i<=6*n;i++){
		if (!w||a[d[w][0]]!=a[i])
			w++,d[w][0]=i,c[w]=1,id[w]=++tot;
		else {
			d[w][c[w]++]=i;
			if (c[w]==3) {
				k=id[w],fa[k]=id[w-1],bz[k]=a[d[w][0]];
				memcpy(p[k],d[w],sizeof(p[k]));
				w--;
			}
		}
	}
	for(i=1;i<=tot;i++) du[fa[i]]++;
	for(i=1;i<=tot;i++) if (fa[i]==0&&bz[i]==0) res++;
	for(i=1;i<=2*n;i++){
		int c=i&1,x=0;
		for(j=1;j<=tot;j++) if (du[j]==0&&!used[j]&&bz[j]==c){
			if (i<2*n&&c==0&&fa[j]==0&&res==1) continue;
			x=j;break;
		}
		printf("%d %d %d\n",p[x][0],p[x][1],p[x][2]);
		du[fa[x]]--,used[x]=1;
		if (c==0&&fa[x]==0) res--;
	}
}