Codeforces Round #806 (Div. 4)

The topic isez Most people believe that card is stuck inG 第一次在csdnWritten in the answer key,Typography is not yet proficient 见谅hhh

A YES or YES?

签到题,For zero basis can alsoa掉

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

const int N=100005;

int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		string s;
		cin>>s;
		int ok=1;
		if(s[0]!='Y'&&s[0]!='y')ok=0;
		if(s[1]!='E'&&s[1]!='e')ok=0;
		if(s[2]!='S'&&s[2]!='s')ok=0;
		puts(ok?"YES":"NO");	
	}
	return 0;
}

B ICPC Balloons

显然 ,The answer is the length of the string+The number of distinct characters in the string,I opened hereset,当出现一个字符,see if it appears for the first time,第一次出现ans++,然后插进去
Pay attention to get a blood reward

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

int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		int n;
		string s;
		cin>>n>>s;
		int ans=0;
		set<int>se;
		for(int i=0;i<n;i++){
    
			if(se.count(s[i])==0)ans++,se.insert(s[i]);
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C Cypher

密码锁
Tell you the last position to find the initial position
Watch out for scrolling up and down don't oppose
有负数 加10Take the modulook

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

const int N=100005;
int a[N];
int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
		cin>>a[i];
		for(int i=0;i<n;i++){
    
			int m;
			string s;
			cin>>m>>s;
			for(auto x:s){
    
				if(x=='D')
				a[i]++;
				else
				a[i]--;
			}
			a[i]=(a[i]%10+10)%10;
			printf("%d%c",a[i],"\n"[i+1==n]);
		} 
	}
	return 0;
}

D Double Strings

The topic of this question is to see whether a string can be composed of two other strings in a set of strings
不难发现 s[j]是s[i]的前缀 s[k]是s[i]的后缀
If I take a string, I use it heresubstr 两个参数是（取的位置,取几个字符）If the second parameter is not filled in, it will be taken to the end
我这里还是用set After taking it out, continue tosetfind it inok
能达到nlogn级别

（In fact, it started withmap做的,过了 使用map,In order to quickly find a string exists,But in order to maintain my single-minded personality,I chose to changeset）

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

const int N=100005;

string s[N];

int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		int n;
		string ans;
		cin>>n;
		set<string>se;
		for(int i=0;i<n;i++)
		cin>>s[i],se.insert(s[i]);
		for(int i=0;i<n;i++){
    
			int ok=0;// 标记 See if I can have two string concatenation 
			for(int j=1;j<s[i].size();j++){
    
				string x=s[i].substr(0,j),y=s[i].substr(j);
				if (se.count(x)&&se.count(y))ok=1;
		    }
		ans.push_back('0'+ok);		    
		}
	cout<<ans<<"\n";		
	} 
	return 0;
}

E Mirror Grid

拜托 I'm really excited to see the matrix, okay?？
The theme is Ask you to change the minimum number of times Then flip the four orientation matrices unchanged
In fact as long as find the location of the string after the flipok了…
Just slap the recursion formula by yourselfOK---------（x,y）->(y,n-1-x),The formula is also easy to find

统计一下1多0多
0的个数为0或者为4就不用变,直接continue;
0的个数为1就改一个;
0的个数为1just change two;
0的个数为3就改1;

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
char s[N][N];
int main(){
    
	int _;
	scanf("%d",&_);
	while(_--){
    
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
    
			scanf("%s",s[i]);
		}
		int ans=0;
		for(int i=0;i<n;i++){
    
			for(int j=0;j<n;j++){
    
				int x=i,y=j;
				int cnt=0;
				for(int k=0;k<4;k++){
    
					cnt+=s[x][y]=='0';
					int ox=x,oy=y;
					x=oy;
					y=n-1-ox;
				}
				if(cnt==0||cnt==4)continue;
				char t;
				if(cnt==1)t='0',ans+=1;
				if(cnt==2)t='0',ans+=2;
				if(cnt==3)t='1',ans+=1;
				x=i,y=j;
				for(int k=0;k<4;k++){
    
					s[x][y]=t;
					int ox=x,oy=y;
					x=oy;
					y=n-ox-1;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

F Yet Another Problem About Pairs Satisfying an Inequality

给个数组
key在ai<i<aj<j.这里;
key中key在i<aj这里;
对于每个i小于ajThe method is just prefixed and maintained directlys[aj-1] 开b数组
注意防止越界a[i]是可以等于0的

#include<bits/stdc++.h>
using namespace std;
typedef int long long LL; 
const int N=200005;
int a[N],s[N]; 
int main(){
    
	ios::sync_with_stdio(false);
	int _;
	scanf("%d",&_);
	while(_--){
    
		int n;
		scanf("%d",&n);
		LL ans=0;
		for(int i=1;i<=n;i++){
    
			scanf("%d",&a[i]);
			s[i]=s[i-1]+(a[i]<i);
			if(a[i]<i&&a[i]-1>=1){
    
				ans+=s[a[i]-1];
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

G Good Key, Bad Key

此题 我wa on 4Two sentorz,is a typical greed
其实想到 All the good keys must be in front of the bad keys
eg：0是好,1是坏
如果你是10010 value will be low
如果你是11000 The high value of open up and go to bad,Definitely the highest value
Apparently you know how to do it Do you know that good is a prefix,Bad is the suffix？？？
那就s【i】Is the prefix minusi*kPlus you suffixok
elements behindvector里面就好了,Of course, to maintain my unique personality,I keep using mineset
复杂度达到nlogn的级别
enumerate backwards
To open a temporary array
The two arrays can be swapped after they are finished

#include<bits/stdc++.h>
using namespace std;
typedef int long long LL;
const LL mod=1e9+7;
const int N=200005;

int a[N];
LL s[N];

int main(){
    
   ios::sync_with_stdio(false);
   int _;
   scanf("%d",&_);
   while(_--){
    
   	int n,m;
   	scanf("%d%d",&n,&m);
   	LL ans=0;
   	for(int i=1;i<=n;i++){
    
   		scanf("%d",&a[i]);
   		s[i]=s[i-1]+a[i];
   	}
   	multiset<int>se;
   	for(int i=n;i>=0;i--){
    
   		LL now=s[i]-(LL)m*i;
   		for(auto x:se)now+=x;
   		ans=max(ans,now);
   		se.insert(a[i]);
   		multiset<int>tmp;
   		for(auto x:se){
    
   			if(x/2>0)tmp.insert(x/2);
   		}
   		swap(se,tmp);
   	}
   	printf("%lld\n",ans);
   }
   return 0;
}

总的来说 ,The subject is still relativelyez,Basic Algorithmic Examination,Suggestion is not specialniebie,So it is difficult to guess the question before the game,I wasn't going to fight…手痒）））