Codeforces Round #767 (Div. 2)

Codeforces Round #767 (Div. 2)

A. Download More RAM

思路：

按需要内存排序，然后循环处理即可。

#include
using namespace std;
#define ll long long 
#define pb push_back
#define fi first 
#define se second
const int N=2e5+5;
const int mod=1e9+7;
pair a[N];
void solve(){
    int n,k;
    cin>>n>>k; 
    for(int i=1;i<=n;i++)cin>>a[i].fi;
    for(int i=1;i<=n;i++)cin>>a[i].se;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(a[i].fi<=k){
            k+=a[i].se;
        }else break;
    }cout<>t;
    while(t--){
        solve();
    }return 0;
}

B. GCD Arrays

思路：

发现只要存在两个相邻的数，那么gcd就肯定是1，那么最小需要去除的数量就是L->R中奇数的个数（也就是将奇数偶数，一组一组的去掉然后加入他们的乘积，那么因子中一定有2），特判当L==R且！=1的时候为YES

#include
using namespace std;
#define ll long long 
#define pb push_back
#define fi first 
#define se second
const int N=2e5+5;
const int mod=1e9+7;
pair a[N];
void solve(){
    int l,r,k;
    cin>>l>>r>>k;
    int fg=0;
    int len=r-l+1;
    if(len==1){
		if(l==1)cout<<"NOn";
		else cout<<"YESn";
		return ;
	} 
    if(len&1){
        len=len/2;
        if(l&1)len++;
        if(k>=len)fg=1;
    }else{
        if(k>=len/2)fg=1;
    }if(fg)cout<<"YESn";
    else cout<<"Non";
}
int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }return 0;
}

C. Meximum Array

思路：

按照MEX的定义来进行贪心，用cnt记录每个数出现的次数，在处理的过程中，出现cnt==0的时候要对下一个能达到的最大值取min，判断是否达到最大值，用set存比当前能达到的最大值小的数，然后判断set的size即可。

特殊的，当最大值为0的时候，要push 0

#include
using namespace std;
#define ll long long 
#define pb push_back
#define fi first 
#define se second
const int N=2e5+5;
const int mod=1e9+7;
int a[N]; 
int cnt[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cnt[i]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	}int pos;
	for(int i=0;i<=n;i++){
		if(cnt[i]==0){
			pos=i;break;
		}
	}
	int k=0;
	set s;
	vector v;
	int nextpos=pos;
	for(int i=1;i<=n;i++){
		if(pos==0){
			v.pb(0);
			continue;
		}
		if(a[i]>t;
    while(t--){
        solve();
    }return 0;
}

D. Peculiar Movie Preferences

思路：

题目中给定的n个字符串，长度为不超过3的非空字符串，那么我们需要用map2和map3来保存长度为2和3的字符串。

由于题目中是按顺序将子字符串进行组成，那么以下做法成立。

特殊的，当出现长度为1的字符串的时候就一定为YES。

当前字符串长度为2，那么我们需要判断长度为2是否存在回文的，或者长度为3的且前两个为回文，用for即可进行判断。

当前字符串长度为3，那么我们需要判断是否存在长度为2且与此字符串相组合后形成回文，或者长度为3的组成回文。

并且记得在每一个字符串要进行判断，当前字符串是否自己就回文。

#include
using namespace std;
#define ll long long 
#define pb push_back
#define fi first 
#define se second
const int N=2e5+5;
const int mod=1e9+7;
map mp2;
map mp3;
void solve(){
   int n;
   cin>>n;
   mp2.clear();
   mp3.clear();
   int fg=0;
   string p;
   for(int i=1;i<=n;i++){
       string s;
       cin>>s;
       if(fg)continue;
       if(s.size()==3){
           if(s[0]==s[2])fg=1;
           p="";p+=s[2];p+=s[1];
           if(mp2[p])fg=1;
           p="";p+=s[2];p+=s[1];p+=s[0];
           if(mp3[p])fg=1;
           mp3[s]=true;
       }if(s.size()==2){
           if(s[0]==s[1])fg=1;
           p="";p+=s[1];p+=s[0];
           if(mp2[p])fg=1;
           for(int i=0;i<26;i++){
               string q=p+(char)('a'+i);
           	   if(mp3[q])fg=1;
		   }
           mp2[s]=true;
       }if(s.size()==1)fg=1;
   }if(fg)cout<<"YESn";
   else cout<<"NOn";
}
int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }return 0;
}

E. Grid Xor

思路：

假设矩阵b即为初始的矩阵，那么对于矩阵a中的元素的值

a[i][j] = b[i-1][j] ^ b[i+1][j] ^ b[i][j-1] ^ b[i][j+1];

那么b[i+][j] = a[i][j] ^ b[i-1][j] ^ b[i][j-1] ^ b[i][j+1]

那么假设b矩阵的第一行为0，通过递推就能将b数组还原，然后分别进行异或 *** 作即可。

注意b数组的初始化。

#include
using namespace std;
#define ll long long 
#define pb push_back
#define fi first 
#define se second
const int N=1005;
const int mod=1e9+7;
int a[N][N],b[N][N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
    for(int i=1;i<=n;i++)for(int j=1;j<=n+1;j++)b[i][j]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            b[i+1][j]=a[i][j]^b[i-1][j]^b[i][j-1]^b[i][j+1];
            ans^=b[i][j];
        }
    }cout<>t;
    while(t--){
        solve();
    }return 0;
}