P8144 [JRKSJ R4] BBWWBB 题解

· · 题解

题目链接

link

题目大意

六个棋子，分布于数轴上六个位置，颜色从左至右依次为 BBWWBB，两名玩家轮流操作己方棋子，左移或右移一个单位长度，直到一方无棋可动，另一方获胜。

分析

观察&猜测

首先，观察询问，题目只需要回答游戏是否会无限进行下去，所以我们无需考虑具体过程。

仔细阅读样例解释，出题人分别举了两种结果各一个例子

  1. W 被 B 全数消灭，输出 No。
  2. W 逃脱，输出 Yes。

由此我们可以大致猜测，因为 W 棋子少于 B 棋子，所以结果不是 W 被全数消灭，就是 W 成功逃脱，不存在 B 被 W 消灭的情况。

分情况讨论

是否存在一种情况使得 B 被 W 尽数消灭呢？我们看下图

显而易见，对于单颗 W ，要么主动送死，要么与 B 换子。

显然，若 W 坐以待毙，左右的 B 迟早会强迫 W 与之换子（如上图第二块），此时 B 获胜。所以，W 必须主动出击。

W 很容易就能形成 WW，此时可以与黑强制换一子（如上图），但此后又陷入了图一的情况。

难道 W 就不可能逃脱吗？肯定不是，再次观察样例解释2，出现了以下情况：

关键：先手 W 并且有 W 与一个且仅有一个 B 相邻（与两个 B 相邻，见图2），此时，W 便可以顺利逃脱。

这里可能有读者有疑问：在上图第二步时如果后方 B 追上来怎么办。

因为这里是两个 W 移动，所以移动速度平均为 1/2 格，而后方同样为两个 B，所以相对静止（如果只有一个 B 追上来并不能强迫 W 换子）。

另外还有一种情况：

不言而喻

结论

因为 W 逃脱条件更少，我们判 W 是否能顺利逃脱。

Code

#include<bits/stdc++.h>
int pos[7],T;char c;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    std::cin>>T;
    while(T--)
    {
        std::cin>>c;
        for(int i=1;i<=6;i++) std::cin>>pos[i];
        if ((c=='W')//W 先手
        && ((pos[3]-pos[2]==1&&pos[2]-pos[1]>1)
        ||  (pos[5]-pos[4]==1&&pos[6]-pos[5]>1))//有
        &&(!(pos[3]-pos[2]==1&&pos[5]-pos[4]==1)))//且仅有一侧与W相邻
             std::cout<<"Yes\n";
        else std::cout<<"No\n";
    }
    return 0;
}