Codeforces Round 900 (Div. 3)

题目

A.

只要k出现过就是YES

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e5+10;
#define inf 0x3f3f3f3f

void solve() {
    int n,k;cin>>n>>k;
    map<int,int>mp;
    for(int i=0,x;i<n;i++){
        cin>>x;
        mp[x]++;
    }
    if(mp[k])cout<<"YES\n";
    else cout<<"NO\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

B.

暴力即可，先一直在想规律，一直想不出来

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+10;
#define inf 0x3f3f3f3f

int dp[N];
void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cout<<dp[i]<<' ';
    cout<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    dp[1]=10;dp[2]=11;
    for(int i=3;i<N;i++){
        for(int j=dp[i-1]+1;;j++){
            if((j*3)%(dp[i-1]+dp[i-2])!=0){
                dp[i]=j;
                break;
            }
        }
    }
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

C.

判x在最小k个数和最大k个数之间即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+10;
#define inf 0x3f3f3f3f

void solve() {
    int n,k,x;cin>>n>>k>>x;
    int pre=k*(k+1)/2,pos=0;
    int l=n-k+1;
    pos=(l+n)*(k/2);
    if(k%2)pos+=n-k/2;
    if(pre<=x&&pos>=x)cout<<"YES\n";
    else cout<<"NO\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

D.

暴力会超时
一个很重要的点是注意到它在每个区间内翻转是对称翻转的
也就是翻转的对象唯一
也就是这个点处于奇数个翻转区间，那么最终结果是翻转对象，
处于偶数个翻转区间，最终结果不变
用了个线段树处理

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+10;
#define inf 0x3f3f3f3f

struct SegmentTree{
    int l,r;//标号i的元素所表示的区间左右端点
    int dat;//根据需要可改变，这里是区间求和
    int add;//懒标记
}segment_tree[N*4];//开4倍空间
void build(int p,int l,int r){//建树
    segment_tree[p].l=l;segment_tree[p].r=r;
    if(l==r){
        // segment_tree[p].dat=a[l];
        //区间长度为1，这里可进行初始化
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    segment_tree[p].dat=segment_tree[p*2].dat+segment_tree[p*2+1].dat;
    //求和
}
//调用入口：build(1,1,n); 编号从1开始，区间为1-n
void change(int p,int x,int v){//单点修改,p是当前编号，x是要修改的编号，v是修改的值
    if(segment_tree[p].l==segment_tree[p].r){
        segment_tree[p].dat=v;//修改
        return ;
    }
    int mid=(segment_tree[p].l+segment_tree[p].r)/2;
    if(x<=mid)change(p*2,x,v);
    else change(p*2+1,x,v);
    segment_tree[p].dat=segment_tree[p*2].dat+segment_tree[p*2+1].dat;
}
//调用入口：change(1,x,v);

//调用入口：ask(1,l,r);
void spread(int p){//用懒标记
    if(segment_tree[p].add){//该懒标记还未用
        segment_tree[p*2].dat+=segment_tree[p].add*(segment_tree[p*2].r-segment_tree[p*2].l+1);
        segment_tree[p*2+1].dat+=segment_tree[p].add*(segment_tree[p*2+1].r-segment_tree[p*2+1].l+1);
        //给左右子节点打懒标记
        segment_tree[p*2].add+=segment_tree[p].add;
        segment_tree[p*2+1].add+=segment_tree[p].add;
        segment_tree[p].add=0;//清除p的懒标记
    }
}
void segment_change(int p,int l,int r,int d){//区间修改
    if(l<=segment_tree[p].l&&segment_tree[p].r<=r){
        segment_tree[p].dat+=d*(segment_tree[p].r-segment_tree[p].l+1);
        segment_tree[p].add+=d;//打标记
        return ;
    }
    spread(p);//下放标记
    int mid=(segment_tree[p].l+segment_tree[p].r)/2;
    if(l<=mid)segment_change(p*2,l,r,d);
    if(r>mid)segment_change(p*2+1,l,r,d);
    segment_tree[p].dat=segment_tree[p*2].dat+segment_tree[p*2+1].dat;
}
//调用入口：change(1,l,r,d);将区间l-r加d
//调用入口：ask(1,l,r);获取l-r的和
int ask(int p,int l,int r){//区间查询
    if(l<=segment_tree[p].l&&segment_tree[p].r<=r){
        return segment_tree[p].dat;
    }
    spread(p);//若用懒标记，则取消注释
    int mid=(segment_tree[p].l+segment_tree[p].r)/2;
    int sum=0;
    if(l<=mid)sum+=ask(p*2,l,r);
    if(r>mid)sum+=ask(p*2+1,l,r);
    return sum;
}
void solve() {
    int n,k;cin>>n>>k;
    build(1,1,n);
    vector<pair<int,int>>v(k+1);
    string s;cin>>s;s=" "+s;
    map<int,int>mp;
    for(int i=1;i<=k;i++)cin>>v[i].first;
    for(int i=1;i<=k;i++){
        cin>>v[i].second;
        mp[v[i].second]=i;
    }

    int q;cin>>q;
    vector<int>x(q+1);
    for(int i=1;i<=q;i++)cin>>x[i];
    sort(x.begin()+1,x.begin()+1+q);
    for(int i=1;i<=q;i++){
        auto it=mp.lower_bound(x[i]);
        int p=it->second;
        int l=v[p].first,r=v[p].second;
        int st=min(x[i],l+r-x[i]),en=max(x[i],l+r-x[i]);
        //cout<<"st="<<st<<' '<<"en="<<en<<'\n';
        segment_change(1,st,en,1);
    }
    for(int i=1;i<=k;i++){
        int l=v[i].first,r=v[i].second;
        for(int j=l;j<=r;j++){
            int cnt=ask(1,j,j);
            //if(cnt&1)cout<<"r-j+1="<<r-j+1<<'\n';
          //  else cout<<j<<'\n';
            if(cnt&1)cout<<s[l-1+r-j+1];
            else cout<<s[j];
     //       cout<<"cnt="<<cnt<<'\n';
        }
    }
    cout<<'\n';
    for(int i=1;i<=n*4;i++){
        segment_tree[i].l=0;
        segment_tree[i].r=0;
        segment_tree[i].dat=0;
        segment_tree[i].add=0;

    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}

E.

无脑线段树做了，直接求区间与+二分

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+10;
#define inf 0x3f3f3f3f

vector<int>a(N);
struct SegmentTree{
    int l,r;//标号i的元素所表示的区间左右端点
    int dat;//根据需要可改变，这里是区间求和
    int add;//懒标记
}segment_tree[N*4];//开4倍空间
void build(int p,int l,int r){//建树
    segment_tree[p].l=l;segment_tree[p].r=r;
    if(l==r){
         segment_tree[p].dat=a[l];
         //cout<<a[l]<<'\n';
        //区间长度为1，这里可进行初始化
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    segment_tree[p].dat=segment_tree[p*2].dat&segment_tree[p*2+1].dat;
    //cout<<"p*2="<<segment_tree[p*2].dat<<' '<<"p*2+1="<<segment_tree[p*2+1].dat<<' '<<segment_tree[p].dat<<'\n';
    //求和
}
//调用入口：build(1,1,n); 编号从1开始，区间为1-
//调用入口：change(1,x,v);
int ask(int p,int l,int r){//区间查询
    if(l<=segment_tree[p].l&&segment_tree[p].r<=r){
        return segment_tree[p].dat;
    }
    //spread(p);//若用懒标记，则取消注释
    int mid=(segment_tree[p].l+segment_tree[p].r)/2;
    int sum_1=-1,sum_2=-1;
    if(l<=mid)sum_1=ask(p*2,l,r);
    if(r>mid)sum_2=ask(p*2+1,l,r);
    //cout<<"sum_1="<<sum_1<<' '<<"sum_2="<<sum_2<<'\n';

    //cout<<"Sum="<<sum<<'\n';
    if(sum_1==-1)return sum_2;
    if(sum_2==-1)return sum_1;
    return (sum_2&sum_1);
}
//调用入口：change(1,l,r,d);将区间l-r加d
//调用入口：ask(1,l,r);获取l-r的和

void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    int q;cin>>q;
    while(q--){
        int st,k;cin>>st>>k;
        int l=st,r=n,mid;
        int ans=-1;
        while(l<=r){
            mid=(l+r)/2;
            //cout<<"st="<<st<<' '<<"mid="<<mid<<'\n';
            //cout<<"tmp="<<ask(1,st,mid)<<'\n';
            if(ask(1,st,mid)>=k){
                //cout<<"mid="<<mid<<' '<<"st-1="<<st-1<<'\n';
                //cout<<"tmp="<<(pre_yu[mid]|pre_huo[st-1])<<'\n';
                l=mid+1;
                ans=max(ans,mid);
            }
            else r=mid-1;
        }
        cout<<ans<<' ';
    }
    cout<<'\n';

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int left=1;
    cin>>left;
    while(left--){
        solve();
    }
}