个人刷题记录（不完全）
cf-contests
存一些让我再写不一定写得来的或者我可能去扒原题的?
1202D d3线下想的数学题
1214D dfs可以搞 两次dfs 第一次把走过的路堵上(“D不是dinic板子题?”)
1217B 是我最讨厌的打怪兽 但是做太多这种了… 要特判一次打死(wcy赛时四题睡前三题醒来两题那场)
1209D 奇怪的并查集
1220B 每个ansi为sqrt(ai*ai/aj)
1221D dp 增高栏杆使没有相同高度 只可能增012
1251C ai和aj奇偶性不同可以交换 问字典序最小 奇偶分别存一个数组里 sort 然后贪心输出
1252H 这b卡double精度
1256A-F 自己博客
1257D 贪心打怪兽
1253D dfs求每个点能到mn和mx 再for一遍补
1265A-E 自己博客
…
1295C 我最怕的二分题 多次选s的子序列加起来使最后结果等于t 问最少几次 开个cnt26去二分
1295D 问有多少0<=x<=m-1%%gcd(a,m)==gcd(a x,m) 结论题 求gcd(a,m)的phi
1300E 任意选区间使区间中所有数变成区间平均数 问字典序最小什么样 贪心 算不算单调栈? for一下遇到小的就去和前面的平均
1301D 自己博客
1303C dfs 给你s问有没有合适的单行键盘序列使每次按都只用移一格
1303D 袋子容量n 给你m个2^ki的物体 问最少拆几次能填满
1304D 构造 给你<和>代表数组递增或者递减 求LIS的最小/最大情况 最小情况就增得少减得多 最大反过来 离散化后就是答案
1305E 构造 递增数列且刚好k个三元组(i,j,k)满足ai aj=ak
1307D 加一条边使加后的1到n最短路最长 跑一遍所有点到1/n的最短路 根据差值排序 然后for
1311D 暴力枚举 范围是坑 给abc问最少加减一次使b%a==0&&c%b==0
1312E 区间dp 两项相邻的相同可以合并成一项比原来大1的值 问最少剩下
1315D 奇怪的并查集 根据时间大到小sort 并查集判点是否出现过
1316D 带模拟
1316E 状压dp 每个人可以选两种身份 贡献是a和b 选p个1身份和k个2身份的人使总贡献最大
1321A-D 自己博客
1326D2 自己博客
1327D 置换群 给p找最小k使p^k存在颜色相同的环 找环后枚举因数再枚举所在环是不是颜色相同
cf-strings/hashing
5C 常见括号匹配 单调栈板子题
7D 自己博客
8A implementation 题意有点难懂 正着find倒着find就完了
25E kmp/hash板子题 多个串省略重复地相连
31B implementation greedy?合法只要是两个@相差2 注意首尾
34C 断句题 断完了就implementation
39J 给定串s和t 问s能不能删一个字符得到t hash完了for一下
58D sort题 sort完暴力找匹配
70B 恶心人的题 带模拟
75B 断句 sort 模拟就完了
432D kmp预处理后o1查某个前缀出现几次
471D 差分后kmp一遍
526D kmp 很考对nex的理解?
985F 给出串s 每次询问以x和y为起点长度len的s子串字符能否形成一一映射 hashmaxn记录 每次求出两个段每个字符的hash值 sort完一一比较
1200E 字符串合并 hash/kmp板子
1204D2 比较精妙的构造?
cf-string suffix structures
19C 自己博客
123D 求所有子串出现次数和 sam板子
128B 求第k小字典序子串的sa/sam板子
cf-geometry
1C 海伦公式 正弦定理 余弦定理 double求gcd
14C 给四个线段问能不能组成矩形 记个数
18A 给三个点问能不能组成或者移一个点组成直角三角形 forforfor
183B 这才1700?虽然是n3暴力
190B 求和两个圆相切的圆的半径
cf-number theory
7C exgcd
10C 求出每位数有几个 然后加上所有组合 再扣掉合法组合
16C 就这?没有binary search 所谓number theory只是gcd罢了
17A 问2-n有几个符合题意的数 筛出素数然后暴力
17D 十进制ksm板子题
26A 就这2400?暴力完事
27E 反素数板子题
45G 哥德巴赫猜想(一个偶数为两个质数相加)?先判单色 枚举质数看能不能双色 不能的话肯定是奇数 -3 剩下的再枚举
55D 数位dp 离散化 dp开202520 2520是1-9的lcm 有48个因数 对每个lcm离散化 搜到最后合法情况就是mod%lcm==0
66D 简单构造
71C 枚举i到n/3(三角形) 每个n%i==0判合不合法
73E 有1选1 没1选n内所有质数(不包含) 太大特判
75C 求完gcd因数对于每个询问查找 暴力就行
74C 很玄学反正求个gcd就没了
78C 单根木头能分解并且木头总数是奇数 先手胜
pta-problemset
L1-064 自己博客 猛男带模拟
hdoj-problemset
1439 置换群 找环记录环长 每次跳k余当前位所在环长次后的位置赋值si
2838 树状数组 记录逆序对数和前缀和 每次存在逆序对的时候累加
2486 k倍博弈板子
1402 大数相乘 fft板子 Java快读板子
2065 递推 推不出具体公式能找规律 循环节为20
4609 fft板子 通过fft算出所有两个数和的可能个数(?表述可能不是很清 想不起来可以看kuangbin博客) 减去选相同的 再总方案减可以构成三角形的
1403 sa/sam板子 lcs
