自动搬运

查看原文

来自洛谷，原作者为

	Junounly 自有明月照山河，自有山河映明月。

搬运于2025-08-24 22:53:30，当前版本为作者最后更新于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;
}