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

$更好的阅读体验$

---

---

A. YES or YES?

---

题目大意

Origional Link

• 判断是否是yes顺序的不区分大小写的字符串
• 是则输出YES，否则输出NO

---

思想

• 读入暴力判断

---

代码

#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

---

题目大意

Origional Link

• 共$A\sim Z$道题，第一次出现送出两个气球，后续出现送出一个气球
• 求比赛共送出多少气球

---

思想

• vis[i]标记是否出现过
• 未出现的送出两个，出现过送出一个
• 遍历字符串求和

---

代码

#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

---

题目大意

Origional Link

• 每个密码锁有$n$个轮子，轮子上有$0\sim 9$
• 给出最终位置显示的数字$a_i$，和第$i$个位置的$b_i$次操作
• 求原始的数字

---

思想

• 模拟
• ans[i]存储第$i$位的最终数字，用flag存储操作的偏移量
• 若为U则flag --，反之flag ++
• 对于ans[i]，加上其偏移量并取正整数模，即ans[i] = ( ans[i] + flag % 10 + 10 ) % 10即为原始数字

---

代码

#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

---

题目大意

Origional Link

• 给定$n$个长度不超过$8$的字符串$s$
• 若对于$s_i=s_j+s_k$成立，则$s_i$标记为$1$，否则标记为$0$

---

思想

• $n$比较大，但$s_i$较短
• 对于$s_i$，每次构造两个$s_i$的字串$s_i^{\prime },s_i^{\prime \prime }$，对字串进行查询
• 若两个字串都可以找到，则标记$s_i$为$1$，反之为$0$
• 利用s[N]和set<string> st同时存储所有的s[i]
• 遍历s[i]，第一个字串从s[0]开始，长度为1 <= j <= s[i].size() - 1 ，第二个字串从s[j]开始，长度为s[i].size() - j
• 利用st.count(s)查询字串s

---

代码

#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

---

题目大意

Origional Link

• 给定由$0$和$1$构成正方形数组
• 将数组向右选择90度，180度，270度
• 求如何改变原数组中的值，使得四种形态的数组里的值都一样的改变最少操作次数

---

思想

• 原二维数组中的一个位置mp[i][j]旋转三次后，总共会出现在三个位置上
• 即mp[j][n + 1 - i]、mp[n + 1 - i][n + 1 - j]、mp[n + 1 - j][i]
• 统计原位置的值和这三个新位置的值变为相同的最小操作次数即可

---

代码

#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

---

题目大意

Origional Link

• 对于数列$a$，找到满足$a_i<i<a_j<j,1\le i,j\le n$的$i,j$对数

---

思想

• 对于$a_i<i<a_j<j,1\le i,j\le n$
  • 一定满足a[i] < i，将a[i] >= i的删去，不参与后续匹配
  • 一定满足i < a[j]，{i,j}的对数为i之前的满足a[i] < i的数量
• 枚举j，二分查找最小满足i < a[j]的位置，总数量加上i之前的所有满足a[i] < i的数量

---

代码

#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;
	
}