『 江南·蒟蒻 』Round 4 暨 2026 跨年赛题解

T1 祝

这里利用到一个重要的思想：对于一个有确切起点和终点的回路，其路径情况，可以认为是同一个位置出发的两个点同时向前推进，类似的题目可以参考 NOIP2008—传纸条。

所以不要被这个题目的题面欺骗。实际上题目问的，就是从一个起点出发的，具有相同终点的两条路径的最小总长度！

做法可以认为是一类套路，如下：

设 $F_{i,j}$ 为从最左侧的起点出发，一个点走到 $i$，一个点走到 $j(i>j)$，且所有 $i$ 以内的点全部被走过的最短路径。

• $i=j+1$ 时：$F_{i,j}$ 可以由 $F_{j,k},k\in[1,j)$ 转移得到，原因如下图

• $i>j+1$ 时，走在前面的人上一步一定是 $i-1$，所以本情况一定由 $F[i-1][j]$ 转移而来。

总复杂度 $O(n^2)$，思维难度还是有的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=21;
const double INF=1e50;
int n,x0,y0;
double d[N][N],f[1<<N][N];
struct P{int x,y;}p[N];
inline double dis(int a,int b){
    int dx=p[a].x-p[b].x,dy=p[a].y-p[b].y;
    return sqrt(1.0*dx*dx+1.0*dy*dy);
}
int main(){
    scanf("%d%d%d",&n,&x0,&y0);
    p[0]={x0,y0};
    for(int i=1;i<=n;++i)scanf("%d%d",&p[i].x,&p[i].y);
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j)
            d[i][j]=dis(i,j);
    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<=n;++j)
            f[i][j]=INF;
    f[0][0]=0;
    for(int s=0;s<(1<<n);++s){
        for(int u=0;u<=n;++u){
            if(f[s][u]==INF)continue;
            for(int v=1;v<=n;++v){
                if((s&(1<<(v-1))))continue;
                int ns=s|(1<<(v-1));
                f[ns][v]=min(f[ns][v],f[s][u]+d[u][v]);
            }
        }
    }
    double ans=INF;
    int full=(1<<n)-1;
    for(int u=1;u<=n;++u)
        ans=min(ans,f[full][u]+d[u][0]);
    printf("%.2lf\n",ans);
    return 0;
}

T2 大家

$\text{None}$

T3 马年快乐

题目分析

本题的核心是处理树上路径异或更新和节点邻边异或和查询的问题。直接暴力更新路径上的每条边会超时（时间复杂度无法满足 $10^5$ 级别的数据），因此需要利用异或的性质和树的路径特性进行优化。

关键观察

• 树中任意两点 $u, v$ 的简单路径是唯一的，路径可以拆分为 $u \to LCA(u,v) \to v$（LCA 为最近公共祖先）。
• 异或的核心性质：$a \oplus x \oplus x = a$（两次异或同一个数会抵消）。
• 对于节点 $u$，其邻边的异或和等价于：将所有以 $u$ 为端点的边权异或起来的结果。

转化思路

将边权异或更新转化为点权异或更新：

• 初始时，每条边 $(a,b,x)$ 对应将点 $a$ 和点 $b$ 的权值都异或 $x$。此时，节点 $u$ 的权值恰好等于其所有邻边的异或和（因为每条邻边都会在 $u$ 上贡献一次 $x$）。
• 操作 1（路径 $u \to v$ 异或 $x$）：路径上的每条边都会被异或 $x$，等价于将点 $u$ 和点 $v$ 的权值各异或 $x$（路径上的中间节点会被两次异或 $x$，抵消后无影响）。
• 操作 2（查询节点 $u$ 的邻边异或和）：直接输出节点 $u$ 的权值即可。

复杂度分析

• 时间复杂度：$O(n + q)$。初始化阶段遍历 $n-1$ 条边，操作阶段处理 $q$ 次操作，均为线性时间。
• 空间复杂度：$O(n)$。仅需存储每个节点的权值数组。

正确性证明

1. 初始状态：对于节点 $u$，其所有邻边的边权都会在 $w[u]$ 中各贡献一次异或，因此 $w[u]$ 恰好是邻边的异或和。
2. 操作1的正确性：路径 $u \to v$ 上的每条边都会被异或 $x$。设路径为 $u \to p_1 \to p_2 \to ... \to p_k \to v$，则：
   • 边 $(u,p_1)$：$w[u]$ 和 $w[p_1]$ 各异或 $x$；
   • 边 $(p_1,p_2)$：$w[p_1]$ 和 $w[p_2]$ 各异或 $x$；
   • ...
   • 边 $(p_k,v)$：$w[p_k]$ 和 $w[v]$ 各异或 $x$；
     最终，中间节点 $p_1,p_2,...,p_k$ 的权值会被两次异或 $x$（抵消），仅 $u$ 和 $v$ 的权值各异或一次 $x$。因此直接对 $w[u]$ 和 $w[v]$ 异或 $x$ 等价于路径更新。
3. 操作2的正确性：$w[u]$ 始终维护了节点 $u$ 邻边的异或和，因此直接输出即可。

总结

1. 核心思路是将边权操作转化为点权操作，利用异或的抵消性质避免暴力更新路径；
2. 初始时每条边对应两个端点的点权异或边权，查询时直接输出点权；
3. 路径异或更新只需对路径两端点的点权异或更新值，时间复杂度线性，可处理 $10^5$ 级别的数据。

代码

#include<bits/stdc++.h>
using namespace std;
int n,q,w[100005];
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;++i){
    	int a,b,x;
    	cin>>a>>b>>x;
    	w[a]^=x,w[b]^=x;
	}
	for(int op,u,v,x;q;--q){
		cin>>op>>u;
		if(op==1){
			cin>>v>>x;
			w[u]^=x,w[v]^=x;
		}else{
			cout<<w[u]<<endl;
		}
	}
	return 0;
}

T4 呀！