题解：P8174 [CEOI2021] Stones

yx666 · 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：定义

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

Part 2.1：极端情况

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

表示为：

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。

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;
}