专栏文章

题解：AT_agc071_a [AGC071A] XOR Cross Over

BBPG_ning
AT_agc071_a题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minahp2s
此快照首次捕获于
2025/12/01 23:13
3 个月前
此快照最后确认于
2025/12/01 23:13
3 个月前
查看原文
半年前做过它，当时不会，由于在学文化也没学，今天晚自习自己做出来了。
首先设 bib_i 表示第 ii 个位置最后的结果。
容易发现，bi=xoriaib_i=\text{xor}_{i} a_{i}，不妨打表看看 bib_i 被哪些 aia_i 影响。
打表代码：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=15;
bitset<N> a[N];
int n,v[N],p[N],fl[N];
void dfs(int x){
    if(x==n){
        for(int i=1;i<=n;i++) a[i]=0,a[i][i]=1;
        for(int i=1;i<=n;i++) fl[i]=0;
        fl[0]=fl[n]=1;
        for(int i=1;i<n;i++){
            bitset<N> al=0,ar=0;
            for(int j=p[i];!fl[j];j--) al^=a[j];
            for(int j=p[i]+1;;j++){ar^=a[j];if(fl[j]) break;}
            for(int j=p[i];!fl[j];j--) a[j]^=ar;
            for(int j=p[i]+1;;j++){a[j]^=al;if(fl[j]) break;}
            fl[p[i]]=1;
        }
        cout<<"dfs::\n";
        for(int i=1;i<n;i++) cout<<p[i]<<' '; cout<<'\n';
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cout<<a[i][j];
            cout<<'\n';
        }
        return ;
    }
    for(int j=1;j<n;j++) if(!v[j]){
        v[j]=1; p[x]=j;
        dfs(x+1);
        v[j]=0;
    }
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    n=8;
    dfs(1);
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}
下文称偶数区间是长度为偶数的区间，奇数区间是长度为奇数的区间。
我们可以发现很多事情：
1.对 ii 有影响的数构成一个包含 ii 的区间（下文称为影响区间）；
2.对于偶数的 nn 来说，所有影响区间 都是 偶数区间；
这告诉我们做操作做到一个偶数区间时，我们不关心这个区间外面对里面的贡献，因为一个里面的位置都会把外面的贡献异或偶数次。
3.对于奇数的 nn 来说，恰好 存在一个位置的影响区间长度是偶数。
我们设这个位置是 pp，我们还能发现：
4.对于奇数的 nn 来说，pp 的影响区间是 [1,n][1,n]。
5.对于奇数的 nn 来说，除了 pp 的其他位置的影响区间 不包含 pp。
6.对于奇数的 nn 来说，pp 把整个序列划分成两个偶数区间，换言之 pp 是奇数。
根据发现的性质 4,5,6 我们猜测，答案就是 [1,p)[1,p) 的答案 +(p,n]+(p,n] 的答案 +xori=1nai+\text{xor}_{i=1}^n a_{i}。
这个时候我们再来看 nn 是偶数的情况。
若下一次操作把他划分成两个偶数区间，由于我们已经推导出了“偶数区间不关心外面对里面的贡献”这件事，所以可以直接划分成两个独立的子问题。
若下一次操作把他划分成两个奇数区间，根据性质 3，我们只关心贡献对 pp 的影响。通过打表观察或者直接分析能发现两个区间的 pp 的影响区间为 [1,n][1,n]，所以还是能划分成两个独立的子问题。
然后我们就可以 dp 了：设 fl,rf_{l,r} 表示在 不考虑 区间外的影响，能操作到的 min⁡∑bi\min\sum b_i (即就把区间 [l,r][l,r] 抠出来作为序列的答案)。根据上述结论转移是容易的。
时间复杂度 O(n3)O(n^3)。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=505;
const LL linf=1e16+10;
int n;
LL a[N],f[N][N],g[N][N];
void read(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
}
void dp(){
    for(int i=1;i<=n;i++) for(int l=1;l+i-1<=n;l++){
        int r=l+i-1;
        f[l][r]=linf;
        if(i&1){
            for(int k=l;k<=r;k+=2){
                f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+(a[r]^a[l-1]));
            }
        }else{
            for(int k=l+1;k<r;k+=2){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
            for(int k=l;k<=r;k+=2){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-(a[k]^a[l-1])-(a[r]^a[k])+(a[r]^a[l-1])*2);
            }
        }
    }
    cout<<f[1][n]<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    read();
    dp();
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}
半年前那个还在迷茫徘徊的少年，我替你做出这道题了，你还满意吗？

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...