P10152 拼图题解

T_TLucas_Yin · 2024-02-12 22:23:05 · 题解

题目的思路总体来说比较简单，但推导过程还是很有意思的。

首先要明白，既然对手绝顶聪明，所以肯定不会让你能一步连成三元环的三个点是同色的。所以，这样的三个点颜色只有两黑一白或两白一黑。如果我们连上了这三个点，对手就可以在同一回合把那个只出现一次的颜色反转，构成同色三元环，他就赢了。所以，不到对手走投无路，不要连三元环。

下面来看最优方案（只是保证必胜）。我们先想象给出的足够多个点排成了环状。将自己的视角带入 Alice。现在进行第一步操作，在任意两点间连一条边。

什么也不会发生。然后对手操作，把任意一个点变成黑色。

还是什么也不会发生。接下来我们这样操作：每次把上次连边的终点和一个未连上任何边的点连起来，最后一步把最后连上的点和第一个点连起来，形成一个环。然后把每个点和环上从它开始顺时针数第 3 个点连起来，直到每个点都与它左右相邻第 3 个点连有一条边。这总共需要 2n 回合。

在此期间，对手的操作方法是，任意改变点的颜色，只要保证任意三个连有两条边的点不是同种颜色的就行。因为，否则，我们就可以在出现同色后一步连上它们剩下的一条边，构成同色三元环。

事实上对手很可能坚持不到第 2n 回合。但我们假设对手足够谨慎，能撑到我们连上述最后一条边，因为到这时更容易证明对手已经必败了。

当我们进行了 2n 次操作，下面该对手操作时，局面大概是这样的（忽略颜色）：

现在对手改变任意一个点的颜色。事实上这时他无论怎么改我们都能一步杀。例如，他要把节点 1 由白色改为黑色。我们只看重要的几条边：

现在，1 要变为黑色。我们考虑与 1 连边的四个点（2，10，4，8）里有几个是黑色的。

需要用到的一个简单的定理是：此时任意三个相邻的点不是同色的。因为这样我们上一步就可以连接这三点间的最后一条边，就获胜了。

如果四个点没有黑色的，也就是说都是白色的，那 2 和 10 就都是白色的，而由于 1 刚才也是白色的，那么就出现了三邻点同色，所以矛盾，排除这种情况。
如果四个点有一个是黑色的。若黑色的是 2，则 10 和 8 一定是白色的，所以 9 是黑色的。现在 1 变成了黑色，那么我们下一步在 1 和 9 之间连边，就可以获胜。黑色的是 10 同理。若黑色的是 4，则 2 和 10 就都是白色的，与“没有黑色”的情况同理。若黑色的是 8 则与 4 同理。
如果四个点有两个是黑色的。由于我们考虑的这四个点都与 1 连有一条边，此时 1 变成黑色的了，不管黑色的是哪两个点，我们把与 1 连边的两个黑色点连起来，就形成了黑色的三元环，我们获胜。
如果有三个是黑色的或四个都是黑色的，则依旧可以连上其中任意两个点构成同色三元环，我们获胜。

如果要把一个点变成白色，那就考虑与它连边的四个点中有几个白色的，同理。由于此时每个点的连边情况都是一样的，所以把 1 换成其他节点还是同理。由此得出结论，我们必胜。

但别忘了我们考虑的是点足够多的情况。如果点变少会有所改变。

如果有一个点，我们没法操作，对方赢。
如果有两个点，我们只能操作一次，对方赢。
如果有三个点，我们最多只能连三元环，连好后对方赢。
如果有四个点，我们最多只能连四元环，连好后还是只能连三元环，对方赢。
如果有五个点，我们先连好五元环，此时连四元环就相当于在大环的另一侧连三元环，还是对方赢。

从 n=6 开始我们就可以按上边的套路必胜了。所以，在 n\le5 的情况下，对方赢。在 n>5 的情况下，我们赢。

代码还用放嘛？

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        if(n>5) cout<<"Alice\n";
        else cout<<"Shinobu\n";
    }
    return 0;
}

P10152 拼图 题解

P10152 拼图题解