wz刷题汇总

个人刷题记录（不完全）

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