CSP2019前的做题记录 & 每日小结

其他

这里是 CSP2019 前的做题记录 & 每日小结！

每天计划如下：

  1. 订正monisai！
  2. ATC一套（2 ~ 3道）
  3. 随即开题 >= 3 道
  4. 算法针对 >= 3 道
  5. 博客总结
  6. 博客回顾 >= 10 篇
  7. 后期安排 NOIp 真题体验

日拱一卒无有尽，功不唐捐终入海！加油加油~

——-

10.29

  • ⚠️monisai T2 模数有一重没加，全wa丢40+。。

luogu3586, agc037C, abc144D+E+F, bzoj1016

10.30

  • ⚠️monisai T1 无向边建成有向的了凉凉。。（奇怪，以前从来不犯的错误啊 o(╥﹏╥)o

luogu3317, luogu1131, luogu1879

10.31

abc137E, bzoj4805, bzoj2005, bzoj2671, luogu2219, luogu2569, luogu2709

11.1

  • ⚠️用着可以 O(n^2 + Q) 的部分分写法，写了 O(n^2 + Qn) 的。。虽然也不会太凉，但是正式比赛一定要小心啊！（别想出正解写了暴力就是了qwq

luogu3172, luogu3830, luogu2613, bzoj1531

11.2

  • 今日份快乐：monisai烤了10.17日的模拟赛T3，然鹅我并没订正过这道清真的斜率优化。。然后我调出来了，耶。
  • 形如 a = b 的东西可以化成 a - b = 0, 也许可以用数据结构维护呢。
  • ⚠️monisai T1 矩阵加速丢 30 pts，原来是 ll 类型的 n 被我用 %d 输入了。。。检查 long long 🈶️🈚️开不只是检查定义处，还有输入输出处哇。。。两个字母三十分 o(╥﹏╥)o 超贵

luogu2915, luogu2150

11.3

  • 今日份快乐：在家休息哦！补觉啦【快快乐乐】然后复习了dp！

bzoj1037, bzoj1042, bzoj1084, bzoj2431, bzoj1190

11.4

  • 今天早上音乐抽到我了，，于是就没有去训练，在家 vp 了 CF round 597 (Div2)

bzoj1833

11.5

  • ⚠️今！天！又！爆！int！了！下次用 #define ing long long 吧
  • T2 可以 AC 的。。vector 定义成 int 类型了，爆了，什么都不想说了，T2 没有了还活个什么劲啊
  • 以下是一些牢骚：诶为什么人家 fst 都是小 f 啊，就我是大 f ？一次 f 100 的那种？水逆特别眷顾我吗 qaq… 要么脑子少一块了🧠

cf997e, bzoj3209, luogu4999

11.6

对于二分图：

  • 最小点覆盖 = 最大匹配
  • 最大独立集 = 最小边覆盖 = 顶点数 - 最小点覆盖（最大匹配）

对于DAG：

  • 最小不相交路径覆盖 = 原图顶点数 - 转为二分图后的最大匹配数
  • 最小可相交路径覆盖 转化转化能变成上面那个。转化方法：用 floyd 求出原图传递闭包，如果 a 到 b 有路径，就加边 a-> b, 就行了。（这样就不用经过中间点了，如果经过中间点有可能会与其它路径相交。）

概念：

  • 最大匹配：二分图中边集的数目最大的那个匹配；
  • 最小点覆盖：用最少的点，让每条边都至少和其中一个点关联；
  • 最小边覆盖：用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点；
  • 最大独立集：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。

bzoj1082, bzoj1179

11.7

bzoj1143, bzoj3175, bzoj2783, bzoj3190

11.8

  • ⚠️给 trick 坑了！（这算 trick 吗）：对于每个质因数 p，将所有能被它分解的 a[i] 提到 vector 里。这样处理每个 p 就只会用到 vector 里的 a[i] 了。每个 a[i] 最多被提 sqrt(a[i]) 次（其实远远达不到），复杂度就由 O(质数个数 ✖️n) 变为 O(n ✖️根号n) 了（哭倒。。。

agc036A

11.9

  • ⚠️T2 想打的部分分没写出来，提交时还没删掉那部分程序，居然 CE 了。。30 分啊。。唯一一次能比 xyr 高的机会。。。被我自己作没了。。。。

agc036B, bzoj1027,

11.10

  • 打了 xj 的一场模拟赛 + ez dalao 出的一场 comet。感想：bitset 真是个好东西 + 我好菜啊qwq

11.11

  • 双十一块乐！

bzoj1027, luogu2680, 然后切了一些历年真题的水题啦

11.12

  • ⚠️每日一fst：二分要注意答案是否有机会为 0 或有可能超过 int 范围！
  • 今日份块乐：有生之年订完了monisai（其实不是第一回qwq）220pts信心赛可 🌊🌟

bzoj1295, luogu3960

11.13

  • 调代码的时候被一些 傻【数据删除】手误给坑了一个多小时。。ㆁᴗㆁ绝了
  • 判断一些东西的时候可以借用另一些比较有用的有特征的东西（我在说什么啊），比如 tarjan 题就离不开 dfn 和 low。

luogu1600, loj114, luogu2827,

11.14

  • 今日份加倍快乐：monisai登顶，有生之年系列（其实只是 1 pts 都没 fst 而已 qwq
  • 后天的 CSP 信心瞬间加满！CSP 2019 RP += (inf) ^ {inf} !!!
  • CSP 时要仔细啊，别 fst 了！
  • 读完题后一定会懵的，此时不妨写写画画，模拟一些小样例，说不定就看破出题人的意思了。

luogu2679, luogu1155, bzoj1823, bzoj1718

11.15

bzoj1305, bzoj2424, bzoj1923,