2019-07-06 23:32:33    294    0    0
Maybe the last codeforces round. A Subtask 1 若不存在度数为 2" role="presentation" style="position: relative;">222 的点,则一定有解;反之无解。My code. Subtask 2 最终边权只会是 even intergereven \ interger。 考虑一条边 (u,v)(u,v) 最终要变成 2x2x 。这条边把树分为两棵树。 u,vu,v 都是叶子只会发生在 n=2n=2 ,特判。 若其中一个是叶子,不妨 vv 为叶
动态dp dp fwt 数据结构 树链剖分    2019-05-21 13:59:41    10    0    0
Problem 给出一棵无根树 T" role="presentation" style="position: relative;">TTT,节点从 1" role="presentation" style="position: relative;">111 到 n" role="presentation" style="position: relative;">nnn 编号,点 i" role="presentation" style="position: relative;">iii 的权值为 vi" role="presentation" style="posi
数据结构 差分 cdq分治    2019-05-21 13:20:51    203    0    0
#44 核能显示屏 题意:矩形加,矩形求和。 不妨设只求二维前缀和。 设求和矩形大小为 N×M" role="presentation" style="position: relative;">N×MN×MN \times M 。 将整个矩形差分。那么矩形加只涉及 4" role="presentation" style="position: relative;">444 个点。查询时一个点的权值即二维前缀和。 考虑一个点 (x,y)" role="presentation" style="position: relative;">(x,y)(
线段树    2019-04-02 07:41:02    776    0    0
Solution 原问题相当于有 m" role="presentation" style="position: relative;">mmm 次给线段树区间 [ql,qr]" role="presentation" style="position: relative;">[ql,qr][ql,qr][ql,qr] 打标记 1" role="presentation" style="position: relative;">111 的操作,每个操作等概率做或不做。这样就有 2m" role="presentation" style="position: relative;"
数学 高斯消元 期望 递推    2019-03-18 17:20:03    258    0    0
令 f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]f[i][j] 为从 (i,j)" role="presentation" style="position: relative;">(i,j)(i,j)(i,j) 走到第 n" role="presentation" style="position: relative;">nnn 行的期望步数。 对于 i∈[1,n−1]" role="presentation" style="posi
2019-03-07 11:30:09    142    0    0
Link http://codeforces.com/gym/102056/problem/K Problem 给一个长度为 n" role="presentation" style="position: relative;">nnn 的序列 ai" role="presentation" style="position: relative;">aiaia_i 。如果相邻两个数相同(为 x" role="presentation" style="position: relative;">xxx ),那么我们可以把它们合并为一个 x+1" role="present
构造 交互题    2019-02-02 21:57:11    459    0    0
Problem 有 n" role="presentation" style="position: relative;">nnn 个物品,每个物品价格要么是 0" role="presentation" style="position: relative;">000 要么是 1" role="presentation" style="position: relative;">111 。 已知 1" role="presentation" style="position: relative;">111 个数的奇偶性,且保证至少存在 1" role="presentat
dp 组合数学    2018-11-25 10:48:29    364    0    0
Problem n" role="presentation" style="position: relative;">nnn 个位置,每个位置 i" role="presentation" style="position: relative;">iii 可以填一个 [ai,bi]" role="presentation" style="position: relative;">[ai,bi][ai,bi][a_i,b_i] 间的数或者填 0" role="presentation" style="position: relative;">000 。问有多少种方案,使得
数据结构 LCT    2018-11-19 15:40:55    555    0    0
Problem 题面戳这里~ Solution 考虑如下两个性质。 询问可以放在所有对于这棵被询问的树的修改操作的后面。因为一旦这两个点出现了,距离就固定了。 对于 1 操作换生长节点,我们就给它建一个虚点,以后在它上面的生长,我们就挂在虚点下面了。(这样方便添加和撤销) 实在不知道怎么说了,代码里写了算法流程。 Code #include <cstdio>#include <cstring>#include <algorithm>inline char gc() { static char now[1
dp 动态dp treedp    2018-11-18 09:21:54    762    0    0
Problem n" role="presentation" style="position: relative;">nnn 个点的有点权树,有 m" role="presentation" style="position: relative;">mmm 次询问。 询问形如 a&#xA0;x&#xA0;b&#xA0;y" role="presentation" style="position: relative;">a x b ya x b ya \ x \ b \ y,其中 x,y&am
文档导航