Description

给你 $n$ 个 $[0,2^k)$ 中的整数 $a_1,a_2,\dots,a_n$，第 $i$ 个数对应代价 $b_i$。

你需要选取一个 $U=\{1,2,\dots,n\}$ 的子集 $S$，满足 $\sum_{i\in S} b_i\le m$，以及一个 $[0,2^k)$ 中的整数 $x$，最大化 $\min\{\min_{i\in S}\{a_i+x\},\min_{i\in U\setminus S}\{a_i\oplus x\}\}$。

共 $T$ 组数据。

$1\le n\le 10^5,1\le \sum n\le 5\times 10 ^5,0\le k\le 120,0\le m\le 10^9,0\le b_i\le 10^9$

Read More

ACC NOI 431 B 草莓路径

求一张无向连通图的路径异或最大值，有自环重边，可以多次经过一个点或一条边。

Read More

CF838C Future Failure

这个游戏性质非常好，因为两个操作其实是独立的，无论进行哪种操作都不会使游戏局面发生太大的变动。

Read More

Description

两个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $b_{1\dots n}$，选择 $i_{1\dots k}$ 和 $j_{1\dots k}$，使得 $i_p\le j_p$，最小化 $\sum (a_{i_p}+b_{j_p})$。

Medium $1\le k\le n\le 2200$ 4s

Hard $1\le k\le n\le 500000$ 10s

Read More

Description

我们称相邻字符不同的字符串是美丽的。

给定字符串 $s_{1\dots n}$，每次操作可以删除 $s$ 的一个美丽子串，剩下的字符会按照原来的顺序拼接起来。

求将 $s$ 变成空串的最小步数。

$n\le2\times10^5$

Read More