Problem - A - Codeforces

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k;
void solve(){cin>>n>>k;bool ok=false;for(int i=1;i<=n;i++){int x;cin>>x;if(x==k) ok=true;}if(ok) cout<<"Yes"<<endl;else cout<<"No"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - B - Codeforces

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std; 
const int N=2e5+10;
int a[N];
int n;
void solve(){cin>>n;a[1]=1;a[2]=3;for(int i=3;i<=n;i++){int cnt=a[i-1]+1;while((3*cnt)%(a[i-1]+a[i-2])==0) cnt++;a[i]=cnt;}for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - C - Codeforces

首先我们能确定的是如果要Yes，一定得刚好取k个数，这是不变的，我们取最小的k个数和最大的k个数，如果x在这之间，那么一定能够取k个数和刚好为x

比如一共5个数，取3个,最小的1 2 3和为6，最大的3 4 5和为12，1 2 4和为7，1 3 4和为8，1 3 5和为9，2 3 5和为10，2 4 5和为11

每次取k个数都可以确保和多一个1，所以中间的数全部能取到，是连续的

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,k,x;
void solve() {cin>>n>>k>>x;int minn=(1+k)*k/2;int maxn=(1+n)*n/2-(1+n-k)*(n-k)/2;if(x>=minn&&x<=maxn) cout<<"Yes"<<endl;else cout<<"No"<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - D - Codeforces

参考Codeforces Round 900 (Div. 3) 题解 | JorbanS_JorbanS的博客-CSDN博客

任何一个区间[l[i],r[i]]都是独立的，互不重叠

如果暴力枚举每一个x所确定的区间[l[id],r[id]]，一定会超时，那么我们就去寻求某种特殊的性质

对于一个x，它所确定的区间所在的区间[l[id],r[id]]是唯一的，且对称轴是所在区间[l[id],r[id]]的对称轴

通过二分来确定区间在哪个区间[l[id],r[id]]，然后对于区间[l[id],r[id]]左半边的点，记录其翻转次数，通过差分数组来记录，再求前缀和得到，如果翻转次数为奇数，那么就换

每个区间都是独立操作，进行差分和前缀和

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int N=2e5+10;
int l[N],r[N];
int a[N];
int sum[N];
int n,k;
string s;
void solve() {cin>>n>>k;vector<vector<int>>e(n+1);cin>>s;for(int i=1;i<=n;i++) a[i]=sum[i]=0;for(int i=1;i<=k;i++) cin>>l[i];for(int i=1;i<=k;i++) cin>>r[i];int q;cin>>q;while(q--){int x;cin>>x;int id=lower_bound(r+1,r+1+k,x)-r;//第id个区间push_back区间左端点if(x<=(l[id]+r[id])/2) e[id].push_back(x);else e[id].push_back(l[id]+r[id]-x);}for(int i=1;i<=k;i++){a[l[i]]=0;sum[l[i]-1]=0;for(auto v:e[i]){int p=v,q=l[i]+r[i]-p;a[p]++,a[q+1]--;}for(int j=l[i];j<=(l[i]+r[i])/2;j++) sum[j]=sum[j-1]+a[j];for(int j=l[i];j<=(l[i]+r[i])/2;j++){if(sum[j]%2==1) swap(s[j-1],s[l[i]+r[i]-j-1]);}}cout<<s<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

Problem - E - Codeforces

ST表(RMQ)

以倍增的思想预处理以每个点为起点,2^0,2^1,...2^17为区间长度的区间相与

相与，不会变大，只会变小，具有单调性

然后对于起点l，进行贪心，从最大的区间开始枚举，如果相与大于等于k，则选用

AC代码:

#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int N=2e5+10,M=18;
int a[N];
int f[N][M];
int n;
void init(){for(int j=0;j<M;j++){for(int i=1;i+(1<<j)-1<=n;i++){if(!j) f[i][j]=a[i];else f[i][j]=f[i][j-1]&f[i+(1<<(j-1))][j-1];}}
}
int query(int l,int k){int r=l;int now=f[l][0];if(now<k) return -1;for(int i=17;i>=0;i--){if(r+(1<<i)<=n+1&&(now&f[r][i])>=k){now&=f[r][i];r+=(1<<i);}}return r-1;
}
void solve() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i];init();int q;cin>>q;while(q--){int l,k;cin>>l>>k;cout<<query(l,k)<<' ';}cout<<endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}