Codeforces Round 984 (Div. 3) （A~E）

https://codeforces.com/contest/2036

A. Quintomania

思路

签到题，直接模拟即可

code

void solve(){
	int n;cin >> n;
	for(int i=1;i<=n;++i) cin >> a[i];
	for(int i=2;i<=n;++i){
		if(abs(a[i]-a[i-1])==5 || abs(a[i]-a[i-1])==7)
		continue;
		else{
			cout << "NO" << endl;
			return ;
		}
	} 
	cout << "YES" << endl;
	return ;
}

B. Startup

思路

考点：排序

用桶标记的思维将k个数存入到数组中，再将数组进行降序排序，最后取前n个数即可

code

const int N=1e6+5;
int a[N];
void solve(){
	int n,k;
	cin >> n >> k;
	int ans=0,mx=0;
	int s=max(n,k);
	for(int i=1;i<=s;++i) a[i]=0;
	for(int i=1;i<=k;++i){
		int x,y;
		cin >> x >> y;
		a[x]+=y;
	}
	sort(a+1,a+1+k,greater<int>());
	for(int i=1;i<=n;++i) ans+=a[i];
	cout << ans << endl;
	return ;
}

C. Anya and 1100

思路

考点：模拟

先统计字符串中"1100"的个数，对于q次询问，每次改变1个字符，通过观察不难发现：
改变的这一个字符只影响它前面3个字符和后面3个字符，因此我们只需要暴力循环这7个字符即可
先不替换这个字符，减去这7个位置的"1100"的个数
替换这个字符，加上这7个位置的"1100"的个数
判断 $cnt$ 个数是否大于0，满足输出YES
反之输出NO

code

void solve(){
	string s;cin >> s;
	int q;cin >> q;
	int cnt=0,n=s.size();
	for(int i=0;i<=n-4;++i){
		if(s[i]=='1' && s[i+1]=='1' && s[i+2]=='0' && s[i+3]=='0')
		cnt++;
	}
	while(q--){
		int x;
		char v;
		cin >> x >> v;
		x--;
		for(int i=max(0ll,x-4+1);i<=x;++i){
			if(s[i]=='1' && s[i+1]=='1' && s[i+2]=='0' && s[i+3]=='0')
		    cnt--;
		}
		s[x]=v;
		for(int i=max(0ll,x-4+1);i<=x;++i){
			if(s[i]=='1' && s[i+1]=='1' && s[i+2]=='0' && s[i+3]=='0')
		    cnt++;
		}
		if(cnt>0) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return ;
}

D. I Love 1543

思路

考点：模拟

对于每一个外层，我们将这些数存入到数组中
注意：需要多存入3个数，例如：

5 4
1 3

假设我们从5开始读取，那么数组包含的数为 5 4 3 1 ，显然数组中并没有连续的1543
可是对于这个样例来说，它是有1个连续的1543
观察数组，这个1在数组的末位
显然我们还需要在这个数组中多添加3个数，因此最终的数组为 5 4 3 1 5 4 3

统计数组中连续的1543，最后输出即可

code

const int N=1e3+5;
char a[N][N];
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;++i)
	   for(int j=1;j<=m;++j){
	   	cin >> a[i][j];
	   }
	int ans=0;
	int t=min(n,m);
	t/=2;
	int l=1;
	while(t--){
		vector<char> v;
		for(int i=l;i<=m;++i) v.push_back(a[l][i]);
		for(int i=l+1;i<=n;++i) v.push_back(a[i][m]);
		for(int i=m-1;i>=l;--i) v.push_back(a[n][i]);
		for(int i=n-1;i>l;--i) v.push_back(a[i][l]);
		int k=3;
		for(int i=l;i<=m;++i){
			if(k){
			v.push_back(a[l][i]);
			k--;
			}
			else break;
		}
		for(int i=l+1;i<=n;++i){
			if(k){
				v.push_back(a[i][m]);
				k--;
			}
			else break;
		} 
		for(int i=m-1;i>=l;--i){
			if(k){
				v.push_back(a[n][i]);
				k--;
			}
			else break;
		}
//		for(auto i : v) cout << i << " "; 
//		cout << endl;
		for(int i=0;i<=v.size()-4;++i){
			if(v[i]=='1'){
				if(v[i+1]=='5' && v[i+2]=='4' && v[i+3]=='3') ans++;
			}
		}
		l++,m--,n--;
	}
	cout << ans << endl;
	return ;
}

E. Reverse the Rivers

思路

考点：二分

首先预处理 $a[i][j]|=a[i-1][j]$
然后将n行k列转换为k行n列，即 $b[j][i]=a[i][j];$
对于q次询问，首先定义左右边界，即 $l=1,r=n$
对于m次询问：

• 如果o为 $<$ ，我们可以用lower_bound函数在 $b[k]$ 中找出大于等于 $c$ 的第一个值的下标
  那么这个下标(包过这个下标)之后的值都不在我们要找的范围中
  将这个下标赋值给x， $r=x-1$ ,同小取小，我们要找最小的下标，那么 $r=min(r,x-1)$
• 反之，我们可以用upper_bound函数在 $b[k]$ 中找出大于 $c$ 的第一个值的下标
  那么这个下标之前的值都不在我们要找的范围中
  将这个下标赋值给x， $l=x$ ,同大取大，我们要找最大的下标，那么 $l=max(l,x)$

最后判断如果 $l<=r$ ，输出左边界 $l$
反之输出 $-1$

code

void solve(){
	int n,k,q;
	cin >> n >> k >> q;
	vector<vector<int>>a(n+1,vector<int>(k+1)); 
	vector<vector<int>>b(k+1,vector<int>(n+1)); 
	for(int i=1;i<=n;++i)
	   for(int j=1;j<=k;++j){
	   	cin >> a[i][j];
	   	a[i][j]|=a[i-1][j];
	   	b[j][i]=a[i][j];
	   }
	while(q--){
		int m;cin >> m;
		int l=1,r=n;
		while(m--){
			int k,c;
			char o;
			cin >> k >> o >> c;
			if(o=='<'){
				int x=lower_bound(b[k].begin()+1,b[k].end(),c)-b[k].begin();
				x--;
				r=min(r,x);
			}
			else{
				int x=upper_bound(b[k].begin()+1,b[k].end(),c)-b[k].begin();
				l=max(l,x);
			}
		}
		if(l<=r) cout << l << endl;
		else cout << -1 << endl;
	}
	return ;
}