Educational Codeforces Round 157 (Rated for Div. 2)-526互联

$D. XOR Construction$

首先观察 $ b_1 \oplus b_2=a_1, b_2 \oplus b_3=a_2 \ldots $ ，发现 $b_1 \oplus b_{j+1}=\bigoplus^{j}_{i=1}a_i$ ，那么自然的想到如果第一个数字确定，后面的数字都可以依次得到，那么我们就需要枚举 $b_1$ ，为了加速递推的过程采用字典树优化，总复杂度 $O(nlog2e5)$。

int son[N][2];
int idx;
void insert(int x){
    int p = 0;
    for (int i = 30; i >= 0; i--){ // 从最高位开始存
        int u = (x >> i) & 1;
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x){
    int p = 0;
    int res = 0; // res用来还原这条路径上的数
    for (int i = 30; i >= 0; i--){
        int u = (x >> i) & 1;
        if (son[p][!u]) { // 如果有相反的二进制位可以走
            p = son[p][!u];
            res |= (1<<i);
        }
        else { // 如果没有相反的可以走
            p = son[p][u];
        }
    }
    return res;
}
void solve(){
    int n=read();
    insert(0);
    vector<int>a(n+1);
    for(int i=1;i<n;i++){
        a[i]=(a[i-1]^read());
        insert(a[i]);
    }
    int re=inf,b1=-1;
    for(int i=0;i<n;i++){
        if(re>(query(i))){
            b1=i;
            re=(query(i));
        }
    }
    cout<<b1<<' ';
    for(int i=1;i<n;i++){
        int res=b1^a[i];
        cout<<res<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

$E. Infinite Card Game$

容易的想到对面一定会打出$b_{xi}>a_{yj}$ 且 $b_{yi}$ 尽量大的牌。如果我们按照 $b_{xi}$ 排序，那么每次就是取后缀中的 $max$ 。手玩一下发现区间会不断减小，是一个递归过程。所以我们模拟递归过程。具体实现是将双方的牌按照攻击力排序然后预处理后缀防御力最大值，每次二分寻找到后缀防御力最大值。如果不存在攻击力大于这张牌防御力的就赢了。否则就回应对面的牌，递归到回应的牌就行了。采用记忆化，时间复杂度为 $(nlogn)$ 。

vector<array<int,2> >a(N),b(N);
vector<array<int,2> >sufa(N),sufb(N);
vector<int>res(N);
int n,m;
int dfs(int x){
    if(res[x]!=-1)return res[x];
    auto fig=(array<int,2>){a[x][1]+1,0};
    int it=upper_bound(b.begin()+1,b.begin()+1+m,fig)-b.begin();
    res[x]=1;
    if(it>m){
        return res[x]=0;
    }
    fig=(array<int,2>){sufb[it][0]+1,0};
    it=upper_bound(a.begin()+1,a.begin()+1+n,fig)-a.begin();
    if(it>n){
        return res[x]=2;
    }
    return res[x]=dfs(sufa[it][1]);
}
void solve(){
    a.clear();
    b.clear();
    sufa.clear();
    sufb.clear();

    n=read();
    for(int i=1;i<=n;i++)   a[i][0]=read();     //attack
    for(int i=1;i<=n;i++)   a[i][1]=read();     //defence

    m=read();
    for(int i=1;i<=m;i++)   b[i][0]=read();
    for(int i=1;i<=m;i++)   b[i][1]=read();

    sort(a.begin()+1,a.begin()+1+n);
    sort(b.begin()+1,b.begin()+1+m);

    for(int i=1;i<=n+1;i++){
        sufa[i][0]=sufa[i][1]=0;
    }
    for(int i=1;i<=m+1;i++){
        sufb[i][0]=sufb[i][1]=0;
    }

    for(int i=n;i>=1;i--){  //[0]=val [1]=poi
        sufa[i]=sufa[i+1];  
        if(a[i][1]>sufa[i][0]){
            sufa[i][0]=a[i][1];
            sufa[i][1]=i;
        }
    }
    for(int i=m;i>=1;i--){
        sufb[i]=sufb[i+1];
        if(b[i][1]>sufb[i][0]){
            sufb[i][0]=b[i][1];
            sufb[i][1]=i;
        }
    }
    int ans[3]={0,0,0};
    for(int i=1;i<=n;i++){
        res[i]=-1;
    }
    for(int i=1;i<=n;i++){
        if(res[i]==-1) res[i]=dfs(i);
        ans[res[i]]++;
    }
    for(auto x:ans){
        cout<<x<<" ";
    }
    cout<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}