【Codeforces Round ＃806 (Div. 4)(A~F)】

$Better\; reading\; experience$

---

---

A. YES or YES?

---

The main idea of the topic

Origional Link

• Judge whether it is yes Sequential case insensitive strings
• Yes, output YES, Otherwise output NO

---

thought

• Read into violent judgment

---

Code

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

void solve(){
    
	
	string s;
	
	cin >> s;
	
	bool flag = 1;
	
	if(s[0] != 'y' && s[0] != 'Y') flag = 0;
	if(s[1] != 'e' && s[1] != 'E') flag = 0;
	if(s[2] != 's' && s[2] != 'S') flag = 0;
	
	if(s.size() == 3 && flag) cout << "YES" << endl;
	else cout << "NO" << endl;
	
}

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

---

B. ICPC Balloons

---

The main idea of the topic

Origional Link

• common $A\sim Z$ Problem , For the first time, send out two balloons , Then a balloon appears
• Ask how many balloons will be sent out in the competition

---

thought

• vis[i] Whether the mark has ever appeared
• Send two if they don't appear , Appeared and sent one
• Traversal string summation

---

Code

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

const int N = 1010;

typedef long long LL;

bool vis[N];

void solve(){
    
	
	memset(vis,0,sizeof vis);
	
	int n;
	
	cin >> n;
	
	LL cnt = 0;
	
	while(n--){
    
		
		char a;
		cin >> a;
		
		if(!vis[a]){
    
			cnt += 2;
			vis[a] = 1;
		}
		else cnt ++;
		
	}
	
	cout << cnt << endl;
	
}

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

---

C. Cypher

---

The main idea of the topic

Origional Link

• Each password lock has $n$ A wheel , On the wheel $0\sim 9$
• Give the number of the final position display $a_i$, And the $i$ Location $b_i$ operations
• Find the original number

---

thought

• simulation
• ans[i] Store the $i$ The final number of bits , use flag The offset of the storage operation
• if U be flag --, conversely flag ++
• about ans[i], Add its offset and take a positive integer modulus , namely ans[i] = ( ans[i] + flag % 10 + 10 ) % 10 It is the original number

---

Code

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

const int N = 1010;

int n;

int ans[N];

void solve(){
    
	
	cin >> n;
	
	for(int i = 1; i <= n; i ++) cin >> ans[i];
	
	for(int i = 1; i <= n; i ++){
    
		
		int m;
		cin >> m;
		
		int flag = 0;
		
		while(m--){
    
			char op;
			cin >> op;
			if(op == 'D') flag ++;
			else flag --;
		}
		
		ans[i] = (ans[i] + flag % 10 + 10) % 10;
		
	}
	
	for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
	
	cout << endl;
	
}

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

---

D. Double Strings

---

The main idea of the topic

Origional Link

• Given $n$ No longer than $8$ String $s$
• If for $s_i=s_j+s_k$ establish , be $s_i$ Marked as $1$, Otherwise, mark as $0$

---

thought

• $n$ The larger , but $s_i$ Shorter
• about $s_i$, Construct two at a time $s_i$ String $s_i^{\prime },s_i^{\prime \prime }$, Query the string
• If both strings can be found , Then mark $s_i$ by $1$, Instead of $0$
• utilize s[N] and set<string> st Store all at the same time s[i]
• Traverse s[i], The first string is from s[0] Start , The length is 1 <= j <= s[i].size() - 1 , The second string is from s[j] Start , The length is s[i].size() - j
• utilize st.count(s) Query string s

---

Code

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

void solve(){
    
	
	int n;
	
	cin >> n;
	
	bool vis[n + 10];
	
	memset(vis,0,sizeof vis);
	
	set<string> st;
	
	string s[n + 1];
	
	for(int i = 0; i < n; i ++){
    
		cin >> s[i];
		st.insert(s[i]);
	}
	
	for(int i = 0; i < n; i ++){
    
		if(s[i].size() == 1) continue;
		for(int j = 1; j <= s[i].size() - 1; j ++){
    
			string s1 = s[i].substr(0,j), s2 = s[i].substr(j,s[i].size() - j);
			if(st.count(s1) == 1 && st.count(s2) == 1){
    
				vis[i] = 1;
				break;	
			}
		}
	}
	
	for(int i = 0; i < n; i ++){
    
		if(vis[i]) cout << 1;
		else cout << 0;
	}
	
	cout << endl;
	
}

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

---

E. Mirror Grid

---

The main idea of the topic

Origional Link

• Given by $0$ and $1$ Form a square array
• Select the array to the right 90 degree ,180 degree ,270 degree
• Find out how to change the value in the original array , Make the values in the four forms of the array all the same, and change the minimum number of operations

---

thought

• A position in the original two-dimensional array mp[i][j] After three rotations , It will appear in three positions in total
• namely mp[j][n + 1 - i]、mp[n + 1 - i][n + 1 - j]、mp[n + 1 - j][i]
• Count the value of the original position and the value of these three new positions to become the same minimum number of operations

---

Code

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

const int N = 110;

char mp[N][N];

bool st[N][N];

void solve()
{
    
    int n;
    cin >> n;
    
    memset(st, 0, sizeof st);
	
	for (int i = 1; i <= n; i++) cin >> mp[i] + 1;
        
    int ans = 0;
    
    for (int i = 1; i <= n; i++){
    
        for (int j = 1; j <= n; j++){
    
        	if(i == j && n % 2 == 1) continue;
        	
            if(!st[i][j]){
    
                int cnt = 0;
                if(mp[i][j] == '1') cnt++;
                
                st[i][j] = 1;
                if(mp[j][n - i + 1] == '1') cnt++;
                
                st[j][n - i + 1] = 1;
                if(mp[n - i + 1][n - j + 1] == '1') cnt++;
                
                st[n - i + 1][n - j + 1] = 1;
                if(mp[n - j + 1][i] == '1') cnt++;
                
                st[n - j + 1][i] = 1;
                
                ans += min(cnt, 4 - cnt);
            }
        }
    }
    
    cout << ans << endl;

}

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

---

F. Yet Another Problem About Pairs Satisfying an Inequality

---

The main idea of the topic

Origional Link

• For sequence $a$, Find satisfaction $a_i<i<a_j<j,1\le i,j\le n$ Of $i,j$ logarithm

---

thought

• about $a_i<i<a_j<j,1\le i,j\le n$
  • Must be satisfied with a[i] < i, take a[i] >= i Deletion of , Do not participate in subsequent matching
  • Must be satisfied with i < a[j],{i,j} The logarithm of is i Previous satisfaction a[i] < i The number of
• enumeration j, Binary search minimum satisfaction i < a[j] The location of , Total quantity plus i All previous satisfaction a[i] < i The number of

---

Code

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

const int N = 1e6 + 3;

int a[N];

typedef long long LL;

LL cnt;

vector<int> st;

void solve(){
    
	int n;
	cin >> n;
	
	st.clear();
	cnt = 0;

	for(int i = 1; i <= n; i ++) cin >> a[i];

	for(int i = 1; i <= n; i ++){
    
		if (a[i] >= i) continue;
		cnt += (lower_bound(st.begin(), st.end(), a[i]) - st.begin());
		st.push_back(i);
	}
	
	cout << cnt << endl;
}
 
int main(){
    
	
	int _;
	
	cin >> _;
	
	while(_--){
    
		solve();
	}
	
	return 0;
	
}