ABC396 题解报告

2025/3/9 OI 题解比赛

闲话

这次评分如下：
\(\text{NaN}-25-384-645-1358-1455-2124\)
知道什么意思了吧（

T1

洛谷传送门
 AT传送门

没看题

T2

洛谷传送门
 AT传送门

没看题

T3

洛谷传送门
 AT传送门

没看题

T4

洛谷传送门
 AT传送门

题意

给你一张联通的 DAG，每条边有权值，求从 \(1\) 到 \(N\) 号点的所有简单路径上的权值的的最小异或和。

数据范围

\(2\le N\le 10\)
\(N-1\le M\le\frac{N(N-1)}{2}\)
\(0\le w_{i}<2^{60}\)

思路

首先如果你没有看见数据范围，默认当成 \(1\le N\le2\times10^{5}\) 的话，可能会想很久。所以这件事告诉我们一定要先看数据范围。

\(N\) 只有 \(10\)，一般就会往 \(2^{n},n!,3^{n},4^{n}\) 之类的复杂度的算法去想。

可能一眼会认为状压DP，但仔细想一想，要求的是异或和最小，但是当前你所在的这种状态的最小值，在后面异或后，可能并不是最小的了，比如 \(2<3\)，但是 \(2\oplus5>3\oplus5\)。这并不是很好维护的（可能存在做法，如果是可行的，请告诉我，谢谢）。
那么状压行不通，\(N\) 这么小，那么我们就可以直接暴力枚举所有可能的情况，最多有 \((N-1)!\) 种可能（因为必须从 \(1\) 号点开始），这道题中也就是 \(9!=362880\) 种，每次还需要 \(O(n)\) 判断是否合法和计算异或和，因此总时间复杂度也就是 \(O(n!n)\)。

注意，当走到 \(N\) 的时候就不能继续走了。

代码

// Problem: D - Minimum XOR Path
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=100+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans=inf_long,p[MAXN],g[MAXN][MAXN];
bool vis[MAXN];

void dfs(int pos){
    if(p[pos-1]==n){
        int sum=0;
        bool flag=false;
        for(int i=2;i<pos;i++){
            if(g[p[i-1]][p[i]]!=-1) sum^=g[p[i-1]][p[i]];
            else{
                flag=true;
                break;
            }
        }
        if(!flag) ans=min(ans,sum);
        return;
    }
    if(pos==n+1) return;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=true;
            p[pos]=i;
            dfs(pos+1);
            vis[i]=false;
        }
    }
}

signed main(){
    read(n,m);
    memset(g,-1,sizeof(g));
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u,v,w);
        g[u][v]=g[v][u]=w;
    }
    p[1]=1;vis[1]=true;
    dfs(2);
    cout<<ans;
    return 0;
}

此题在 AtCoder 上评分为 \(645\)，也就只是一次 DFS，思路也很容易，建议评黄。

T5

洛谷传送门
 AT传送门

题意

给定三个长度为 \(M\) 的序列 \(X,Y,Z\)，问是否存在一个长度为 \(N\) 的序列 \(A\)，满足 \(\forall1\le i\le M,A_{X_{i}}\oplus A_{Y_{i}}=Z_{i}\)。输出 \(\sum\limits_{i=1}^{n}A_{i}\) 最小的任意一种方案，若不存在合法的 \(A\)，则输出 \(-1\)。

数据范围

\(2\le N\le 2\times10^{5}\)
\(2\le M\le 10^{5}\)
\(1\le X_{i},Y_{i}\le N\)
\(0\le Z_{i}<10^{9}\)

思路

首先，异或是存在交换律的，也就是 \(x\oplus y=y\oplus x\)。
因此我们考虑将 \(X_{i}\) 和 \(Y_{i}\) 之间连一条边，边权为 \(Z_{i}\)，那么问题就转化成了：对于任意一条边，都需要满足它的两个端点的权值的异或和，等于这条边的权值。若存在一条边出现矛盾，那么就不存在合法的方案。

我们知道，若 \(x=y\)，那么有 \(x\oplus z=y\oplus z\)，因此我们找出一种合法的方案后，对该连通块的所有点的权值都异或上一个相同的数，依然是合法的方案。

找任意一个合法的方案是容易的，我们 DFS 一下，对未访问过的点赋值，对访问过的点进行检查，出现矛盾直接为无解。

找出一种方案后，我们统计一下当前这个连通块下，每个点的权值在二进制下每一位的 \(0\) 的数量和 \(1\) 的数量。假如 \(1\) 的数量大于 \(0\) 的数量，那么显然对于这一位，把 \(1\) 异或成 \(0\)，\(0\) 异或成 \(1\) 是更优的。

最后再跑一次 DFS，把这个连通块内每个点的权值都改一下就行了。

注意：图不一定全联通。

代码

// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,k,num,head[MAXN],t[MAXN][40][2],z[MAXN];
bool vis[MAXN],vis2[MAXN];
struct node{
    int to,next,val;
}edge[MAXN<<1];

void build(int u,int v,int w){
    edge[++k].to=v;
    edge[k].next=head[u];
    edge[k].val=w;
    head[u]=k;
}

void dfs(int f,int fa,int u){
    vis[u]=true;
    for(int i=0;i<=35;i++){
        if(z[u]&(1ll<<i)) t[f][i][1]++;
        else t[f][i][0]++;
    }
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v]){
            if(z[v]!=(z[u]^edge[i].val)){
                cout<<-1;
                exit(0);
            }
            continue;
        }
        z[v]=z[u]^edge[i].val;
        dfs(f,u,v);
    }
}

void work(int u){
    vis2[u]=true;
    z[u]^=num;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis2[v]) continue;
        work(v);
    }
}

signed main(){
    read(n,m);
    memset(z,-1,sizeof(z));
    for(int i=1;i<=m;i++){
        int x,y,z;
        read(x,y,z);
        build(x,y,z);
        build(y,x,z);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            z[i]=0;
            dfs(i,i,i);
            num=0;
            for(int j=0;j<=35;j++) if(t[i][j][1]>t[i][j][0]) num|=(1ll<<j);
            work(i);
        }
    }
    for(int i=1;i<=n;i++) cout<<z[i]<<" ";
    return 0;
}

此题在 AtCoder 上评分为 \(1358\)，转化为图上问题，思路较为容易，建议评绿。

T6

洛谷传送门
 AT传送门

题意

给定一个长度为 \(N\) 的序列 \(A\)，对于每一个 \(0\le k\le M-1\)，令 \(B_{i}=(A_{i}+k)\bmod M\)，求 \(B\) 的逆序对数量。

数据范围

\(1\le N,M\le 2\times10^{5}\)
\(0\le A_{i}<M\)

思路

我们知道，对一个序列中所有数同时加上或者减去一个相同的数，这个序列的逆序对数量是不会发生改变的。
但这道题中，它还需要取模，这会导致某些数的相对大小关系发生变化。
首先我们转化一下，题意其实也就是每次将 \(A\) 中每个元素增加 \(1\) 后，对 \(M\) 取模后，求一下逆序对数量。

思考一下会产生哪些影响，一个数发生变化，要么是增加 \(1\)，要么是从 \(M-1\) 变成 \(0\)。前者因为是全局加，不会产生影响，因此我们只需要考虑后者。

逆序对是对于一个数，计算它前面的数中有多少比它大的数，在我的思路中，我将其转化为了计算小于等于它的数有多少，记 \(val_{i}\) 表示第 \(i\) 个位置的数的前面的数中，有多少个是小于等于第 \(i\) 个数的。当然，正着做也是可行的。

我们不妨先假设 \(A\) 序列中没有相同的元素。
那么当这个数是 \(M-1\) 时，对于其后面的每一个数 \(A_{i}\)，一定都是 \(M-1>A_{i}\)，而变成 \(0\) 后，一定都是 \(0<A_{i}+1\)。因此也就是一个区间加。
而对于他自己，原来它前面的数都是小于等于它的，现在全都变成大于它了，也就是这个位置的 \(val_{i}\) 变为 \(0\)。

那么对于有重复的数的时候。
因为是同时发生变化的，所以对于位置靠后的数，从 \(M-1\) 变为 \(0\) 后，\(val_{i}\) 并不会变成 \(0\)，而会变成：其前面的数中，在更改之前，值为 \(M-1\) 的数的数量。

每个位置从 \(M-1\) 变为 \(0\) 的时间是可以计算的，我们便可以按照每个数变化的时间来进行计算。

代码

// Problem: F - Rotated Inversions
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans,tot,cnt,b[MAXN],pos[MAXN],val[MAXN],id[MAXN],t[MAXN];
struct node{
    int l,r,val,lazy;
}tree[MAXN<<2];

bool cmp(int n1,int n2){
    if(pos[n1]!=pos[n2]) return pos[n1]<pos[n2];
    return n1<n2;
}

int lowbit(int u){return u&(-u);}

void update(int pos,int val){
    while(pos<=m){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=0;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

void pushup(int id){
    tree[id].val=tree[id*2].val+tree[id*2+1].val;
}

void pushdown(int id){
    if(tree[id].lazy==0) return;
    tree[id*2].val+=(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
    tree[id*2+1].val+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
    tree[id*2].lazy+=tree[id].lazy;
    tree[id*2+1].lazy+=tree[id].lazy;
    tree[id].lazy=0;
}

void build(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    tree[id].lazy=0;
    if(l==r){
        tree[id].val=val[l];
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}

void update(int id,int l,int r,int L,int R,int val){
    if(L>R) return;
    if(r<L||R<l) return;
    if(L<=l&&r<=R){
        tree[id].lazy+=val;
        tree[id].val+=(r-l+1)*val;
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    if(L<=mid) update(id*2,l,mid,L,R,val);
    if(R>mid) update(id*2+1,mid+1,r,L,R,val);
    pushup(id);
}

int query(int id,int l,int r,int pos){
    if(l==r) return tree[id].val;
    pushdown(id);
    int mid=(l+r)>>1;
    if(pos<=mid) return query(id*2,l,mid,pos);
    else return query(id*2+1,mid+1,r,pos);
}

signed main(){
    read(n,m);tot=n*(n-1);tot>>=1;
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=n;i++) pos[i]=(m-b[i])%m;
    for(int i=1;i<=n;i++) if(pos[i]==0) pos[i]=m;
    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++){
        val[i]=query(b[i]+1);
        update(b[i]+1,1);
    }
    build(1,1,n);
    ans=tree[1].val;
    for(int i=1;i<=n;i++){
        if(pos[id[i-1]]!=pos[id[i]]) cnt=0;
        else cnt++;
        for(int j=pos[id[i-1]];j<pos[id[i]];j++) cout<<tot-ans<<endl;
        update(1,1,n,id[i]+1,n,1);
        int should=-query(1,1,n,id[i])+cnt;
        update(1,1,n,id[i],id[i],should);
        ans=tree[1].val;
    }
    for(int j=pos[id[n]]+1;j<=m;j++) cout<<tot-ans<<endl;
    return 0;
}

优化

其实我们发现，每次区间加，都是对从当前这个位置的后一个位置到序列结尾都增加 \(1\)，这个是可以直接计算的，再将单点进行修改，这个也是只对其位置和前面的数的值有关的，这些都是可以简单计算的，因此并不需要线段树。
另外，对于前文所说：

因为是同时发生变化的，所以对于位置靠后的数，从 \(M-1\) 变为 \(0\) 后，\(val_{i}\) 并不会变成 \(0\)，而会变成：其前面的数中，在更改之前，值为 \(M-1\) 的数的数量。

因为原先前面的 \(M-1\) 对后面的 \(M-1\) 多贡献了一次（最开始本来相等贡献了一次，变成 \(0\) 后又贡献了一次）。因此在处理到后面的 \(M-1\) 的时候，直接减去其前面的数的个数，就可以了。

~~（但是我在场上想到线段树后就直接打线段树了啊啊啊啊）~~

注意，因为权值有 \(0\)，所以在树状数组上求逆序对的时候，需要先将权值增加 \(1\)，再加进树状数组里。

更简单的代码

// Problem: F - Rotated Inversions
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans,tot,b[MAXN],pos[MAXN],id[MAXN],t[MAXN];

bool cmp(int n1,int n2){
    if(pos[n1]!=pos[n2]) return pos[n1]<pos[n2];
    return n1<n2;
}

int lowbit(int u){return u&(-u);}

void update(int pos,int val){
    while(pos<=m){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=0;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

signed main(){
    read(n,m);tot=n*(n-1);tot>>=1;
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<=n;i++) pos[i]=(m-b[i])%m;
    for(int i=1;i<=n;i++) if(pos[i]==0) pos[i]=m;
    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++){
        ans+=query(b[i]+1);
        update(b[i]+1,1);
    }
    for(int i=1;i<=n;i++){
        for(int j=pos[id[i-1]];j<pos[id[i]];j++) cout<<tot-ans<<endl;
        ans+=n-id[i];ans-=id[i]-1;
    }
    for(int j=pos[id[n]]+1;j<=m;j++) cout<<tot-ans<<endl;
    return 0;
}

此题在 AtCoder 上评分为 \(1455\)，考虑一个数改变后产生的影响，相对容易，再进一步推导，可以得出不需要使用线段树的做法，建议评绿。

T7

洛谷传送门
 AT传送门

暂时不会。

LOADING

ABC396 题解报告

闲话

T1

T2

T3

T4

题意

数据范围

思路

代码

T5

题意

数据范围

思路

代码

T6

题意

数据范围

思路

代码

优化

更简单的代码

T7