自动搬运

查看原文

来自洛谷，原作者为

	yx666 幸会，OI。OI，幸会 。

搬运于2025-08-24 22:36:36，当前版本为作者最后更新于2024-05-02 11:51:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P8174 Stones 题解

Part 1：题意

Part 1.1：题目描述

游戏包含 $N$ 堆石子，其中第 $i$ 堆有 $a_i$ 个石子。你和对手交替指定石子堆 $k$（$a_k\neq0$，对手先指定石子堆），并让对方从石子堆 $k$ 中拿去 $[1,a_k]$ 个石子。拿到最后一个石子的人获胜。

求必胜策略（数据保证你有必胜策略）。

Part 1.2：交互题读入输出

从标准输入读入游戏的初始状态。初始状态有两行，第一行包含一个整数 $N$ ，第二行包含 $N$ 个空格隔开的整数，其中第 $i$ 个表示 $a_i$。

你的程序应根据现在是奇数或偶数轮给出不同的输出，具体地：

在奇数轮：

• 你的程序应先读入一个整数 $k$。如果此时所有的石子堆都是空的，$k=-1$，结束程序，因为你已经输了。否则 $k\in[1,N]$ ，代表你现在必须从第 $k$ 堆石子取走至少一个至多所有石子。保证第 $k$ 堆石子此时不为空。令当前第 $k$ 堆石子有 $s_k$ 个石子。
• 你的程序应输出一行一个 $[1,s_k]$ 中的整数，代表你从第 $k$ 堆石子希望取走的石子个数，然后刷新缓冲区。

在偶数轮：

• 你的程序应先输出一个整数 $k$，然后刷新缓冲区。如果此时所有的石子堆都是空的，$k$ 应为 $-1$，结束程序，因为你赢了。否则 $k\in[1,N]$，代表你希望对手从第 $k$ 堆石子取石子。应保证第 $k$ 堆石子此时不为空。令当前第 $k$ 堆石子有 $s_k$ 个石子。
• 你的程序应读入一行一个 $[1,s_k]$ 中的整数，代表对手从第 $k$ 堆石子取走的石子个数。

保证给出的初始状态使得你有必胜策略。

刷新缓冲区解释：

• 如果采用 cin、cout 读入输出，在每次输出时使用 cout.flush(); 或 cout<<endl;
• 如果采用 scanf、printf 读入输出，在每次输出时使用 fflush(stdout);

Part 2：思路

Part 2.0：定义

• $[P]$ 表示能否获胜，$[F]$ 表示是否是自己在取石子。

• 记剩下的石子数等于 $1$ 的石子堆个数为 $n$，石子数大于 $1$ 的石子堆个数为 $n'$，编号为 $i$ 的石子堆石子数为 $a_i$。

Part 2.1：极端情况

发现：如果没有石子数超过 $1$ 的堆，那么最后的赢家是确定的。

表示为：

$$[P]=\begin{cases} 1&[F]=0,n \bmod 2=0\\ 0&[F]=0,n \bmod 2=1\\ 0&[F]=1,n \bmod 2=0\\ 1&[F]=1,n \bmod 2=1\\ \end{cases}$$

Part 2.2：一般情况

由一般到特殊，中间的转折点就是仅剩 $1$ 堆大于 $1$ 的石子堆时。

所以我们只需要处理好 $n'\ne1$ 与 $n'=1$ 时就 OK 了。也就是要将最后一堆个数大于 $1$ 的石子堆将轮到我们取。

Part 2.2.1：$n'> 1$ 时决策：

目标就是要消耗掉个数大于 $1$ 的石子堆。记对手要求取的堆编号为 $p$。

1. $a_p=1$，拿走 $a_p$ 个。接下来给对手指定一个 $a_i=1$ 的堆 $i$。因为数据保证有必胜策略，而取走偶数个石子数为 $1$ 的堆是不影响结果的，所以可以这样干（也不用担心能否找到）。

2. $a_p>1$，拿走 $a_p-1$ 个，并指定对手拿一个 $a_i=1$ 的堆 $i$（这里可以用 $p$）。这样子就消耗掉个数大于 $1$ 的石子堆，达成目标。

Part 2.2.2：$n'=1$ 时决策：

上面已经保证了最后一堆个数大于 $1$ 的石子堆将轮到我们取，所以此时 $[F]=1$。记对手要求取的堆编号为 $p$。

• 如果 $a_p>1$，且 $n\bmod2=1$，取走 $a_p-1$ 个，使情况变为 $[F]=0,n\bmod2=0,n'=0$ 的必胜策略。

• 如果 $a_p>1$，且 $n\bmod2=0$，取走 $a_p$ 个，使情况变为 $[F]=0,n\bmod2=0,n'=0$ 的必胜策略。

• 否则，$a_p=1$，取走 $1$ 个。

Part 2.2.3：$n'=0$ 时决策：

无论对手怎么挣扎都能赢：

每次取都取一个，然后找到一个 $a_i=1$ 的堆 $i$ 让对手取即可。

Part 3：代码实现

改了好久发现自己少打了一个赋值。

#include<bits/stdc++.h>
using namespace std;

#define N 505
#define M 505
#define pii pair<int,int>

int n,a[N];
int cnt1=0,cnt2=0;	// cnt1：a_i=1 的石子堆个数，cnt2：a_i>1 的石子堆个数
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	auto get=[](){	// 得到一个 i 满足 a_i=1
		for(int i=1;i<=n;++i)
			if(a[i]==1){
				cout<<i<<endl;
				a[i]=0,--cnt1;
				int tp; cin>>tp;
				return i;
			}
		return -1;
	};
	
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(a[i]==1) ++cnt1;
		else if(a[i]>1) ++cnt2;
	}
	
	for(int p;;){
		cin>>p;
		if(a[p]==1){
			// 取石子
			cout<<1<<endl;
			a[p]=0,--cnt1;
			
			// 指定堆
			if(cnt1==0) break;
			p=get();
		}else{
			if(cnt2==1){
				if(cnt1%2){
					cout<<a[p]-1<<endl;
					a[p]=1,++cnt1,--cnt2;
					break;
				}else{
					cout<<a[p]<<endl;
					a[p]=0,--cnt2;
					break;
				}
			}else{
				// 取石子
				cout<<a[p]-1<<endl;
				a[p]=0,--cnt2;
				
				// 指定堆
				cout<<p<<endl;
				cin>>p;
			}
		}
	}
	
	
	// n'=0,[F]=0,n mod 2=0 的必胜策略
	for(int p;;){
		// 指定
		if(cnt1<=0) break;
		p=get();
		
		// 取石子
		cin>>p;
		a[p]=0,--cnt1;
		cout<<1<<endl;
	}
	
	cout<<-1<<endl;
	return 0;
}