Codeforces Round #767 (Div. 2) A~E

Codeforces Round #767 (Div. 2) A~E Codeforces Round #767 (Div. 2) A~E A Download More RAM

大意是你一开始有 m G内存,每次你可以使用不超过你内存的RAM来升级你的内存，第i个扩充内存b[i].

思路：

直接贪心即可，每次都选最小的来升级。

void solve(){
	n=read();m=read();
	rep(i,1,n) a[i].x=read(),a[i].y=i;
	rep(i,1,n) b[i]=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		if(m>=a[i].x) m+=b[a[i].y];
	print(m);
}

B. GCD Arrays

大意是给你一段连续的[l,r]之内的数，每次可以选择两个数丢掉并把他们的乘积加进来，问k次 *** 作以内是否可以把整个序列的gcd大于1

思路：

我们可以直接想到让区间内的所有数获得因子2是 *** 作最少的，因此把所有奇数 *** 作掉即可。因此判断[l,r]中的奇数数量是否小于等于k,注意l=r=1的时候要特判

void solve(){
	l=read(),r=read(),k=read();
	LL num=(r-l)/2+(((l%2)==0)||(r%2==0));
	num=r-l+1-num;
	if(l==1&&r==1){
		puts("NO");
		return ;
	}
	if(l==r&&l!=1) {
		puts("YES");
		return ;
	}
	if(k>=num) puts("YES");
	else puts("NO");
}

C. Meximum Array

大意是给你一个序列，你可以任意分割序列使得得到的每一段序列的mex值按顺序组成新序列字典序最大

思路：

容易想到，需要贪心的让第一端mex最大，然后在剩下的让第二段mex最大…因此我们可以利用双指针直接模拟，用两个辅助数组，一个记录哪些数出现过，另一个记录每个数出现了多少次。前面的指针每次找到当前端mex-1第一次出现的位置，然后记录答案，后面的指针删去这一段的次数。

const int N = 200010, tot=200000;
int n,cnt[N],a[N],num[N];
vector ans;
int mex=0,last=0,mx=0;

void solve(){
	mex=mx=0; ans.clear();
	n=read();
	rep(i,1,n) a[i]=read(),mx=max(mx,a[i]),num[a[i]]++;	
	last=1;
	for(int i=1;i<=n;++i){
		cnt[a[i]]++;
		while(cnt[mex]) mex++;
		if(!num[mex]){
			ans.push_back(mex);
			for(int j=last;j<=i;++j) num[a[j]]-=cnt[a[j]],cnt[a[j]]=0;
			mex=0;
			last=i+1;
		}
	}
	print(ans.size());
	for(auto u:ans) printf("%d ",u); puts("");
	rep(i,0,mx) num[i]=0,cnt[i]=0;
}

[D. Peculiar Movie Preferences](D. Peculiar Movie Preferences)

大意是给你一些长度不超过3的字符串，问在保留原有顺序的情况下是否可以选择一些字符串（不可以不选）拼接成回文串

思路：

最终是回文串一共只有五种情况。

存在单个字符或者本身回文的字符串长度2+长度2拼接成回文串长度2+长度3拼接成回文串长度3+长度2拼接成回文串长度3+长度3拼接成回文串

由于长度很短，因此我们可以不用哈希，直接开数组存储即可。

#define int LL
const int N=200010,M=27;
int n,m,k;
string str[N];
int t1[M],t2[M][M],t3[M][M][M];

int get(char ch){
	return ch-'a'+1;
}

void solve(){	
	memset(t1,0,sizeof t1);
	memset(t2,0,sizeof t2);
	memset(t3,0,sizeof t3);
	
	cin >> n;
	rep(i,1,n) cin >> str[i];
	bool ok=false;
	
	rep(i,1,n){
		if(str[i].size()==1){ //1
			ok=true;
			break;
		}
		else if(str[i].size()==2){//2+2 2+3
			t2[get(str[i][0])][get(str[i][1])]++;
			if(str[i][0]==str[i][1]) {
				ok=true;
				break;
			}
		}
		else{//3,3+3,3+2
			t3[get(str[i][0])][get(str[i][1])][get(str[i][2])]++;
		}
	}
	
	if(ok){
		puts("YES");
		return ;
	}
	
	for(int i=1;i<=n;++i){
		if(str[i].size()==1) continue;
		else if(str[i].size()==2){
			//2+2
			if(t2[get(str[i][1])][get(str[i][0])]) {
				ok=true;
				break;
			}
			//2+3
			for(int j=1;j<=26;++j) {
				if(ok) break;
				if(t3[j][get(str[i][1])][get(str[i][0])]){
					ok=true;
					break;
				}
			}
		}
		else{
			//3+3
			if(t3[get(str[i][2])][get(str[i][1])][get(str[i][0])]){
				ok=true;
				break;
			}
			//3+2
			if(t2[get(str[i][1])][get(str[i][0])]){
				ok=true;
				break;
			}
		}
		
		if(str[i].size()==2) t2[get(str[i][0])][get(str[i][1])]--;
		else if(str[i].size()==3) t3[get(str[i][0])][get(str[i][1])][get(str[i][2])]--;
	}
	
	puts(ok?"YES":"NO");
}

E. Grid Xor

大意是给你一个边长为偶数的正方形方格，只告诉你每个方格其所有相邻方格的异或和，求整个方形的全部元素异或和。

思路：

我们通过模拟4*4的发现一定是两个两个选的，且不能选会覆盖之前已经选了的区域。根据题目中

可以证明解一定唯一，我们得知解一定存在，又由于是正方形，因此我们一行一行的选取格子并将其覆盖区域染色，时刻保证

前面的空格不被遗漏后面新选取的格子覆盖的区域与之前无重叠

因为有重叠了等于没染，此时又要新的格子来染被消除的，会导致新的格子被消除。

const int N = 1010;
int n,a[N][N],g[N][N],mov[4][2]={1,0,0,1,-1,0,0,-1};
LL ans=0;

void solve(){
	memset(g,0,sizeof g);
	ans=0;
	n=read();
	rep(i,1,n) rep(j,1,n) a[i][j]=read();
	rep(i,1,n) rep(j,1,n){
		bool flag=true;
		rep(k,0,3){  //先判断四周有没有被覆盖到
			int x=i+mov[k][0], y=j+mov[k][1];
			if(g[x][y]) flag=false;
		}
		if(flag){ //如果没有被覆盖到，则选择
			ans^=a[i][j];
			rep(k,0,3){  //先判断四周有没有被覆盖到
				int x=i+mov[k][0], y=j+mov[k][1];
				g[x][y] ++;
			}
		}
	}
	print(ans);
}