题解:P7356 「PMOI-1」游戏

naughty-naught / 2024-10-15 / 原文

Problem Link

「PMOI-1」游戏

题意

给你一个胜利规则为 黑白白白 的棋类游戏,你执白,黑先行且第一步必下 \((0,0)\),双方皆可放弃落子且落子坐标必须为自然数,请在 4 步内获胜。

思路

在自己与自己对下几局之后,有几个显然的发现:

  • 黑棋会尽量阻止你 4 步获胜。

  • 在你不会再下一步就获胜前,黑棋弃子非常合理(因为黑子多下会多提供获胜必须的 )。

综合思考,发现必须要让你落一子后黑子也落子才有获胜之机。

如何做到这个呢?

思考几下,发现:假设黑棋第二步必弃子

此时不论黑方怎么落子我们都胜了,所以我们第一步下 2 时黑方必须下 1 或 3 或 4。把它展开到二维时在模拟几下,发现第一步下 \((2,2)\) 时,继续在另一处构造上图情况即可。

其他疑问见代码及注释。

// written by Naught

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

typedef long long ll;
// #define int long long
#define Maxn 105
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
// #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<21], *p1 = buf, *p2 = buf;
// inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
// inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
// void train() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}

int main()
{
    // T = read();
    int T, x, y;
    cin >> T ;
    while (T--)
    {

        cout << "2 2" << endl; cin >> x >> y;
        if ((x == 1 && y == 1) || (x == 3 && y == 3) || (x == 4 && y == 4)) // 黑方堵你
        {
            cout << "0 3" << endl; cin >> x >> y;
            if (x == 0 && y == 2)
            {
                cout << "3 2" << endl; cin >> x >> y;
                if (x == 1 && y == 2) cout << "4 2" << endl;
                else cout  << "1 2" << endl; // 黑方摆了
            }
            else if(x == 0 && y == 4)
            {
                cout << "3 1" << endl; cin >> x >> y;
                if(x == 1 && y == 3) cout << "4 0" << endl;
                else cout << "1 3" << endl; // 黑方摆了
            }
            else if(x == 0 && y == 1)
            {
                cout << "0 4" << endl; cin >> x >> y;
                if(x == 0 && y == 2) cout << "0 5" << endl;
                else cout << "0 2" << endl; // 黑方摆了
            }
            else
            {
                cout << "0 2" << endl; cin >> x >> y;
                if(x == 0 && y == 1) cout << "0 4" << endl;
                else cout << "0 1" << endl; // 黑方摆了
            }
        }
        else // 黑方摆了
        {
            cout << "3 3" << endl;
            cin >> x >> y;
            if(x == 1 && y == 1) cout << "4 4" << endl;
            else cout << "1 1" << endl; // 黑方摆了
        }
    }
    return 0;
}

/*
    自己与自己对下以发现规律
    不懂时多画图
*/

Tips

  • 第一步交互库走的 \((0,0)\) 无需输入。