OI笔记 | 2022.12 做题记录（一）
半个月没放做题记录了。清一下云剪贴板。
- [NOIP2003 提高组] 加分二叉树
- 划分数列
- [NOIP2006 提高组] 能量项链
- [USACO16OPEN]262144 P
- TWINSNOW - Snowflakes
- 平面最近点对
- 由乃救爷爷
- XOR on Segment
- 最长异或路径
- 基数排序
[NOIP2003 提高组] 加分二叉树
设一个 $n$ 个节点的二叉树 $\text{tree}$ 的中序遍历为$(1,2,3,\ldots,n)$，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$，$\text{tree}$ 及它的每个子树都有一个加分，任一棵子树 $\text{subtree}$（也包含 $\text{tree}$ 本身）的加分计算方法如下：
$\text{subtree}$ 的左子树的加分 $\times$ $\text{subtree}$ 的右子树的加分 $+$ $\text{subtree}$ 的根的分数。
若某个子树为空，规定其加分为 $1$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 且加分最高的二叉树 $\text{tree}$。要求输出
-
$\text{tree}$ 的最高加分。
-
$\text{tree}$ 的前序遍历。
题解
考虑区间 dp。如果中序遍历是一个 $(x\dots y)$ 的排列，那么枚举根节点 $k$，可以设 $(x\dots k-1)$ 为左子树， $(k+1\dots y)$ 为右子树，加分即为 $dp(x,k-1)\times dp(k+1,y)+dp(k,k)$。从较小的区间开始转移，故答案即为 $dp(1,n)$。输出前序遍历只要在 $dp$ 时记录即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 40;
int n, dp[MAX_N][MAX_N], r[MAX_N][MAX_N];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
void print(int s, int t) {
write(r[s][t]), putchar(' ');
if(s == t) return;
if(s <= r[s][t] - 1) print(s, r[s][t] - 1);
if(r[s][t] + 1 <= t) print(r[s][t] + 1, t);
}
int main() {
n = read();
for(int i = 1; i <= n; i++)
dp[i][i] = read(), dp[i][i - 1] = 1, r[i][i] = i;
for(int len = 1; len <= n; len++) {
for(int i = 1; i + len <= n; i++) {
int j = i + len;
dp[i][j] = dp[i + 1][j] + dp[i][i];
r[i][j] = i;
for(int k = i + 1; k < j; k++) {
if(dp[i][j] < dp[i][k - 1] * dp[k + 1][j] + dp[k][k]) {
dp[i][j] = dp[i][k - 1] * dp[k + 1][j] + dp[k][k];
r[i][j] = k;
}
}
}
}
write(dp[1][n]), putchar('\n');
print(1, n);
return 0;
}
划分数列
给定一个正整数 $n$，请你考虑下面这个长度为 $n$ 的数列：
\[\varphi(1),\varphi(2),\varphi(3),\dots\varphi(n)\]其中 $\varphi(x)$ 为欧拉函数，定义为小于或等于 $x$ 且与 $x$ 互质的正整数的个数，例如 $\varphi(1)=\varphi(2)=1$。
判断是否可以把这个数列分成和相等的两组，如果可以，输出任意一种划分方案。
$1\le n\le 5×10^6$
题解
自己造的第一个题。原 MO 题是 2022 北大金秋营的一题：
求证：对任意整数 $n>1,\varphi(1),\varphi(2),\dots\varphi(n)$ 可以分成和相等的两组。
结论来看，我们这题只有 $n=1$ 的情况不能找到划分方案。接下来我们来证明一下原题，证明的过程中也就得到了划分的方案。
考虑直接证明一个更强的结论：
引理：对任意整数 $n>1,a_1,a_2,\dots a_n\in \mathbb{Z_+},a_i\le i$ 且 $\sum\limits_{i=1}^n a_i$ 为偶数，则数列 $a$ 可以分成和相等的两组。
引理证明：
设 $A$ 组内的和为 $S_A $，$B$ 组内的和为 $S_B$。
首先我们把 $a_n$ 放入 $A$ 组， $a_{n-1}$ 放入 $B$ 组。则由于 $1\le a_n\le n$ 且 $1\le a_{n-1}\le n-1$，可知 $0\le \lvert S_A-S_B\rvert \le n - 1$。
数学归纳法。假设已经放好了 $a_n,a_{n-1}\dots a_{i+1}$，且满足 $0\le \lvert S_A-S_B\rvert \le i + 1$。 现在考虑放 $a_{i}$，分类讨论：
-
若此时 $S_A=S_B$，我们随意放入一个组内，假设放入 $B$ 中。那么新的差的绝对值会等于 $ \lvert S_A-(S_B + a_i)\rvert = \lvert a_i\rvert$，由于 $1\le a_i\le i$，所以新的差的绝对值满足 $0\le \lvert S_A-(S_B + a_i)\rvert\le i$。
-
若此时 $S_A>S_B$，我们放入 $B$ 中。由于 $0< S_A-S_B\le i+1$ 且 $1\le a_i\le i$，则新的差 $-i<S_A-(S_B+a_i) \le i$，所以新的差的绝对值也满足 $0\le \lvert S_A-(S_B + a_i)\rvert\le i$。
-
若此时 $S_A<S_B$，同 $2$ 可证放入 $A$ 中能使得新的差的绝对值也满足 $0\le \lvert S_B-(S_A + a_i)\rvert\le i$
所以我们可以从考虑 $a_n\dots a_{i+1}$ 时的 $0\le \lvert S_A-S_B\rvert \le i + 1$ 推出考虑 $a_n\dots a_i$ 时的 $0\le \lvert S_A-S_B\rvert \le i$。
所以考虑 $a_n\dots a_1$ 时的 $0\le \lvert S_A-S_B\rvert \le 1$。又因为 $S_A+S_B$ 为偶数，所以有 $S_A=S_B$。
事实上，这就是 OIer 说的不断贪心地把当前的数加到和较小的组上，能使得两组的和最平均的依据。
那么这题就很显然了，显然 $1$ 到 $n$ 的欧拉函数之和一定为偶数。用线性筛 $O(n)$ 求出所有 $1$ 到 $n$ 的欧拉函数，然后贪心地分组即可。注意开 long long。
std.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e7 + 10;
inline ll read() {...}
inline void write(ll x) {...}
bool vis[MAX_N];
int phi[MAX_N], primes[MAX_N], cnt = 0;
void init(int n) {
for(int i = 1; i <= n; i++)
vis[i] = 1;
vis[1] = 0, phi[1] = 1;
for(int i = 2; i <= n; i++) {
if(vis[i]) {
primes[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * primes[j] <= n; j++) {
vis[i * primes[j]] = 0;
if(i % primes[j] == 0) {
phi[i * primes[j]] = primes[j] * phi[i];
break;
}
else phi[i * primes[j]] = phi[primes[j]] * phi[i];
}
}
}
vector<int> A, B;
ll sumA, sumB;
int main() {
int n = read();
init(n);
if(n == 1) {
puts("NO");
return 0;
}
A.push_back(phi[n]), B.push_back(phi[n - 1]);
sumA += phi[n], sumB += phi[n - 1];
for(int i = n - 2; i >= 1; i--) {
if(sumA >= sumB) {
B.push_back(phi[i]);
sumB += phi[i];
}
else {
A.push_back(phi[i]);
sumA += phi[i];
}
}
puts("YES");
write(A.size()), putchar(' '), write(B.size()), putchar('\n');
for(int x : A) write(x), putchar(' ');
putchar('\n');
for(int x : B) write(x), putchar(' ');
putchar('\n');
return 0;
}
gen.py
from cyaron import *
_n = ati([0, 200, 600, 1000, 1, 10000, 100000, 5e5, 1e6, 5e6, 5e6])
for i in range(1, 11):
io = IO(file_prefix = "seq", data_id = i)
if(_n[i] == 1):
n = 1
else:
n = randint(_n[i - 1], _n[i])
io.input_writeln(n)
io.output_gen("std.exe")
[NOIP2006 提高组] 能量项链
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
$4 \le N \le 100$
题解
断环成链，然后就是区间 dp 的板子。
$dp(l,r)$ 表示从第 $l$ 个项链到第 $r$ 个项链的最大能量，然后枚举断开点 $k$，则有：
$dp(l,r) = \max(dp(l,k)+dp(k,r)+a_l\times a_k \times a_r)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 210;
int dp[MAX_N][MAX_N], a[MAX_N];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n; i++)
a[i] = read(), a[i + n] = a[i];
for(int len = 1; len <= n; len++) {
for(int l = 1; l + len <= 2 * n; l++) {
int r = l + len;
for(int k = l + 1; k <= r - 1; k++)
dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
}
}
for(int i = 1; i <= n; i++)
ans = max(ans, dp[i][i + n]);
write(ans);
return 0;
}
[USACO16OPEN]262144 P
Bessie 喜欢在手机上下游戏玩，然而她蹄子太大，很难在小小的手机屏幕上面操作。
她被她最近玩的一款游戏迷住了，游戏一开始有 $n$ 个正整数，($2\le n\le 262144$)，范围在 $1\sim40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个 $7$ 合并成一个 $8$)，目标是使得最大的数最大，请帮助 Bessie 来求最大值。
题解
考虑一个玄妙的状态设计： $dp(i,j)$ 表示以 $j$ 为起点，合成出 $i$ 的右端下标，则：
$dp(i,j)=dp(i-1,dp(i-1,j))$
类似于倍增。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 3e5 + 10, MAX_M = 60;
int a[MAX_N], dp[MAX_M][MAX_N];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
int main() {
int n = read(), ans = 1;
for(int i = 1; i <= n; i++)
a[i] = read(), dp[a[i]][i] = i + 1;
for(int i = 2; i <= 58; i++) {
for(int j = 1; j <= n; j++) {
if(!dp[i][j]) dp[i][j] = dp[i - 1][dp[i - 1][j]];
if(dp[i][j]) ans = i;
}
}
write(ans);
return 0;
}
TWINSNOW - Snowflakes
你可能听说过，没有两片雪花是相同的。你要写一个程序，判断这是不是真的。你的程序会读到一些有关于这些雪花的信息，找到一对完全相同的雪花。每片雪花有六个角。对于每个雪花，你的程序会获得每个角的长度。我们认为两片雪花相同，当且仅当它们各自从某一个角开始，逆时针或顺时针记录长度，能得到两个相同的六元组。
题解
对于一个雪花，记录它的所有数字和 $sum_i\bmod 99991$，作为它的特征值（hash）。
然后对与这个雪花特征值相同的所有雪花暴力匹配。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5, MOD = 99991;
int a[MAX_N][6], sum[MAX_N];
vector<int> f[MOD + 5];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
bool check(int x, int y) {
for(int i = 0; i <= 5; i++) {
bool flag = 1;
for(int k = 0; k <= 5; k++) {
if(a[x][k] != a[y][(i + k) % 6]) {
flag = 0;
break;
}
}
if(flag) return 1;
flag = 1;
for(int k = 0; k <= 5; k++) {
if(a[x][k] != a[y][(i + 6 - k) % 6]) {
flag = 0;
break;
}
}
if(flag) return 1;
}
return 0;
}
int main() {
int n = read();
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 5; j++)
a[i][j] = read(), (sum[i] += a[i][j]) %= MOD;
for(int i = 1; i <= n; i++) {
for(int k : f[sum[i]])
if(check(i, k)) {
puts("Twin snowflakes found.");
return 0;
}
f[sum[i]].push_back(i);
}
puts("No two snowflakes are alike.");
return 0;
}
平面最近点对
给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$，请输出距离最近的两个点的距离。
$2 \leq n \leq 4 \times 10^5$，$-10^7 \leq x_i, y_i \leq 10^7$。
题解
我们可以通过分治解决这个问题。
假设函数 $\operatorname{solve}(l,mid)$ 和 $\operatorname{solve}(mid,r)$ 已经分别处理完了 $[l,mid)$ 和 $[mid, r)$ 两个区间内部的最近点对，现在考虑如何快速合并答案。
我们先把这个两个区间内的点以纵坐标为关键字做归并排序。
考虑什么样的点会分居在这两个区间内，且可能对答案产生贡献。设这样的点为 $T(x_0,y_0)$ ，它首先要满足 $\lvert x_0 - x_{mid}\rvert \le ans$，否则它与另半边上的所有点的距离都大于 $ans$。其次它可能影响到的区间为 $(y_0, y_0 + ans]$，考虑我们按纵坐标排序了，所以可以双指针，对于每一个可能产生贡献的点，向上找到 $(y_0, y_0 + ans]$ 的所有点，然后计算 $A$ 到这些点的距离，更新答案即可。
从题解里学到了一个内置函数 inplace_merge(l, mid, r, cmp) 可以原地把 $[l,mid)$ 和 $[mid, r)$ 做归并排序。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double, double> pii;
const int MAX_N = 4e5 + 10;
const double INF = 1e20;
int n;
double ans = INF;
pii p[MAX_N];
inline bool cmpx(pii x, pii y) {return x.first < y.first;}
inline bool cmpy(pii x, pii y) {return x.second < y.second;}
inline ll read() {...}
double dis(pii x, pii y) {
double dx = 1.0 * x.first - y.first, dy = 1.0 * x.second - y.second;
return sqrt(dx * dx + dy * dy);
}
void solve(int l, int r) {
if(l + 1 >= r) return;
int mid = (l + r) >> 1, midx = p[mid].first;
solve(l, mid), solve(mid, r);
inplace_merge(p + l, p + mid, p + r, cmpy);
vector<int> t;
for(int i = l; i < r; i++)
if((double)abs((double)midx - p[i].first) <= ans) t.push_back(i);
int i = 0, j = 0;
for(; i < (int)t.size(); i++) {
while(j < (int)t.size() && (double)p[t[j]].second <= (double)p[t[i]].second + ans)
j++;
for(int k = i + 1; k < j; k++)
ans = min(ans, dis(p[t[i]], p[t[k]]));
}
}
int main() {
n = read();
for(int i = 0; i < n; i++)
scanf("%lf %lf", &p[i].first, &p[i].second);
sort(p, p + n, cmpx);
solve(0, n);
printf("%.4lf\n", ans);
return 0;
}
由乃救爷爷
给定一个 $n$ 个数的数列，有 $m$ 次询问。
每次询问给出两个随机数 $l,r$，求 $\max\limits_{i=l}^r a_i$。
$n,m \le 2\times 10^7$，时间限制 $5s$，空间限制 500.00MB。
题解
分块 ST 表的模板题。考虑到时间和空间，不可能直接对整个数列 $O(n\log n)$ 预处理 ST 表。
考虑分块。我们把数列分为 $\sqrt{n}$ 块，对于每块内的最大值建 ST 表，并且求出块内的前缀最大值和后缀最大值。这部分的复杂度为 $O(n+\sqrt n \log \sqrt n)$。
询问时，如果 $l, r$ 不在同一块，则 $l,r$ 之间的整块的最大值可以 ST 表查询，散块的最大值可以用前缀后缀最大值查询，时间复杂度 $O(1)$。如果 $l,r$ 在同一块内，只能暴力计算，时间复杂度 $O(\sqrt n)$。
然后由于数据随机，可以算出期望时间复杂度为 $O(n)$。但是我不会算期望就不算了，反正能过。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N = 2e7 + 10, MAX_LEN = 4500, MAX_LOG = 15;
int a[MAX_N], pre[MAX_N], suf[MAX_N], siz;
struct st {
int mx[MAX_LEN][MAX_LOG], log_2[MAX_LEN], len;
st() {memset(mx, 0, sizeof(mx));}
void init() {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i <= len; i++)
log_2[i] = log_2[i >> 1] + 1;
for(int j = 1; j < MAX_LOG; j++)
for(int i = 1; i + (1 << (j - 1)) - 1 <= len; i++)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
int query(int l, int r) {
int x = log_2[r - l + 1];
return max(mx[l][x], mx[r - (1 << x) + 1][x]);
}
} ST;
// -- 随机数生成器和读入输出优化 --
namespace GenHelper{...}
void srand(unsigned x){...}
int read(){...}
inline ll readint() {...}
inline void write(ull x) {...}
// ------------------------------
inline int bl(int x) {return (x - 1) / siz + 1;};
int main() {
int n = readint(), m = readint(), s = readint();
srand(s);
siz = sqrt(n);
for(int i = 1; i <= n; i++)
a[i] = read();
ST.len = bl(n);
for(int i = 1; i <= bl(n); i++) {
int L = (i - 1) * siz + 1, R = min(i * siz, n);
pre[L] = a[L], suf[R] = a[R];
for(int j = L; j <= R; j++) {
ST.mx[i][0] = max(ST.mx[i][0], a[j]);
if(j > L) pre[j] = max(pre[j - 1], a[j]);
}
for(int j = R - 1; j >= L; j--)
suf[j] = max(suf[j + 1], a[j]);
}
ST.init();
ull ans = 0;
while(m--) {
int l = read() % n + 1, r = read() % n + 1;
if(l > r) swap(l, r);
int t = 0;
if(bl(l) == bl(r)) {
for(int i = l; i <= r; i++)
t = max(t, a[i]);
}
else {
if(bl(l) + 1 <= bl(r) - 1) t = max(t, ST.query(bl(l) + 1, bl(r) - 1));
t = max(t, suf[l]);
t = max(t, pre[r]);
}
ans += t;
}
write(ans);
return 0;
}
XOR on Segment
给定 $n$ 个数的序列 $a$。$m$ 次操作，操作有两种：
1 l r ：求 $\displaystyle\sum_{i=l}^r a_i$。
2 l r x ：把 $a_l\sim a_r$ 异或上 $x$。
$1\le n\le 10^5$，$1\le m\le 5\times 10^4$，$0\le a_i\le 10^6$，$1\le x\le 10^6$。
题解
考虑在线段树的每个节点上维护数组 $cnt$，其中 $cnt_i$ 为区间内数的二进制为 $i$ 的个数。
对于查询操作，答案即为查询 $[l,r]$ 上节点的 $\sum\limits_{i=0}^{19} 2^i\times cnt_i$。
对于修改操作：如果 $x$ 的二进制表示的第 $i$ 位为 $1$，则 $cnt_i\gets (t-s+1)-cnt_i$，其中 $s,t$ 为节点表示的区间。否则不操作。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int a[MAX_N];
struct node {
int cnt[20], tag;
node() {memset(cnt, 0, sizeof(cnt)); tag = 0;}
} d[MAX_N << 2];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return s + ((t - s) >> 1);}
inline void pu(int p) {
for(int i = 0; i < 20; i++)
d[p].cnt[i] = d[lc(p)].cnt[i] + d[rc(p)].cnt[i];
}
inline void change(int p, int x, int s, int t) {
for(int i = 0; i < 20; i++)
if(x & (1 << i)) d[p].cnt[i] = (t - s + 1) - d[p].cnt[i];
}
inline void pd(int p, int s, int t) {
int m = mid(s, t);
change(lc(p), d[p].tag, s, m), change(rc(p), d[p].tag, m + 1, t);
d[lc(p)].tag ^= d[p].tag;
d[rc(p)].tag ^= d[p].tag;
d[p].tag = 0;
}
void build_tree(int s, int t, int p) {
if(s == t) {
for(int i = 0; i < 20; i++)
if(a[s] & (1 << i)) d[p].cnt[i]++;
return;
}
int m = mid(s, t);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
pu(p);
}
ll query(int s, int t, int p, int l, int r) {
if(l <= s && t <= r) {
ll ret = 0;
for(int i = 0; i < 20; i++)
ret += (1ll << i) * d[p].cnt[i];
return ret;
}
pd(p, s, t);
int m = mid(s, t);
ll ret = 0;
if(l <= m) ret += query(s, m, lc(p), l, r);
if(r > m) ret += query(m + 1, t, rc(p), l, r);
return ret;
}
void update(int s, int t, int p, int l, int r, int x) {
if(l <= s && t <= r) {
change(p, x, s, t);
d[p].tag ^= x;
return;
}
pd(p, s, t);
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, x);
if(r > m) update(m + 1, t, rc(p), l, r, x);
pu(p);
}
int main() {
int n = read();
for(int i = 1; i <= n; i++)
a[i] = read();
build_tree(1, n, 1);
int m = read();
while(m--) {
int op = read(), l = read(), r = read(), x;
if(op == 1) write(query(1, n, 1, l, r)), putchar('\n');
else x = read(), update(1, n, 1, l, r, x);
}
return 0;
}
最长异或路径
给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
题解
定义 $sum_i$ 为节点 $i$ 到根节点的异或和，可以 $O(n)$ 处理出来。
则 $x$ 到 $y$ 的路径异或和为 $sum_x \operatorname{xor} sum_y$。
然后我们对所有 $sum_i$ 建 01trie，然后对于每一个 $sum_i$，在 01trie 上跑一遍按位贪心即可。具体来说，如果当前可选的路径中有与 $sum_i$ 的这一位不一样的，就往那边走。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct edge {int u, v, w;};
vector<edge> edges;
vector<int> G[MAX_N];
int tree[MAX_N << 5][2], sum[MAX_N], cnt;
void AddEdge(int u, int v, int w) {
edges.push_back({u, v, w});
G[u].push_back(edges.size() - 1);
}
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
void dfs(int u, int pre) {
for(int i : G[u]) {
int v = edges[i].v, w = edges[i].w;
if(v == pre) continue;
sum[v] = sum[u] ^ w;
dfs(v, u);
}
}
void build(int val) {
int now = 0;
for(int i = 30; i >= 0; i--) {
bool f = (1 << i) & val;
if(!tree[now][f]) tree[now][f] = ++cnt;
now = tree[now][f];
}
}
int query(int val) {
int now = 0, ret = 0;
for(int i = 30; i >= 0; i--) {
bool f = (1 << i) & val;
if(tree[now][f ^ 1]) ret += (1 << i), now = tree[now][f ^ 1];
else now = tree[now][f];
}
return ret;
}
int main() {
int n = read(), ans = 0;
for(int i = 1; i <= n - 1; i++) {
int u = read(), v = read(), w = read();
AddEdge(u, v, w);
}
dfs(1, 0);
for(int i = 1; i <= n; i++)
build(sum[i]);
for(int i = 1; i <= n; i++)
ans = max(ans, query(sum[i]));
write(ans);
return 0;
}
基数排序
基数排序，即按照从小到大的数位排序。
首先我们把个位为 $i$ 的数推入数组 $G_i$ 中，然后枚举 $i=0\sim 9$ 把 $G_i$ 中所有数取出，完成这一步排序。然后依次做十位和百位。
对于 int 范围内的数，其实我们可以转为 $2^{16}$ 进制，这样只用对两位排序，再转回去即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 1e5 + 10, BASE = (1 << 16);
pii num[MAX_N];
vector<pii> G[BASE];
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
int x = read();
num[i].first = x / BASE, num[i].second = x % BASE;
}
for(int i = 1; i <= n; i++)
G[num[i].second].push_back(num[i]);
int tot = 0;
for(int i = 0; i < BASE; i++) {
for(pii x : G[i])
num[++tot] = x;
G[i].clear();
}
for(int i = 1; i <= n; i++)
G[num[i].first].push_back(num[i]);
tot = 0;
for(int i = 0; i < BASE; i++)
for(pii x : G[i])
num[++tot] = x;
for(int i = 1; i <= n; i++)
write(num[i].first * BASE + num[i].second), putchar(i == n ? '\n' : ' ');
return 0;
}
♥