P10026 「HCOI-R1」哀之变化题解

Guoliyuan2023 · 2024-01-08 22:12:21 · 题解

学哥出的题，当然得写个题解啊

题目：P10026 「HCOI-R1」哀之变化

思路：

我们发现如果对 a 直接模拟很难处理，所以选择对 n 进行逆向操作。

用最少的步数使 n 变为 1，再考虑如何处理多余的次数，若次数不足则直接无解。

于是先分类讨论（第一步）：

若 2|n，则让 n=n\div2；

若 2|(n+1)，则让 n=(n+1)\div2；

接下来处理剩余的次数。

我们欣喜的发现，竟然有周期哎！

于是乎，若剩余次数大于 1，则必定有解。

对于剩余 1 的情况，我们应该尽量将其加入到我们的缩减过程中，但列出式子后，我们发现，在这种情况下，无解。

最后，注意两点：

2. 不要搞岔！！！

放上代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int T , n , m , a , b;
    bool flag = 0;
    cin >> T;
    while(T --)
    {
        m = 0;
        flag = 0;
        b = 0;
        cin >> a >> n;
        if(n == 0)
        {
            if(a != 0)
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
            continue;
        }
        if(n == 1)
        {
            if(a == 1 || a == 3)
            {
                cout << "No" << endl;
            }
            else
            {
                cout << "Yes" << endl;
            }
            continue;
        }
        while(n > 1)
        {
            m ++;
            if(n % 2 == 1)
            {
                if(m == 1)
                {
                    flag = 1;
                }
                else
                {
                    flag = 0;
                }
            }
            if(n % 2)
            {
                n ++;
                b = 1;
            }
            else
            {
                n /= 2;
            }
        }
        if(((b == 0 || flag) && a - m == 1) || m > a)
        {   
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
    }
    return 0;
}