【Codeforces Round ＃808 (Div 2.) A·B·C】

$Better\; reading\; experience$

---

---

A. Difference Operations

---

Original link

Origional Link

---

thought

• if $a_i(i>=2)$ Can pass $a_i=a_i-a_{i-1}$ Turn into $0$
• explain ：$a_{i-1}|a_i$
• if $a_{i-1}(i>=2)$ Can pass $a_{i-1}=a_{i-1}-a_{i-2}$ Turn into $0$
• explain ：$a_{i_2}|a_{i-1}$
• It can be obtained. , When $a_i(i>=2)$ It can be $0$ when
• explain ：$a_1|a_i$

---

Code

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

const int N = 1e6 + 3;

int a[N];

void solve(){
    
	
	int n;
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i++){
    
		cin >> a[i];
	}
	
	bool flag = 1;
	
	int t = a[1];
	
	for(int i = 2 ; i <= n ; i++){
    
		if(a[i] % t != 0){
    
			flag = 0;
			break;
		}
	}
	
	if(flag) cout << "YES" << "\n";
	else cout << "NO" << "\n";
	
}

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

---

B. Difference of GCDs

---

Original link

Origional Link

---

thought

• requirement $gcd(i,a_i)$ In the sequence formed ,$gcd(i,a_i)$ All different
• explain $gcd(i,a_i)=i$, namely $i|a_i$
• So it needs to be in the interval $[l,r]$ Search for $i$ Multiple
• about $a_i$, if $l⩽a_i=\lfloor \frac{r}{i}\rfloor \times i⩽r$, Then the conditions are met

---

Code

---

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

const int N = 1e6 + 3;

int a[N];

void solve(){
    
	
	int n, l, r;
	cin >> n >> l >> r;
	
	bool flag = 1;
	
	for(int i = 1; i <= n; i++){
    
		
		a[i] = r / i * i;
		if(a[i] < l ){
    
			flag = 0;
			break;
		}
		
	}
	
	if(flag){
    
		cout << "YES" << "\n";
		for(int i = 1; i <= n; i++) cout << a[i] << " ";
		cout << "\n";
	}
	else cout << "NO" << "\n";
	
}

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

---

C. Doremy’s IQ

---

Original link

Origional Link

---

thought

• Reverse greed
• Consider from the last day , Set the upper limit of IQ to $Q$, The IQ on the last day is $q_i=0$
• if $a_i⩽q_i$, Is the first $i$ Day's game needs to be played
• if $a_i>q_i$, And $q_i<Q$ when , Ruodi $i$ Day fight , be $q_i=q_i+1$
• because $a_i>q_i$ I played the most games $Q$ Time , For the previous games, we should continue to play , need $q_i$ As big as possible
• so $a_i>q_i$, And $q_i<Q$ when , This section $i$ Days of competition must be played ,$q_i=q_i+1$
• if $a_i>q_i$, And $q_i=Q$ when , The first $i$ Days of competition cannot be played

---

Code

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

const int N = 1e6 + 3;

int a[N];

void solve(){
    
	
	int n,m;
	
	cin >> n >> m;
	
	string s(n,'0');
	
	for(int i = 0; i < n; i++) cin >> a[i];
	
	int q=0;
	
	for(int i = n-1; i >= 0; i--){
    
		
		if(a[i] <= q) s[i] = '1';
		else if(a[i] > q && q < m){
    
			q++;
			s[i] = '1';
		}
		
	}
	
	cout << s << "\n";
	
}

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

---

Postscript

• I was a little nervous during the competition this day
• $A$ and $B$ They are all types of mathematical proof , It's troublesome to think , Get yourself trapped
• After the game, I found that $A$ and $B$ It's so simple , Or my math foundation is not good , Suffer a great loss QAQ
• $C$ Question one eye DP, Greed was considered during the game , But it didn't prove , I don't know how to deal with the problem of reverse greed
• I hope it will turn green soon ......（ I'm so stupid ）