CF2138A/2139C Cake Assignment 题解

· · 题解

题意简析

两个数，初始都等于 2^k，执行任意（可以为 0）次以下操作后分别变成 x 和 2^{k+1}-x：

  1. 当第一个数为偶数时，第二个数可以加上第一个数的一半，第一个数同时减少一半；
  2. 当第二个数为偶数时，第一个数可以加上第二个数的一半，第二个数同时减少一半。

给定 k,x\ (1\le k\le 60，1\le x\le 2^{k+1}-1)，求出操作序列。

代码/解释

显然无论从初始状态开始如何操作，这两个数都一直为正整数。所以对于状态 \{x,y\}，若执行第一种操作得到 \{x'=\dfrac{x}{2},y'=y+\dfrac{x}{2}\} 时一定有 x'<y'，若执行第二种操作得到 \{x'=x+\dfrac{y}{2},y'=\dfrac{y}{2}\} 时一定有 x'>y'。根据结论反推每次操作的结果即可。

#include<bits/stdc++.h>
using namespace std;
stack<int> st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long x,y;
    int t,k;
    cin>>t;
    while(t--)
    {
        cin>>k>>x;
        y=(1ll<<k+1)-x;
        while(x!=1ll<<k)
        if(x<y)
        y-=x,x*=2,st.push(1);
        else
        x-=y,y*=2,st.push(2);
        printf("%d\n",st.size());
        while(!st.empty())
        printf("%d ",st.top()),st.pop();//用栈倒序输出
        printf("\n");
    }
    return 0;
}