SSL 2682_YMW的杯子_bfs

发布于 2017-08-12  923 次阅读

题目描述

有一天YMW看见竞赛室里面放着n个正面向上的杯子，他随手把所有的杯子翻转成正面向下的杯子了。后来突然想起来自己有两只手，于是他尝试同时翻转两只杯子，看下最后能不能翻转成为全部正面朝下。聪明的你看到了这一切，突然脑子里面闪过一个问题，假如每次同时翻转m只杯子，最后能全部翻转成为正面朝下吗？（初始时全部正面朝上）

 

思路

因为是可以不连续放，所以我们是需要记录有多少个是正放的即可

然后暴力bfs出每种状态，加上判重就可以a了

#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x));
bool v[20001];
int main()
{
    while (1)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        if (m > n) m = m - n;
        if (n == -1 && m == -1) break;
        queue t;
        t.push(n);
        v[n] = 1;
        int fl = 1;
        while (!t.empty())
        {
            int now = t.front();
            t.pop();
            for (int i = 0; i <= m; i++)
                if (now >= i && n - now >= m - i && !v[now - 2 * i + m])
                {
                    v[now - 2 * i + m] = 1;
                    t.push(now - 2 * i + m);
                    if (now - 2 * i + m == 0)
                    {
                        fl = 0;
                        printf("Yes\n");
                        while (!t.empty()) t.pop();
                        break;
                    }
                }
        }
        if (fl) printf("No\n");
        fill(v, 0);
    }
}

 

]]>