https://codeforces.com/contest/1941
训练情况
50min后罚坐
反思
C题刚开始思路错了，以为是删字符串最后面，然后漏考虑掉两字符串部分拼接的情况
A题
直接模拟，求 \(a_i + b_j \le k\) 的对数。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n,m,k; cin>>n>>m>>k;
vector<int> a(n + 1);
vector<int> b(m + 1);
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=m;i++) cin>>b[i];
int ans = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(a[i] + b[j] <= k) ans++;
}
}
cout<<ans<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
B题
我们考虑倒着思考，如果数组能最后删成全零，那它一定是由若干个 \([1,2,1]\) 这样子加起来的，所以我们就可以从左往右贪心，能删掉的尽量删掉，如果最后剩下的数不是 \(0\)，答案就是 NO，否则就是 YES。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin>>n;
vector<int> a(n + 3);
for(int i = 1;i<=n;i++) cin>>a[i];
for(int i = 1;i<=n;i++){
if(a[i] > 1){
int mi = min(a[i - 1],a[i + 1]);
a[i-1] -= mi;
a[i+1] -= mi;
a[i] -= mi*2;
}
}
bool flag = true;
for(int i = 1;i<=n;i++) if(a[i]) flag = false;
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
C题
我们发现想让子串 pie 和 map 消失，我们肯定考虑要删中间的那个字符，比如 ppppieeee 这种，显然只能删中间的字符，删头尾的两个字符反而操作次数更多，所以对于每个 pie 或 map 只需要操作一次，把中间的字符删掉，然后我们只需要统计 pie 和 map 子串出现的次数即可，注意一下子串匹配到了指针要往下跳
hack数据
mapie
答案是 \(1\)，删掉 p 即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin>>n;
string s; cin>>s;
int ans = 0;
for(int i = 0;i<n - 2;i++){
string ss = s.substr(i,3);
if(ss == "map" || ss == "pie") ans++,i+=2;
}
cout<<ans<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}
D题
我们发现最后要输出可能的人数，并且人的编号要单调递增，容易想到使用 set 集合来维护，所以我们只要一轮一轮的维护，每一轮将上一轮可能接到球的人取出来模拟即可，如果为 ? 则顺时针和逆时针都跑一遍，注意一下顺时针和逆时针的环，减一取模加一即可。
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n,m,x; cin>>n>>m>>x;
set<int> ans;
ans.insert(x);
for(int i = 1;i<=m;i++){
set<int> se;
int c; string s;
cin>>c>>s;
if(s == "0") for(auto j:ans) se.insert((j+c-1)%n+1);
else if(s == "1") for(auto j:ans) se.insert((n+j-c-1)%n+1);
else if(s == "?"){
for(auto j:ans) se.insert((j+c-1)%n+1);
for(auto j:ans) se.insert((n+j-c-1)%n+1);
}
ans = se;
}
cout<<ans.size()<<endl;
for(auto i:ans) cout<<i<<" ";
cout<<endl;
}
signed main(){
int T; cin>>T; while(T--)
solve();
return 0;
}