题解：P12572 [UOI 2023] An Array and Addition Again

Vct14 · 2025-06-06 04:32:27 · 题解

构造好玩捏！

我们发现通过增量操作我们可以轻易地将一个数翻倍。所以考虑递归当前数应为多少。但是如果当前数 k 是奇数的话其无法通过翻倍得到，而翻出 k-1 之后再加一也不好处理。于是考虑一开始就将所有 a_i 均赋为 1。如此若 k 为奇数，可以直接递归 \dfrac {k-1}2；否则在递归前先将当前 a_i 赋为 2，然后递归 \dfrac{k-2}2。

可以发现每次递归实质上是消去了 k 的一个二进制位，最终目标为 1 位（即 1）。而 k 最多有 \left\lfloor\log_2 10^{18}\right\rfloor+1=60 位，因此需要的最大 a 数组大小约为 60<100，操作次数 s<99+(60-1)\times3=276<300。因此这样构造是正确的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define add op.push_back(i)

vector<int> op;
void work(int i,int k){
    if(k==1) return ;
    if(k==2){add;return ;}
    if(!(k%2)) add;
    work(i+1,(k-1)/2); // k 为偶数时，(k-2)/2==(k-1)/2
    add;add; // 将 a_i 赋值为 $a_{i+1}*2
}

signed main(){
    int t,g;cin>>t>>g;
    while(t--){
        op.clear();
        int n;cin>>n;
        for(int i=99; i>=1; i--) add;
        work(1,n);
        cout<<op.size()<<"\n";
        for(int x : op) cout<<x<<" "; 
        cout<<"\n";
    }
    return 0;
}