SOS Gym – 101775L(博弈找规律)

题目链接:https://cn.vjudge.net/problem/Gym-101775L
题目大意:1*n的矩阵,两个人轮流填充s或o先出现连续的sos的赢,两个人足够聪明,问对于给定的n,结果是什么
解题思路:
首先不难推出必胜态是S _ _ S,一但构成了这种状态,谁先在里面落子谁就会输,现在要想构成这样的状态,先手一定会去下一个S,而后手一定会用一个O堵在S+3或者S-3的位置。
由此可得,当n小于7的时候是必平,因为长度限制无论先手把s放到哪里都只能构成s+3或者s-3中的一种必胜态,后手可以轻易的将对方堵死。
当n>=7的时候,7之所以会先手赢是因为当先手把S放到中间的时候,向左向右都能够成一个必胜态,而后手只能堵死其中的一个,又因为出现了必胜态后谁都不想先在那两个S中间下子,因为只要有人在两个S中间下子那么另一个人一定会在下一步凑出SOS,也就是要计算两个S之外剩余的可以落子的数量,由此可见当n为奇数的时候先手必赢,
而n为偶数的时候后手却不一定必赢,因为先手会阻挠后手获胜达到平局的状态,后手获胜只能发生在n>=15的状态下,因为n>=15的时候无论先手在哪里落子,都有一边的空各子数量大于7,这样的话相当于B先手且格子数大于7且格子数为奇数(不看先手的第一个落子),由之前的判断可以得出后手必胜。
代码

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

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int n;
    int kk=0;
    while(t--)
    {
        kk++;
        cin>>n;
        if(n<7)
        {
            cout<<"Case #"<<kk<<": Draw"<<endl;
        }
        else if(n%2)
        {
            cout<<"Case #"<<kk<<": Panda"<<endl;
        }
        else if(n>14&&n%2==0)
        {
            cout<<"Case #"<<kk<<": Sheep"<<endl;
        }
        else
        {
            cout<<"Case #"<<kk<<": Draw"<<endl;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注