Codeforces Round 806 (Div. 4)

A - YES or YES?

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

void solve()
{
	string s;
	cin>>s;
	
	if(s=="YES"){
		cout<<"Yes"<<endl;
	}
	else {
		cout<<"NO"<<endl;
	}
	
	
}

signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

B - ICPC Balloons

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

void solve()
{
	int n;
	cin>>n;
	
	string s;
	cin>>s;
	int ans=0;
	map<char,int> mp;
	
	for (int i=0;i<(int)s.size();i++){
		if(mp[s[i]]==0){
			ans+=2;
			mp[s[i]]=1;
		}
		else {
			ans++;
		}
	}
	
	cout<<ans<<endl;
}

signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

C - Cypher

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

void solve()
{
	int n;
	cin>>n;
	
	vi a(n);
	for (int i=0;i<n;i++){
		cin>>a[i];
	}
	
	for (int i=0;i<n;i++){
		int m;
		cin>>m;
		string s;
		cin>>s;
		for (int j=0;j<m;j++){
			if(s[j]=='U'){
				if(a[i]==0){
					a[i]=9;
				}
				else {
					a[i]--;
				}
			}
			else {
				if(a[i]==9){
					a[i]=0;
				}
				else {
					a[i]++;
				}
				
			}
		}
	}
	
	for (int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	
	
	
}
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

D - Double Strings

这题数据较小遍历每个字符串暴力求解即可

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

void solve()
{
	int n;
	cin>>n;
	
	string s[n];
	vi a(n);
	map<string ,int> mp;
	for (int i=0;i<n;i++){
		cin>>s[i];
		mp[s[i]]=1;
	}
	
	for (int i=0;i<n;i++){
		string s1=s[i];
		
			
			for (int j=0;j<(int)s1.size();j++){
				string s3=s1.substr(j);
				string s2=s1.substr(0,j);
			if(mp[s2] && mp[s3]){
				a[i]=1;
			
			}
		}
	}
		
	
	for (int i=0;i<n;i++){
		cout<<a[i];
	}
	cout<<endl;
}
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

E - Mirror Grid

实际上就是让四个部分关于中心点对称。所以只要遍历四分之一区块即可，通过推导推出另外三点于这点的关系。

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

char s[110][110];

int n;
int sum=0;
void cal(int x,int y){
	int x1,x2,x3,y1,y2,y3;
	 x3=n+1-y,y3=x;
	 x1=n+1-x3,y1=n+1-y3;
	 x2=n+1-x,y2=n+1-y;
	
	int ans=0;
	if(s[x][y]=='1') ans++;
	if(s[x1][y1]=='1') ans++;
	if(s[x2][y2]=='1') ans++;
	if(s[x3][y3]=='1') ans++;
	
	sum+=min(ans,4-ans);
	
}

void solve()
{
	sum=0;

	cin>>n;
	
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cin>>s[i][j];
		}
	}
	for(int i = 1 ; i <= (n + 1) / 2 -(n%2); i ++ )
		for(int j = 1 ; j <= (n + 1) / 2 ; j ++ )
			cal(i,j);
		
	
	cout<<sum<<endl;

	
	
}
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

F - Yet Another Problem About Pairs Satisfying an Inequality

遍历一便当这个数小于这个数的下标时，就二分一下求出这个数大于的队列中的下标的数量。

并将这个下标放入队列中即可。（队列中放的都是下标）

#include "bits/stdc++.h"
using namespace std;
 
#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
 
bool cmp(pi a,pi b){
	return a.first<b.first;
}
void solve()
{
	int n;
	cin>>n;
	vi a(n+1);
	vector<int> v;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	int sum=0;
	for (int i=1;i<=n;i++){
		if(a[i]<i){
			sum+=lower_bound(v.begin(),v.end(),a[i])-v.begin();
			v.push_back(a[i]);
		}
	}
	
	cout<<sum<<endl;
	
	
	
	
}
 
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

G - Good Key, Bad Key

这题可以考虑贪心的思想。因为dp的话具有后效性。因为要上限最高，所以尽量让坏钥匙放在后面，因为不会降低上限。所以我们遍历一遍分界点，从第一个到最后一个。其中坏钥匙最多只要计算32个左右，因为数值最大为1e9 

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

#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>

int m[40];
void solve()
{
	int n,k;
	cin>>n>>k;
	int maxn=0;
	int sum=0;
	vi a(n+1);
	vi s(n+1);
	for (int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	
	for (int i=0;i<=n;i++){
		sum=s[i]-(int)i*k;
		for (int j=i+1;j<=min(i+32,n);j++){
			sum+=a[j]/m[j-i];
		}
		maxn=max(maxn,sum);
	}
	cout<<maxn<<endl;
}

signed main()
{
	m[0]=1;
	for (int i=1;i<=35;i++){
		m[i]=m[i-1]*2;
	}
	IOS
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}