A-F Codeforces Round #806 (Div.4) A-F题解及代码

题意及要求：给定**均为小写字母且长度为3**的字符串，判断它是否为"YES",同时"yES",“Yes”,"yes"都是满足答案的。

思路：字面意思的题目不解释。

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void solve(){
	string s;
	cin >>s;
	if((s[0]=='Y'||s[0]=='y')&&(s[1]=='E'||s[1]=='e')&&(s[2]=='s'||s[2]=='S')){
		cout <<"YES"<>T;
	while(T--){
		solve();
	}
	return 0;
}

题意：在ICPC比赛中，每做出来一个题目，队伍将得到一个气球，完成此题的队伍是第一个做出来此题的，则得到一个额外的气球。

要求：现给定一个字符串，用A,B,C…,Z表示26个题目，第i个字符表示该问题已经被某个团队解决（没有队伍会两次解决同一个问题），求此次比赛共有多少个气球。

思路：遍历此字符串的每个字符，若这个字符是第一次出现，则气球数量+2，若不是第一次出现，则气球数量+1。

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void solve(){
	map mp;
	int n;
	string s;
	cin >>n>>s;
	int ans = 0;
	for(int i=0;iT;
	while(T--){
		solve();
	}
	return 0;
}

题意：有一个密码锁，如下图，他的密码区域是可旋转的，可以执行下面两种操作：

• 向上转动（以字符U来表示）：将密码数字增加1，但将9向上转动后，则会变成0。
• 向下转动（以字符D来表示）：将密码数字减少1，但将0向下转动后，则会变成9。

要求：给出最终的密码，以及轮子的若干移动方向，求出原始密码。

思路：字面意思，反过来求解原始密码。

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int a[mn];

void solve(){
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	for(int i=1;i<=n;i++){
		int num;
		cin >>num;
		int ans = a[i];
		for(int i=1;i<=num;i++){
			char x;
			cin >>x;
			if(x=='D'){	//如果向下转动,则原始密码应+1;
				ans++;
			}else{		//如果向下转动，则原始密码应-1;
				ans--;
			}
			if(ans==-1){
				ans=9;
			}
			if(ans==10){
				ans=0;
			}
		}
		cout <>T;
	while(T--){
		solve();
	}
	return 0;
}

题意及要求：给出n个字符串，每个字符串长度不超过8；对于每个字符串，若它可以由其他两个字符串（可以是相同的字符串）拼接起来，则输出1，否则输出0。

思路：

• 若将每个字符串暴力判断，则时间复杂度为O(n^2)，会TLE。

• 但是若将字符串用map标记存储，再将每个字符串判断，则可以将时间复杂度降低到O(n*length)。

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

string a[mn];

void solve(){
	map mp;
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		mp[a[i]]=true;
	}
	for(int i=1;i<=n;i++){
		bool pd = true;
		if(pd)
		for(int j=0;j>T;
	while(T--){
		solve();
	}
	return 0;
}

题意：存在一个n行*n列的矩阵，每一个格子存在一个数字，你每次可以将任意一个格子的数字变化（将0变成1或将1变成0）。
要求：你将进行若干次变化，求一个最小次数的变化后，这个矩阵进行0度，90度，180度，270度旋转后矩阵不变；

思路：将矩阵分为四4个，判断左上角这个矩阵中每个格子旋转各个角度所对应的格子（共四个）中0和1的数量，若：

• 0的数量少：则将这些格子全部变成1，次数+四个格子中0的数量
• 1的数量少：则将这些格子全部变成0，次数+四个格子中1的数量

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int a[200][200];

void solve(){
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		string s;
		cin >>s;
		for(int j=0;jT;
	while(T--){
		solve();
	}
	return 0;
}

题意及要求：给出n个数组a1，a2，…，an，求有多少个满足ai < i < aj < j（i和j为下标）。

思路：将满足ax < x的下标记录下来，然后将这些记录下来的下标所对应的值ax与这些下标进行比较，每有一个大于坐标的值，答案+1；故我们用树状数组记录下标。

代码：

#include
#define IOS std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long
#define endl "n"

using namespace std;

const int mn = 1e5+10;
const int mod = 1e9+7;
const int N = 2e5+10;
int dr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n = 262144;
int d[262145];
int a[N];

int lowbit(int x){
	return x&(-x);
}

int query(int x){
	int res=0;
	while(x){
		res+=d[x];
		x-=lowbit(x);
	}
	return res;
} 

void update(int x,int v){
	while(x<=n){
		d[x]+=v;
		x+=lowbit(x);
	}
}

void solve(){
	memset(d,0,sizeof(d));
	vector t;
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
		if(a[i]T;
	while(T--){
		solve();
	}
	return 0;
}