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 ;
}