[CF1453D] Checkpoints

[CF1453D] Checkpoints - 概率,构造

Description

需要设计一个游戏关卡，由01字符串组成，1表示存档点，0表示普通关卡，规定每一步可以从第i个关卡前进到第i+1个关卡，不过有0.5的概率会成功，剩下0.5的概率会失败，失败的话会返回最近的存档点重新开始，现在问如何设计关卡，可以使得到达终点的期望为k

Solution

手推一下找找规律，首先我们一定可以将序列划分为若干个 100...00 的串的连接，即每个 1 开始的部分是一个独立的部分，各个独立部分之间的贡献是和的关系

我们发现，一个 1 贡献 2，一个 10 贡献 6，一个 100 贡献 14……

注：这里每个部分内部的 f(n) 都是 2 的整数幂 2^n，然后 f(n-1)=f(n)+2^(n-1)

所以每个部分的贡献是 (2(2^n -1)) 的形式，我们贪心地每次拆出极大的这样的部分即可

显然所有偶数都是有解的，所有奇数都是无解的

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
        if (n & 1)
        {
            cout << -1 << endl;
        }
        else
        {
            n /= 2;
            vector<int> ans;
            while (n)
            {
                int q = 1, pw2q = 2;
                while (pw2q * 2 - 1 <= n)
                    ++q, pw2q *= 2;
                n -= pw2q - 1;
                for (int i = 1; i <= q; i++)
                    ans.push_back(i == 1 ? 1 : 0);
            }
            cout << ans.size() << endl;
            for (auto i : ans)
                cout << i << " ";
            cout << endl;
        }
    }
}