补题 list


计数

一道树上计数

2018 Qingdao L (可容斥可指数生成函数)

督导给出计数题之一

督导给出计数题之二(H)

毒瘤生成函数

指数生成函数 + 分治 fft

有趣的计数,Singapore g

好像一个很强的计数?HDU Day2 1001,棋盘上一些直线相交的整数点不能经过

稍微硬核的组合数学

硬核计数

计计计数

字符串

个人排位#6 hash 维护前后缀

hash 求 lcp 然后开搞,牛客多校第一场 G

SAM 妙用,HDU Day1 1006

SAM 后缀树启发式合并 + 主席树

SAM + 求贡献

后缀数组

二分 + hash

hhhhhhash

dp

dp + 拉格朗日插值

dp + 线段树,牛客多校第一场 I

关于树重心 dp 一

关于树重心 dp 二

四边形 dp(单调性 dp)

dp + BM 线性递推,牛客第二场 B

有点难的 dp ?牛客第二场 I

$dp[i][j][k][t]$大概挺好补的 HDU Day1 1001

非法状态较多的区间 dp,跑记忆化比较快

离散化 + 背包,背包合并,第一行特殊处理,好像有点难?HDU Day1 1003

最长山峰子序列,同时要求字典序最小 HDU Day2 1002

环上走路

结论,dp 做中位数求一个方案,牛客第三场 I

计数 dp,或者应该叫计数?,牛客第四场 E

树 dp,维护删边与否,最大,次大,第三大,与父亲相连最大,HDU Day3 K

硬核数位 dp

诡异 dp,可二分转移,也可线性

撤销背包 dp

数据结构

线段树合并

启发式

线段树维护矩阵

Kruskal 重构树

平衡树 or 线段树分裂?好像有点难,牛客第四场 F

三维莫队?带修改莫队?HDU Day3 H

硬核树剖,或者 LCT

用 set 维护时间,然后再用个线段树维护其他信息?

维护 8 个象限,三维 BIT

策略 + 线段树上二分

图论

点分计数

二分 + 网络流

nb 点分树?Dhaka G

有点巧妙的秃论

dsu on tree

dsu on tree again

长链剖分 +最小割

点分 + dp

稳定婚姻模型

simply 秃论

计算几何

好像有点牛逼的几何?给出 n 条直线求有多少个闭合多边形,求最小最大,求 k 大

求两个凸包是否有交,学一下闵科夫斯基和

三维几何求两个三角形平面最短距离 I

又是一道很强的计算几何,给出一个凸多边形,让你切一刀使得凸多边形变成面积相同的两部分,输出最长的线段和最短的线段 F

几几几几几几几几几何

有点东西的几何

数学

好像是数论函数前缀和,带个二分 HDU Day1 1007

HDU Day1 1011,开立方根

多项式,HDU Day1 1012

多项式经典问题?看题解好像推了好多东西 HDU Day2 1003

数数数数数数数数数数学

推导 + 杜教筛

二次剩余

诡异的推导,貌似做法很多?

思维 + 类欧几里得

min25

杂项

fwt 枚举子集乱搞(Solved by purple_bro)

Dhaka A,求平均数第 K 大,好像值得补

你好又是 fwt,牛客多校第一场 D

图边权随机化

随机,模拟 fib

倍。。。倍增?

bitset 搞,牛客第二场 D

好似乱搞?牛客第二场 J

博弈?HDU Day2 1007

CTF 最短路

线性规划 or 乱搞

数形结合,好像有点难?

构造

分段打表。。。

带点技巧的 meet in the middle

分析 + 矩阵快速幂,注意爆 long long

博弈 + 二分图