1 条题解

  • 0
    @ 2026-5-4 20:51:59

    显然的,每个数最大是之前所有数之和,也就是二倍上一个数(特别地,第二个数为 11),所以最少需要 log2x+1\lceil \log_2 x \rceil +1 次操作。下面证明这个次数可以做到。

    考虑对于一些位,不取前面所有数的和,而是前面所有数的和 1{}-1(不选择第一个数)。于是我们会发现:

    • 当前数会少 11
    • 下一个数也会少 11
    • 下下个数会少两个 11 的和,也就是 22
    • 后面第三个数会少 1+1+2=41+1+2=4
    • 以此类推,后面第 ii 个数会少 2i12^{i-1}

    于是不难想到,我们先对所有操作选择前面所有的数,然后提取最后一个数(记为 xx),计算 xqx-q 然后二进制拆分,对应的操作不选择第一个数即可。

    :::success[code]

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    #define lowbit(x) ((x)&(-(x)))
    const int N=2e6+10,mod=1e9+7;
    void solve()
    {
    	int x;
    	cin>>x;
    	int fx=ceil(log2l(x));
    	int tx=(1ll<<fx);
    	int cx=tx-x;
    	cout<<fx+1<<'\n';
    	for(int i=1;i<=fx+1;i++)
    	{
    		if(cx&(1ll<<(fx-i))) cout<<2<<' '<<i<<'\n';
    		else cout<<1<<' '<<i<<'\n';
    	}
    }
    signed main()
    {
    	ios::sync_with_stdio(0);
    	cin.tie(0),cout.tie(0);
    	int t;
    	cin>>t;
    	while(t--) solve();
    	return 0;
    }
    

    :::

    • 1

    信息

    ID
    10798
    时间
    2000ms
    内存
    100MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者