Codeforces Round 1048 A

逆向思维有时真的很重要

这道题因为初始时两人数量一样，因此并不需要作区分，因为题目保障有解所以肯定有且仅有一个解。所以我们直接从末状态开始看。一个人是x个，另一个就是n-x个。我们只需要一直操作，直到他们相等即可。

• 我们因为是倒序操作，因此最好用stack（LIFO）的特性储存操作；
• 每次操作让两个数中较小的那个翻倍即可；

    int x = (int)pow(2, n), y = (int)pow(2, n);
    stack<int> sk;
    int t = x * 2;
    int fin_1 = m, fin_2 = t - m, cut = 0;
    while (fin_1 != fin_2)
    {
        if (fin_1 < fin_2)
        {
            cut++;
            fin_2 -= fin_1;
            fin_1 = fin_1 * 2;
            sk.push(1);
        }
        else
        {
            cut++;
            fin_1 -= fin_2;
            fin_2 *= 2;
            sk.push(2);
        }
    }
    cout << cut << endl;
    while (!sk.empty())
    {
        cout << sk.top() << " ";
        sk.pop();
    }