CodeForces 1453 D. CheckpointsCodeForces 1453 D. Checkpoints

62 阅读 0 评论 41 点赞

我是靠谱客的博主欣慰心情，最近开发中收集的这篇文章主要介绍CodeForces 1453 D. CheckpointsCodeForces 1453 D. Checkpoints，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

CodeForces 1453 D. Checkpoints

题目大意：

构造一个序列， $1$ 就是当前关卡的存档点， $0$ 就不是，给一个 $k$ ，怎么构造关卡序列使得所有关卡的期望等于 $k$ ，每个关卡的通过率是 $1 2 frac 1 2$

思路：

思考后发现： $1$ 的关卡的期望一定是 $2$ ，问题就在 $0001$ 这种上面，在 $1$ 这个关卡上一定要 $2$ 次，那 $1$ 前面的 $0$ 就要 $4$ 次，因为 $4$ 次机会才会有两次机会通过，这两次机会才能通过后面的 $1$ ，所以不难发现规律

那事情就简单了，就按着这样一直去减即可，要注意题目规定了第一个关卡必须是 $1$ 。

每个关卡的期望贡献都是偶数，所以和一定是偶数，那奇数就是 $- 1$

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl 'n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

void solve()
{
    ll k;
    cin >> k;
    if(k & 1) {
        cout << -1 << endl;
        return ;
    }
    vector<int> ans;
    k -= 2;
    while(k) {
        ans.push_back(1);
        k -= 2;
        for(ll i = 4; i <= k; i <<= 1) {
            ans.push_back(0);
            k -= i;
        }
    }
    ans.push_back(1);
    reverse(ans.begin(), ans.end());
    
    cout << ans.size() << endl;
    for(int & i : ans)
        cout << i << " ";
    cout << endl;
}

int main()
{
    IOS();
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
    
    
    return 0;
}