P9058 [Ynoi2004] rpmtdq 题解
Description 给定一棵有边权的无根树，需要回答一些询问。 定义 dist(i,j)\texttt{dist(i,j)}dist(i,j) 代表树上点 iii 和点 jjj 之间的距离。 对于每一组询问，会给出 l,rl,rl,r，你需要输出 min(dist(i,j))\min(\texttt{dist(i,j)})min(dist(i,j)) 其中 l≤i<j≤rl\leq
UOJ #514. 【UR #19】通用测评号
Description 有 nnn 个管道，每个管道的最大大小为 aaa，每次等概率随机选一个没满的管道里放一个石子，当所有管道的大小都 ≥b\geq b≥b 时停止，问装满的管道的期望个数，与 998244353998244353998244353 取模。 1≤n≤250,1≤b<a≤2501 \le n \le 250,1 \le b < a \le 2501≤n≤250,1≤b
P9731 [CEOI2023] Balance 题解
Description 由于黑客对评测机的攻击，组委会决定重测所有提交记录。 有 NNN 台评测机，TTT 个题目（编号为 1,2,⋯ ,T1, 2, \cdots, T1,2,⋯,T）。组委会已经确定，每台评测机要评测哪些提交（数目相同，都是 SSS 个提交，保证 SSS 是 222 的整数次幂）。在接下来的 SSS 分钟内，每分钟每台评测机会评测一个提交。 每个提交都会提交至某个题目。由于存
Public Easy Round #2 E. 2048
Description pb 大师喜欢玩 2048。 pb 大师在一个 1×n1\times n1×n 的网格上玩 2048，初始 nnn 个格子都是空的。 游戏会进行若干轮，每轮将发生如下事件： 如果没有空位，游戏结束。否则随机一个 111 到 mmm 的数，随机到 iii 的概率是 pip_ipi，再等概率随机一个空位，在空位中填入 2i−12^i−12i−1。 将所有数顺序不变移
prufer 序列
定义：prufer序列是树和序列的双向映射，prufer 序列描述了节点的度数以及父节点的信息。 使用场景：将构造树的问题转化为构造序列，将统计树的问题转化为统计序列，将树的 dp 转化为序列的 dp。 如何得到 prufer 序列： 统计树上所有结点的 degree. 找到度数为 1 的最小的点把他的父亲加到 prufer 序列并删掉他。 重复 2 直到只剩两个点。 性质： 剩余两个点中一
P10218 [省选联考 2024] 魔法手杖 题解
Description 给定 a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an 以及 b1,b2,…,bnb_1,b_2,\dots,b_nb1,b2,…,bn，满足 ai∈[0,2k−1]a_i \in [0,2^k-1]ai∈[0,2k−1] 以及 bi≥0b_i\geq 0bi≥0，你需要给出 S⊆{1,2,…,n}S \subseteq \{1,
HNOI2024 游记
Day 0 机房打摆，早上扫雷但是离 xkr 的记录差的有点远，很自闭。 一天就写了 fft 和 ntt。 晚上有点失眠。 Day 1 带了东鹏特饮和巧克力就去考试了。 T1 发现直接枚举 m mod nm\bmod nmmodn 的值然后解方程就行，25 分钟过了大样例，然后对着代码瞪了 10 分钟发现没什么错误就丢掉了。 T2 想了一下发现可以二分，想着先写暴力再想正解，于是很快写完 2
[AGC018F] Two Trees 题解
Description 给定两棵都是 nnn 个节点的有根树 A,BA,BA,B，节点均从 1..n1..n1..n 标号。 我们需要给每个标号定一个权值，使在两棵树上均满足任意节点子树权值和为 111 或 −1-1−1。 输出任意一种解，需要判断无解。 1≤n≤1051\leq n\leq 10^51≤n≤105。 Solution 注意到每个点权值的奇偶性是确定的，所以如果两棵树对应点的奇