Codeforces Round 900 (Div. 3)

Problem - A - Codeforces

AC代码:

#include
#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"<
    else cout<<"No"<
}
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
#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<' ';
    cout<
}
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
#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"<
    else cout<<"No"<
}
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
#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;
    vectorint>>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<
}
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
#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
        for(int i=1;i+(1<-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(nowreturn -1;
    for(int i=17;i>=0;i--){
        if(r+(1<1&&(now&f[r][i])>=k){
            now&=f[r][i];
            r+=(1<
        }
    }
    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<
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}