2023牛客暑假多校2

K

定义 $dp[n][0/1/2]$ 表示第 $n$ 个盖子左移/不动/右移时的最大分数。

容易 $O(n)$ 转移。

代码

#include<bits/stdc++.h>
#define N 1000010
#define ll long long 

using namespace std;

int n;
ll a[N],b[N],dp[N][3];
vector<int> pos;
void work() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) {
        cin>>b[i];
        if(b[i]) pos.push_back(i);
    }
    int t=pos.size();
    if(n==1) {
        if(t) cout<<a[1]<<endl;
        else cout<<0<<endl;
    }
    else if(t==0) {
        cout<<0<<endl;
    }
    else {
        if(pos[0]==1) {
            dp[0][0]=0,dp[0][1]=a[pos[0]],dp[0][2]=a[pos[0]+1];
        }
        else if(pos[0]==n) {
            dp[0][0]=a[pos[0]-1],dp[0][1]=a[pos[0]],dp[0][2]=0;
        }
        else {
            dp[0][0]=a[pos[0]-1],dp[0][1]=a[pos[0]],dp[0][2]=a[pos[0]+1];
        }
        if(t==1) cout<<max(dp[0][0],max(dp[0][1],dp[0][2]))<<endl;
        else {
            for(int i=1;i<t;i++) {
                if(pos[i]-pos[i-1]==1) {
                    dp[i][0]=dp[i-1][0]+a[pos[i]-1];
                    dp[i][1]=max(dp[i-1][0],dp[i-1][1])+a[pos[i]];
                    dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]+1];
                }
                else if(pos[i]-pos[i-1]==2) {
                    dp[i][0]=max(dp[i-1][0],dp[i-1][1])+a[pos[i]-1];
                    dp[i][1]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]];
                    dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]+1];
                }
                else {
                    dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]-1];
                    dp[i][1]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]];
                    dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]))+a[pos[i]+1];
                }
            }
            cout<<max(dp[t-1][0],max(dp[t-1][1],dp[t-1][2]))<<endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}

---

H

发现，异或操作相当于 $x\gets S-x$ , 其中 $S=2^{len}-1$ 。

加一操作就是加一。

维护一个类似于前缀和的东西即可 $O(1)$ 求出每个询问。

详见代码。

代码

#include<bits/stdc++.h>
#define N 400010
#define ll long long 

using namespace std;

int n,q;
ll ans=0;
char s[N];
ll MAXN=(1ll<<51ll)-1ll,val[N],cnt[N];
ll calc(string x) {
    ll res=0;
    int t=x.size();
    for(int i=0;i<t;i++) res=(res<<1)+x[i]-'0';
    return res;
}
void printp(string x,ll y) {
    stack<int> stk;
    int t=x.size();
    ll res=0;
    for(int i=1;i<=t;i++) {
        stk.push(y&1);
        res+=((y&1)<<(i-1));
        y>>=1;
    }
    ans=res;
    for(int i=1;i<=t;i++) {
        if(stk.size()) cout<<stk.top();
        if(stk.size()) stk.pop();
    }
    cout<<endl;
}
void work() {
    cin>>n>>q;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) val[i]=cnt[i]=0;
    for(int i=1;i<=n;i++) {
        if(s[i]=='A') val[i]=val[i-1]*(-1),cnt[i]=1;
        else val[i]=val[i-1]+1,cnt[i]=0;
    }
    for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
    for(int i=1;i<=q;i++) {
        int l,r,L,R;
        string x;
        cin>>l>>r>>x;
        L=min((ans^l)%n+1,(ans^r)%n+1);
        R=max((ans^l)%n+1,(ans^r)%n+1);
        ll c=cnt[R]-cnt[L-1];
        ll v=val[R];
        if(c&1) v+=val[L-1];
        else v-=val[L-1];
        if(c&1) {
            ll tmp=calc(x);
            tmp=MAXN-tmp+v;
            printp(x,tmp);
        }
        else {
            ll tmp=calc(x);
            tmp=tmp+v;
            printp(x,tmp);
        }
    }
}

int main() {
    work();
    return 0;
}

---

D

贪心题。

根据喜好程度，倒着选。

#include<bits/stdc++.h>
#define N 2010

using namespace std;

int T;

int n,m,k,pos[N];
bool cmp(pair<int,int> a,pair<int,int> b) {
    return a.second>b.second;
}
vector<pair<int,int> > a[N];
bool vh[N];
vector<int> ans;

void work() {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            int val;
            cin>>val;
            a[i].push_back(make_pair(j,val));
        }
    }
    for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end(),cmp);
    int now=k%n,cnt=1;
    while(cnt<=k) {
        if(!now) now=n;
        while(vh[a[now][pos[now]].first]) pos[now]++;
        vh[a[now][pos[now]].first]=true;
        ans.push_back(a[now][pos[now]].first);
        cnt++;
        now--;
    }
    sort(ans.begin(),ans.end());
    for(int i:ans) cout<<i<<" ";
    cout<<endl;
    ans.clear();
    for(int i=1;i<=n;i++) {
        a[i].clear();
        pos[i]=0;
    }
    for(int i=1;i<=m;i++) vh[i]=false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) work();
    return 0;
}