Round D

这次笔试题的链接。笔试题目挺有意思的，没有用到难的数据结构，都是很简单的想法。

这个题目意思很简单，给我们nn个数，让我们找出最长的连续区间，使得这个区间内的数通过异或操作得到结果之后，这个结果二进制位上为1的位置有偶数个。输出最长的区间的长度即可。

这个题目我在比赛的时候，猜对了！但是我并不知道如何证明我的算法是正确的。看了一下题解，才知道原来有这么一个有意思的性质：

• 我们称一个二进制数含偶数个1的数为：num-even
• 我们称一个二进制数含奇数个1的数为：num-odd
• num-odd和num-even做异或的话，结果是num-odd的
• num-odd和num-odd做异或的话，结果是num-even的
• num-even和num-even做异或的话，结果是num-even的

通过上面的性质的话，我们可以想到，只要一个区间含有偶数个num-odd的数，那么这个区间的结果就是num-even的。于是，如果整个序列是num-odd的话，我们只需要处理出来第一个num-odd的位置和最后一个num-odd的位置就好了，那么结果就是除去第一个num-odd的那一段和除去最后一个num-odd的两段之间的最大值即可。

#include<bits/stdc++.h>
using namespace std;
int judge(int x){
    int cnt=0;
    while(x){
        if(x&1) cnt++;
        x/=2;
    }
    return cnt&1;
}
int A[100005],D[5124];
int main(void){
    int i,j,n,m,T,now,ok,even,odd,ca=1,all;
    for(i=0;i<=5120;i++){
        D[i]=!judge(i);
    }
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n,&m);
        odd=even=all=0;
        for(i=0;i<n;i++){
            scanf("%d",A+i);
            all^=A[i];
        }
        printf("Case #%d:",ca++);
        while(m--){
            scanf("%d %d",&i,&ok);
            all^=A[i];
            A[i]=ok;
            all^=A[i];
            if (D[all]) {
                printf(" %d", n);
            }
            else {
                now=all; // 这里是暴力的，实际上可以改成set之类的加速。
                for(i=0;i<n;i++){
                    now^=A[i];
                    if(D[now]) break;
                }
                odd=all;
                for(j=n-1;j>=0;j--){
                    odd^=A[j];
                    if(D[odd]) break;
                }
                printf(" %d", max(n-i-1,j));
            }
        }
        printf("\n");
    }
}

这个题目是给我们一个圈，即n和1是相连接的，之后有些人是顺时针走的，有些人是逆时针走的，每一个节点被走过的话，会把前人的标记擦掉，只留下自己的标记，如果一个节点被多个人同时走过的话，那么会留下多个人的标记。现在给定人的位置x和顺时针走逆时针走C or A，以及走了多少步m。问最后每个人还有多少标记。

首先我们可以根据公式，顺时针的话，x+m%n的话可以得到结果，逆时针的话，x-m%n+n%n就好了。只不过需要把之前的下标都-1。通过这个的话我们可算出来最终的位置，之后最多再反向回溯一圈就好了。根据这样的想法，我们就能解出这个题目。

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

vector<int> A[100005],C[100005];
int n,m,va[100005],vc[100005],ans[100005],aid[100005],cid[100005];
void go(vector<int> x[100005],int op,int id[],int v[]){
    // end = pos+m%n ;
    int i,j,step,now,ok;
    vector<int> cur,pos;
    for(i=0;i<n;i++){
        if(x[i].size()){
            if(op==1) {
                j = (i + m) % n;
                cur.push_back(j);
                pos.push_back(i);
            }
            else {
                j = (i - m) % n;
                if (j < 0) j += n;
                cur.push_back(j);
                pos.push_back(i);
            }
        }
    }
    if(op==1){
        for(i=cur.size()-1;i>=0;i--){
            ok=0;
            if(i==0){
                j=cur[cur.size()-1];
                if(cur.size()==1) j=-1,ok=1;
            }
            else j=cur[i-1];
            now=cur[i];
            step=m;
            v[now]=step;
            id[now]=pos[i];
            for(step--;step>=0;step--){
                now--;
                if(now<0) now+=n;
                if(now==j) break;
                if(ok){
                    v[now]=max(step,v[now]);
                }
                else v[now]=step;
                id[now]=pos[i];
            }
        }
    }
    else {
        for(i=0;i<cur.size();i++){
            ok=0;
            if(i!=cur.size()-1){
                j=cur[i+1];
            }
            else{
                j=cur[0];
                if(cur.size()==1) j=n+1,ok=1;
            }
            now=cur[i];
            step=m;
            v[now]=step;
            id[now]=pos[i];
            for(step--;step>=0;step--){
                now++;
                if(now>=n) now%=n;
                if(now==j) break;
                if(ok){
                    v[now]=max(step,v[now]);
                }
                else v[now]=step;
                id[now]=pos[i];
            }
        }
    }
}
int main(void){
    int i,j,k,g,T,pos,ca=1;
    char s[10];
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&g,&m);
        for(i=0;i<=n;i++){
            A[i].clear();
            C[i].clear();
        }
        memset(ans,0, sizeof(ans));
        memset(va,-1,sizeof(va));
        memset(vc,-1,sizeof(vc));

for(i=0;i<g;i++){
            scanf("%d %s",&pos,s);
            pos-=1;
            if(s[0]=='C') {
                C[pos].push_back(i+1);
            }
            if(s[0]=='A') {
                A[pos].push_back(i+1);
            }
        }
        if(m>2*n){
            m%=n;
            m+=n;
        }
        go(C,1,cid,vc);
        go(A,-1,aid,va);
        for(i=0;i<n;i++){
            //cout<<va[i]<<"kkk"<<vc[i]<<endl;
            if(va[i]>vc[i]) {
                for(j=0;j<A[aid[i]].size();j++) {
                    ans[A[aid[i]][j]]++;
                }
            }
            else if(va[i]==vc[i]){
                if(va[i]==-1) continue ;
                for(j=0;j<A[aid[i]].size();j++) {
                    ans[A[aid[i]][j]]++;
                }
                for(j=0;j<C[cid[i]].size();j++) {
                    ans[C[cid[i]][j]]++;
                }
            }
            else {
                for(j=0;j<C[cid[i]].size();j++) {
                    ans[C[cid[i]][j]]++;
                }
            }
        }
        printf("Case #%d:",ca++);
        for(i=1;i<=g;i++){
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
}

这个题目的意思也比较有趣，在一条1e9的线段上有nn个点，我们需要选择其中的k+1k+1个位置，其中kk个门店，1个仓库。之后每个点有其所需要花费的代价，代价计算分为两个部分。

• 当前点原本的花费
• 门店到仓库的距离

之后问我们，如何选地址，才可以使得总花费最小？

首先有一个很明显的结论

• 仓库一定在所选的这些点的正中间
• 对于奇数的情况下，仓库在正中间是没什么问题的
• 偶数的时候，正中间有两个节点。这个时候仓库在这两个节点的任意一个就好了

于是我们可以分为两段考虑。

• 第一段dp[i]，表示仓库在第i个位置，左边选择了一半的门店的话，最少的花费是多少？
• 第二段DP[i]，表示仓库在第i个位置，右边选择了一半的门店的话，最少的花费是多少？

其中，我们需要用一个优先队列辅助我们如何进行计算。换句话说，我们需要固定优先队列的大小，每离开一个点，判断是不是在这个点增加门店使结果更优。

这个时候我们的评价指标就是

表示假设仓库在第nn个点，门店在第ii个点花费是什么。如果当前点的ViVi小于队列顶，那么进行替换。

为什么和第nn个进行比较也是很有讲究的，这是为了方便我们进行dp的计算，因为我们在dp的时候，从仓库在第nn个点转移到仓库到第ii个点的计算是十分简单的。

同理，我们再计算DP。那么最后的最优结果就是min(dp[i]+DP[i])min(dp[i]+DP[i])。

#include<bits/stdc++.h>
using namespace std;
long long x[100005],y[100005],dp[100005],dp2[100005];
priority_queue<long long> que;
struct node{
    long long x,y;
}A[100005];
int cmp(node A,node B){
    return A.x<B.x;
}
int main(void){
    long long i,j,n,m,T,sz,v,ca=1,ans,t;
    long long sum;
    scanf("%lld",&T);
    while(T--) {
        scanf("%lld %lld", &m, &n);
        for (i = 1; i <= n; i++) {
            scanf("%lld", &A[i].x);
        }
        for (i = 1; i <= n; i++) {
            scanf("%lld", &A[i].y);
        }
        sort(A+1,A+1+n,cmp);
        for (i = 1; i <= n; i++) {
            x[i]=A[i].x;
        }
        for (i = 1; i <= n; i++) {
            y[i]=A[i].y;
        }
        for (i = 1; i <= n; i++) {
            dp[i] = dp2[i] = -1;
        }
        sz = (m + 1 + 1) / 2;
        sum = 0;
        while (que.size()) que.pop();
        for (i = 1; i < sz; i++) {
            v = y[i] + x[n] - x[i];
            que.push(v);
            sum += v;
        }
        for (i = sz; i <= n; i++) {
            v = y[i] + x[n] - x[i];
            dp[i] = sum + v - (x[n] - x[i]) * sz;
            if (que.size() && que.top() > v) {
                t = que.top();
                sum -= t;
                que.pop();
                que.push(v);
                sum += v;
            }
        }
        sz = m + 1 - sz;
        sum = 0;
        while (que.size()) que.pop();
        for (i = 0; i < sz; i++) {
            v = y[n - i] + x[n - i] - x[1];
            que.push(v);
            sum += v;
        }
        for (i = sz; i < n; i++) {
            v = y[n - i] + x[n - i] - x[1];
            dp2[n - i] = sum - (x[n - i] - x[1]) * sz;
            if (que.size() && que.top() > v) {
                t = que.top();
                sum -= t;
                que.pop();
                que.push(v);
                sum += v;
            }
        }
        ans = 2e18;
        for (i = 1; i <= n; i++) {
            if (dp[i] == -1) continue;
            if (dp2[i] == -1) continue;
            ans = min(ans, dp[i] + dp2[i]);
        }
        printf("Case #%lld: %lld\n", ca++, ans);
    }
}