Codeforces 1404D

Codeforces 题面传送门 & 洛谷题面传送门

首先注意到 (sumlimits_{i=1}^{2n}i=dfrac{2n(2n+1)}{2}=n(2n+1)equiv npmod{2n}),也就是说,如果我们能够在每个 pair 找到一个数,使取出的 (n) 个数加起来是 (n)​ 的倍数,那么后手就有必胜策略,因为如果取出的数之和 (mod 2n=0) 那么显然符合要求,否则我们这 (n) 个数之和 (mod 2n) 必然等于 (n),因此我们可以考虑取个补集,剩余数之和 (mod 2n) 显然就等于所有数之和减去取出的数之和,也就是 (2n) 的倍数了。

因此考虑分情况讨论:如果 (n) 是偶数那比较好办,我们考虑当先手,对于所有 (iin[1,n]),将 (i)(i+n) 分在一组,那么不论后手怎么取,他取出的 (n)​ 个数之和 (equivsumlimits_{i=1}^nipmod{n}),而显然 (sumlimits_{i=1}^ni=dfrac{n(n+1)}{2}=n·dfrac{n+1}{2}),后者不是整数,因此左式也不是 (n) 的倍数,因此后手无法取出 (n) 个数使它们的和为 (2n) 的倍数。

接下来考虑 (n) 是奇数的情况,显然根据此题的设计,(n) 为偶数的情况我们要选择当先手,那 (n) 为奇数的情况题目肯定要让我们当后手了,也就是说,我们要对于所有可能的分组情况,从每个 pair 中找出一个数,使它们的和是 (n) 的倍数。注意到对于奇数而言,就有 (sumlimits_{i=1}^ni)(n) 的倍数了,因此考虑 (equiv 1,2,3,cdots,n) 的数各取一个,怎么取呢?我们考虑对于所有 (iin[1,n])连一条 (i) 所在的 pair 到 (i+n) 所在的 pair 的有向边,权值为 (0),编号为 (i),同理连一条 (i+n) 所在的 pair 到 (i) 所在的 pair 的有向边,权值为 (1),编号为 (i),这样每个点恰好连出两条边,也就是说我们会形成若干个环,我们考虑以任意顺序(顺时针、逆时针皆可),那么在遍历的过程中,如果我们经过编号为 (i) 的边时经过的那条边权值为 (0),那么我们就选择 (i),否则如果经过编号为 (i) 的边时,经过的那条边权值为 (1),我们就选择 (i+n),不难发现这样每组恰好选择一个,而每个编号的边恰好遍历了一次,因此 (equiv 1,2,3,cdots,n) 的数也都各取一个,因此和肯定是 (n) 的倍数。注意,如果最后选出来的数之和 (mod 2n=n) 那么还需取个补集。

坑点:注意 fflush(stdout)

const int MAXN=5e5;
int n,p[MAXN*2+5],hd[MAXN*2+5],to[MAXN*2+5],nxt[MAXN*2+5],id[MAXN*2+5],ec=1;
void adde(int u,int v,int x){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;id[ec]=x;}
bool vis[MAXN*2+5],book[MAXN*2+5];int ans[MAXN+5];
void dfs(int x,int pre,int st){
//	printf("%d %d
",x,pre);
	vis[x]=1;
	for(int e=hd[x];e;e=nxt[e]){
		int y=to[e],z=id[e];if((e>>1)==(pre>>1)) continue;
		book[z*n+(e>>1)]=1;if(y^st) dfs(y,e,st);return;
	}
}
int main(){
	scanf("%d",&n);
	if(~n&1){
		puts("First");
		for(int i=1;i<=n<<1;i++) printf("%d%c",i%n+1," 
"[i==n<<1]);
		fflush(stdout);
	} else {
		puts("Second");fflush(stdout);ll sum=0;
		for(int i=1;i<=n<<1;i++) scanf("%d",&p[i]);
		for(int i=1;i<=n;i++) adde(p[i],p[i+n],0),adde(p[i+n],p[i],1);
		for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0,i);
		for(int i=1;i<=n<<1;i++) sum+=book[i]*i;
		if(sum%(n<<1)){
			for(int i=1;i<=n<<1;i++) book[i]^=1;
		} for(int i=1;i<=n<<1;i++) if(book[i]) ans[p[i]]=i;
		for(int i=1;i<=n;i++) printf("%d%c",ans[i]," 
"[i==n]);
		fflush(stdout);
	}
	return 0;
}
原文地址:https://www.cnblogs.com/ET2006/p/Codeforces-1404D.html