＃ CF ＃808 Div.2(A - C)

A Difference Operations（ thinking , intuition ）

Description:

​ Give the array a, about i (2 <= i <= n) It can be executed ai = ai - a_i-1 The operation of

​ Could you let me know (2 <= i <= n) Of ai Zero clearing

Solution:

​ yes a1 The multiple of can be cleared as 0, Second cut

Code:

void solve()
{
    
	cin >> n;
	int x;
	cin >> x;
 
	bool ok = true;
	for(int i = 1; i < n; i ++)
	{
    
		int xx;
		cin >> xx;
		if(xx % x != 0)
			ok = false;
	}
	if(ok)
		cout << "YES\n";
	else 
		cout << "NO\n";
}

B Difference of GCDs（ thinking , structure ）

Description:

​ give n, And interval [l, r]. You need to construct a sequence ai (1 <= i <= n) bring gcd(i, ai) Each are not identical

​ If there is a solution , Output YES And sequence a, No solution output NO

Solution:

​ because i The value is [1, n], therefore gcd If the result is different , It must be distributed in [1, n]（ gcd(a, b) <= min(a, b) ）

​ Since it is distributed like this , We might as well order gcd(i, ai) == i, because ai It's not said that you can't take duplicates , So directly for each i Go to [l, r] Look inside i The first multiple of

Code:

int n;
LL l, r;

void solve()
{
    
	cin >> n >> l >> r;
	vector<LL> res;

	for(int i = 1; i <= n; i ++)
	{
    
		LL st = i * ((l + i - 1) / i); // Round up 
		if(st > r)
		{
    
			cout << "NO\n";
			return;
		}
		else 
			res.pb(st);
	}
	cout << "YES\n";
	for(auto x : res)
		cout << x << ' ';
	cout << '\n';
}

C Doremy’s IQ（ greedy , Guess the conclusion ）

Description:

​ Yes n Game and initial IQ q, Decide whether to participate in the i game , If participating in section i Games and q < ai When ,q –

​ Only q > 0 When , Can participate in the competition

​ Output one 01 strand ,1 Means to participate in the game , Ask for 1 As much as possible

Solution:

​ At first I thought it was DP, But found DP You can't save q(q = 1e9) This state means , Thought it was greedy but didn't think of a strategy .

​ After the game, I read the big man's solution , It's what I guessed , But I can't convince myself that it's right . Be positive next time WA Try it

6 4
5 4 4 4 4 4
 Through this example, we find , A positive ergodic solution cannot be obtained . We need to think backwards .

​ You can think of it greedily , At the end, I just put q Flowers , And only possible to participate in the competition . Then the question becomes when to choose to participate in the competition .

​ Look backwards , If current position q_now < a_i, Play in your current position and make q_now ++, In this case, we will ensure that all the following items are taken , At present q_now Has been the best strategy .

Code:

const int N = 100005;
int n, q;
int a[N];
int res[N];

void solve()
{
    
	memset(res, 0, sizeof res);
	cin >> n >> q;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];

	int cur = 0;
	for(int i = n; i >= 1; i --)
	{
    
		if(cur >= a[i])
			res[i] = 1;
		else if(cur < q)
			cur ++, res[i] = 1;
	}

	for(int i = 1; i <= n; i ++)
		cout << res[i];
	cout << '\n';
}