树上启发式合并 树上启发式合并 注意事项:多测时,需要清空dfn和big,同时要将对根的 dfs1 的 keep 标记置为 0。 树上启发式合并一般解决的是不带修改对子树内的询问,可以通过对所有儿子暴力求答案,但删除轻儿子的结果,保留重儿子的结果,从而保证了复杂度。 树上启发式合并的流程为: 遍历轻子树,递归求解答案,不保留它们的影响。 遍历重子树,递归求解答案,保留它们的影响。 再遍历轻子树,保留它们的影响。 2023-07-06 ACM #树上启发式合并
Codeforces Round 856 (Div. 2) 题目质量很好的一场比赛。 D. Counting Factorizations 题意 一个整数的唯一分解形式为 m=∏i=1kpieim=\prod\limits_{i=1}^kp_i^{e_i}m=i=1∏kpiei。我们记集合 f(m)={p1,e1,p2,e2,⋯ ,pk,ek}f(m)=\{p_1,e_1,p_2,e_2,\cdots,p_k,e_k\}f(m)={p1,e1,p 2023-07-06 ACM #生成函数 #哈希 #换根dp
Codeforces Round 861 (Div. 2) 比较难的一场比赛。 C. Unlucky Numbers 题意 定义一个整数的幸运值为其数位中的最大值减去最小值。求区间 [l,r][l,r][l,r] 内幸运值最小的数。 题解 比较特殊的数位dp。由于不是求数量,所以不能用前缀和来做。这时,在dp中需要同时设置上界和下界。其它区别就不大了。 代码 1234567891011121314151617181920212223242526272829 2023-07-04 ACM #数位dp
AtCoder Regular Contest 163 C - Harmonic Mean 题意 要求构造一个长度为 nnn 的一个数组 aaa,满足以下条件: ∑i=1n1ai=1\sum\limits_{i=1}^n\dfrac{1}{a_i}=1i=1∑nai1=1 aaa 中的元素各不相同 1≤ai≤1091\leq a_i\leq 10^91≤ai≤109 题解 利用 1k(k+1)=1k−1k+1\dfrac{1}{k(k+1) 2023-07-03 ACM #构造
AtCoder Beginner Contest 308 G - Minimum Xor Pair Query 题意 给出一个初始为空的可重集合和三种操作。 插入一个数; 删除一个数; 输出集合内任取两数异或的最小值。 题解 一个重要的性质是:若 x<y<zx<y<zx<y<z,则 min(x⊕y,y⊕z)<x⊕z\min(x\oplus y,y\oplus z)<x\oplus zmin(x⊕y,y 2023-07-02 ACM #异或
AtCoder Regular Contest 162 C - Mex Game on Tree 题意 给出一棵树,其中一些点标有数字。Alice和Bob轮流给剩下的点标数字,如果最终有一棵子树的所有结点 mex\mathrm{mex}mex 为 kkk,则Alice胜,否则Bob胜。要求判断两人最优操作下谁能获胜。 题解 很直观的想法是Bob每次操作都会填入 kkk,而若一棵子树中存在一个结点数字为 kkk,那么这棵子树的 mex\mathrm{me 2023-07-01 ACM #博弈 #树上启发式合并
点分治 点分治 点分治常用于解决树上路径统计问题。它的基本思路是:选定某个点 uuu,将路径划分为经过 uuu 和不经过 uuu 两类。对于前一种,我们直接处理。对于后一种,我们递归,在子树中处理。 首先要解决的是递归的层数,考虑一条链,如果从链的一端开始,每次向子结点递归,那么递归层数是 O(n)O(n)O(n) 的。解决方法是每次选取重心进行递归:即先处理整棵树的重心,然后递归处理每棵子树的重心。这样 2023-06-29 ACM #点分治
Educational Codeforces Round 151 (Rated for Div. 2) D. Rating System 题意 给出一个得分序列。可以设定一个 kkk,使得分数到达 kkk 后不会再低于 kkk。求一个 kkk 使得最终得分最大。 题解 显然 kkk 应该为得分序列前缀和中的一个。对于给定的 k=sumik=sum_ik=sumi,必然存在一个位置 j∈[i,n]j\in[i,n]j∈[i,n],使得从该位置往后得分不再小于 kkk。所以我们直接维护后缀最大值即可( 2023-06-29 ACM #dp #前缀和
CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) E. Tenzing and Triangle 题意 在网格图 0≤x,y,x+y<k0\leq x,y,x+y< k0≤x,y,x+y<k 范围内有一些格点,每个点有点权。每次可以以 x+y=kx+y=kx+y=k 为斜边,圈定一个等腰直角三角形,消除范围内的点的点权,代价为 AAA 乘直角边长。也可以以某点点权为代价,消除该点。 问消除所有点的最小代价。 题解 我们用斜边表示 2023-06-27 ACM #线段树优化dp #树的重心
AtCoder Regular Contest 161 C - Dyed by Majority (Odd Tree) 题意 给定一棵树,保证每个点的度数都是奇数。对树上的结点进行黑白染色。现给出目标颜色序列,要求找到一个初始颜色序列,使得经一次操作后得到目标颜色序列。 操作定义为:对每个结点,记目标颜色为与它相邻的结点中超过半数所具有的颜色。将所有结点的颜色同时修改为目标颜色。 题解 从特殊情况入手。考虑叶子结点和它的父亲。显然,具有相同父亲的叶子结 2023-06-23 ACM #贪心 #随机 #2-sat