整理了几道2026 XCPC区域赛的典型题目，覆盖不同考点，分享思路与细节处理。
题1 山东区域赛：最大异或和树
题目大意
给定一棵n个节点的树，每个点有权值 a_i，定义一条路径的权值为路径上所有点权的异或和，求树上所有路径中，权值最大的那条路径的权值。n ≤ 2e5。
思路分析
经典异或问题变形，我们先回忆一下树上两点路径异或和的性质：设 x[i] 表示根节点到i节点的异或和，那么u到v路径的异或和等于 x[u]^ x[v]，因为LCA到根的部分被异或抵消了。
所以问题转化为：给定一个长度为n的数组x，找出数组中两个数异或的最大值，这就是经典的01字典树模板题，具体步骤：
DFS遍历树求出所有节点的x[i]
从高位到低位将每个x[i]插入二进制01字典树
每个x[i]插入前，在字典树走贪心路径：尽量走和当前位相反的位，得到最大异或值，更新全局答案
细节注意
点权异或和时不要忘了根节点本身的权值，边界处理：根节点x[root] = a[root]，最终结果至少可以取单点路径，不会出现空路径。
时间复杂度O(n log A)，A是最大点权，完全可以过2e5的数据范围。
题2 西安区域赛：区间质数计数
题目大意
给定L和R，求区间 [L, R] 中质数的个数，其中 1 ≤ L ≤ R ≤ 1e12，R-L ≤ 1e6。
思路分析
这是经典的埃氏筛法分段应用，核心思路：
所有区间 [L, R] 中的合数，一定有一个不超过 √R 的质因子，√(1e12) = 1e6，范围很小。
先筛出 1~1e6 之间的所有质数，保存下来。
开辟一个大小为 R-L+1 的布尔数组，初始全部标记为质数，然后用每个筛出来的质数p，将 [L, R] 中所有p的倍数标记为合数。
最后数一下数组中剩余的质数个数，注意特判L=1的情况，1要标记为合数。
技巧处理
找第一个≥L的p的倍数，公式是 ceil(L/p) * p，代码实现可以写成：(L + p - 1)/p * p，不需要浮点运算，直接整数计算即可。每个数的下标可以用 x - L 映射到数组，空间占用刚好是1e6，完全没问题。
题3 沈阳区域赛：多重背包的二进制拆分优化
题目大意
有n种物品，第i种物品有 c_i 个，重量 w_i，价值 v_i，背包总容量是m，求背包能装下的最大价值，其中n ≤ 1000，m ≤ 1e4，Σc_i ≤ 1e5。
思路分析
多重背包的标准优化题，普通O(nm)的单调队列优化可以过，但二进制拆分写起来更简单不容易错：
二进制拆分的核心是，任何一个数 c_i 都可以拆成 2^0, 2^1, ..., 2^k, 剩余 的和，这样拆分后的每一份可以选或不选，就能组合出0~c_i的任意个数，把多重背包转化为01背包求解。
比如 c_i=10，拆成 1, 2, 4, 3，1+2+4+3=10，可以组合出0~10的任何整数，拆分之后一共只有 log c_i 份，n个物品拆分后的总个数最多是 Σ log c_i，对于1e5的总c，拆分后不到2000个，完全可以跑01背包。
复杂度
时间复杂度O(m * Σ log c_i)，本题中m=1e4，拆分后总个数约2000，总运算量2e7，完全可以在时间限制内跑完，比单调队列写起来简单很多，考场优先选这个方法。
题4 广州区域赛：字符串最小循环移位
题目大意
给定一个长度为n的字符串s，求它的最小字典序循环移位结果，n ≤ 1e6。
思路分析
经典的Booth算法模板题，可以在O(n)时间内求出最小循环移位：
核心思路是用两个指针i,j分别标记两个候选的起始位置，k表示当前匹配的长度，每次比较 s[(i+k)%n] 和 s[(j+k)%n]：
如果相等，k++继续比
如果 s[(i+k)%n] > s[(j+k)%n]，说明i到i+k之间的所有位置都不可能是答案，令 i += k+1
否则，说明j到j+k之间的位置不可能是答案，令 j += k+1
如果i == j，就把其中一个加1，避免两个指针重合
最后取i和j中较小的那个，就是最小循环移位的起始位置，输出从这个位置开始的循环串即可。
也可以用后缀数组做：把s拼接成s+s，然后建后缀数组，找第一个长度≥n的后缀，起始位置< n，输出对应长度为n的子串即可，时间复杂度O(n log n)，对于1e6也能过，但是Booth算法更省空间，时间更快，是最优解。
题5 南京区域赛：矩阵快速幂求线性递推第n项
题目大意
已知递推式 f(n) = a1 f(n-1) + a2 f(n-2) + ... + ak f(n-k)，给定前k项，求f(n) mod 1e9+7，其中 k ≤ 100，n ≤ 1e18。
思路分析
这是线性递推的标准矩阵快速幂解法：
构造k×k的转移矩阵，第一行就是递推系数a1, a2, ..., ak，第i行（i≥2）在第i-1列是1，其余是0，也就是：
初始列向量就是 [f(k), f(k-1), ..., f(1)]^T，转移矩阵的n-k次方乘初始向量，第一个元素就是f(n)。
优化提示
当k比较大的时候，矩阵乘法复杂度是O(k^3 log n)，对于k=100，log n是60，总运算量约6e7，完全没问题；如果k更大，可以用快速倍增法（也就是常说的杜兰伯戈-伯恩斯坦算法，也就是俗称的快速线性递推）把复杂度降到O(k^2 log n)，不过本题k很小，矩阵快速幂写起来更简单，足够通过。
总结
2026 XCPC区域赛的题目整体还是注重基础算法的考察，大部分题目都是经典模型的变形，只要把基础模板练熟，掌握常见转化技巧，就能拿到不错的分数。上面整理的这几道都是区域赛中难度中等偏基础的题，适合用来练习算法基础。