[THUPC 2024 初赛] 三步棋-题解

Junounly · 2023-12-20 22:25:27 · 题解

很有意思的一道题，使我的手旋转赛时手玩出结论，为了弥补吃的两发罚时造福后人，写的详细一点

题目大意是多组询问，每次给你一个 5\times5 的方格和一个不超过 4 个棋子的连通图案，两个人轮流，每次各放一个棋子，直到一方拼出给定图案。若此时棋盘上棋子个数是 3 的倍数，其获胜；反之另一方获胜。求先手是否必胜。

情况不多，选择分类讨论。（事实上 ICPC 赛制可以把所有情况都试一遍）

令 t= 给定图案的棋子个数。

• 若 t=1，先手必败。（这不用解释吧）

• 若 t=2，样例已经解释过了，当先手放下棋子，后手只有两种选择：与或者不与先手放下的棋子组成图案。如果与，那么棋盘上有 2 颗棋子，先手就赢了；如果不与，先手只需要下 1 颗棋与刚才的组成图案，棋盘上有 3 颗棋子，先手还是赢，所以先手必胜。

• 若 t=3，考虑第 1 个赢的机会，此时场上有 3 颗棋子，先手下 2 颗，后手下 1 颗，此时先手刚下完，只能先手赢，若先手想赢，那就必须使 3 颗棋子组成图案，那后手就要尽量避免这种情况，后手只需要在先手下完第 1 颗棋子后，选 1 个不可能与那颗棋组成图案的位置即可，所以第 1 个机会一定用不到；接着考虑第 2 个赢的机会，此时场上有 6 颗棋子，先手下 3 颗，后手下 3 颗，同理只能后手赢，若后手想赢，就可以直接用这 3 颗棋子的机会拼出图案，所以先手必败。

• 若 t=4，同样考虑第 1 个赢的机会，场上棋子不到 4 颗，不可能赢；考虑第 2 个赢的机会，还是先手下 3 颗，后手下 3 颗，后手显然有一种策略就是利用先手的第 1 颗棋和自己的 3 颗拼出图案，但如果后手无法利用先手的第 1 颗棋呢？（我赛时就因为这个吃了罚时）

• 由于将图案旋转后不会影响结果，所以可以简化成以上 5 种形状，容易发现，对于形状 1 和 2，不存在后手无法利用的位置，所以先手必败；对于形状 3、4 和 5，先手只要下左上角，后手就无法利用这颗棋子，那么后手将失去第 2 次机会，接下来考虑第 3 次机会，此时场上有 9 颗棋子，先手下 5 颗，后手下 4 颗，先手虽然已经浪费掉第 1 次机会来阻止后手利用，但剩下的 4 颗棋子足够组成图案，所以先手必胜。

经过上面的分类讨论，最终只需要依次判断并输出结果就可以了。

Code:

#include<bits/stdc++.h>
using namespace std;
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        char c;int cnt=0;
        int mnx=6,mny=6,mxx=0,mxy=0;
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
            {
                cin>>c;
                if(c=='o')
                {
                    cnt++;
                    mnx=min(mnx,i);mny=min(mny,j);
                    mxx=max(mxx,i);mxy=max(mxy,j);
                }
            }
        printf(cnt==2||(cnt==4&&(mxx-mnx>=2||mxy-mny>=2)&&(mxx-mnx<3&&mxy-mny<3))?"Far\n":"Away\n");
    }
    return 0;
}