当前位置:网站首页>Cf688div2 1453d. Checkpoints

Cf688div2 1453d. Checkpoints

2020-12-07 10:48:10 osc_ kiub62pt

Portal

The question

Construct a string of long n n n A sequence of zeros ( n < = 2000 ) (n<=2000) (n<=2000)

Yes 1 2 \frac{1}{2} 21 The probability of successful passage of i i i A level

If you fail , Return immediately less than or equal to i i i The smallest 1 1 1 Location


Observation found that if only one 1 1 1, The expected number of steps through the past is 2 2 2

If you want to calculate, it's very simple , Let's go through a single 1 1 1 The expectation is x x x

Yes 1 2 \frac{1}{2} 21 The probability of going through , 1 2 \frac{1}{2} 21 The probability of one step failure , Expectations are also needed x x x adopt

that x = 1 2 ∗ 1 + 1 2 ∗ ( x + 1 ) x=\frac{1}{2}*1+\frac{1}{2}*(x+1) x=211+21(x+1)

Solution x = 2 x=2 x=2

Then the final constructed sequence can be decomposed into several forms such as 1 0 0 0 In the form of ( Of course 1 1 1 There can be no 0 0 0)

Definition f [ i ] f[i] f[i] For the first one 1 1 1, Followed by i − 1 i-1 i1 individual 0 0 0 Through the number of steps

So from the above derivation f [ 1 ] = 2 f[1]=2 f[1]=2

We can get the following recursion

f [ i ] = f [ i − 1 ] + 1 + 1 2 ∗ [ f [ i − 1 ] + ( f [ i ] − f [ i − 1 ] ) ] f[i]=f[i-1]+1+\frac{1}{2}*[f[i-1]+(f[i]-f[i-1])] f[i]=f[i1]+1+21[f[i1]+(f[i]f[i1])]

I'll explain the equation , Want to break through number one i i i A level , The premise is that before the breakthrough i − 1 i-1 i1 A level , Expectation is f [ i − 1 ] f[i-1] f[i1]

Now take a chance to try to break through number one i i i A level , Expectation is 1 1 1

1 2 \frac{1}{2} 21 The probability of a breakthrough i i i A level , There's no extra cost

1 2 \frac{1}{2} 21 The probability of not breaking back to where it started 1 1 1

So first of all, we need to go back to i − 1 i-1 i1 A place needs f [ i − 1 ] f[i-1] f[i1], Break through the first i i i You need to expect f [ i ] − f [ i − 1 ] f[i]-f[i-1] f[i]f[i1]

So we get the formula above , Put the one on the right f [ i ] f[i] f[i] Move the item to the left , Solution f [ i ] f[i] f[i]

f [ i ] = 2 ∗ f [ i − 1 ] + 2 f[i]=2*f[i-1]+2 f[i]=2f[i1]+2

So we find that every small unit is an even number expectation , So when k k k There is no solution for odd numbers

Otherwise, it must be from big to small 1   0   0   0   0... 1\ 0\ 0\ 0\ 0... 1 0 0 0 0...

Because the final unit is f [ 1 ] = 2 f[1]=2 f[1]=2, So as long as it's even k k k, Can be constructed

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+10;
int f[maxn],k;
vector<int>ans;
signed main()
{
   
    
	f[1] = 2;
	for(int i=2;i<=60;i++)	f[i] = 2*f[i-1]+2;
	int t; cin >> t;
	while( t-- )
	{
   
    
		ans.clear(); int flag = 1;
		cin >> k;
		while( k )
		{
   
    
			for(int i=60;i>=1;i--)
				if( f[i]<=k )
				{
   
    
					k-=f[i];	ans.push_back(1);
					for(int j=2;j<=i;j++)	ans.push_back(0);
					break;
				}
			if( k%2==1 ){
   
     flag=0; break; }
		}
		if( ans.size()>2000 )	flag=0;
		if( flag == 0 )	cout << -1;
		else
		{
   
    
			cout << ans.size() << endl;
			for(int i=0;i<ans.size();i++)
				cout << ans[i] << " ";
		}
		cout << endl;
	}
}

版权声明
本文为[osc_ kiub62pt]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207104656926n.html