1. EC Final 2021

趣事：vp 开始后发现其实我之前在 2022.1 帮验过《EC Final Easy Version》好像做了 ABE，但都忘了，当时 20min 过的 B，现在好像看错题还罚时了三次。

https://board.xcpcio.com/icpc/46th/ec-final?group=official

Rank 16, 7 题 1052

Story

开局我把 ABI 签了（三发罚时，B 卡了半天，思路错了），deep_code 把 L（四发罚时）签了。然后我感觉 C 可做，乱卡了半天过了。xl 在做 E，分讨题我们都讨论不清楚容易错，很痛苦。deep_code 一直在计算几何 D(3.5h)，但是无从调代码。面对 J 题这种奇怪贪心我也不放心我写的是对的，wa 总犹豫是边界（代码）问题还是思路问题（三发罚时。好在最后 J 和 E 都过了。

Sol

https://www.cnblogs.com/Als123/p/16614701.html

https://codeforces.com/blog/entry/105449

C. String-dle Count

限制可以被刻化为每个字母出现次数要大于或者恰好等于某个数 \(L_i\)。\(\sum L_i \le k\)

之后我选择了枚举填哪个字母，再从前往后枚举位置，再 \(g[i][j]\) 记哪些位置填了和这个字母用了几次。写完才发现做法编的 \(O(2^kk^3)\) 但后来发现 \(j\) 大于下界的状态没意义可以合并，这样就是 \(O(2^kk^2)\) 了。 https://qoj.ac/submission/290181

但后来看题解发现这样其实没前途，就从前往后填位置，只记录满足了哪些下界被满足了多少，这样是划分数，硬卡上界是不如 01 的 \(2^k\) 的。然后就是这样一放发现比如 \(\sum L_i = u\)。那么只有 \(k-u\) 个位置可以对应着 \(2^k\) 个状态，那总共这样的复杂度确实是 \(O(2^k*(26+k)\)

刚学会的小技巧：计数划分数状态不用手写可以自己放大成每个选不选，最后再除以 \(\prod sz_i\) 就行了。

至于为啥直接填位置严格优秀也可以有点理解，这是个整体的结构，总信息对应着 \(k\) 。可以控制自由的位置，那如果按字母填记录个数好像就失去了整体的势（纯扯淡

G. Check Pattern is Bad

据说是乱搞题，循环贪心填，有坏掉的就急了，否则找到差一个 ? 填错就完了的把他填对，否则瞎填一个，好像就过了，为啥啊。不会证没理解也从来不觉得可以这么做

H. Check Pattern is Good

奇偶染色，奇的反转这样变成 \(2*2\) 纯色尽量多
黑白 \(2*2\) 是否可以实现当成点（\(2n^2\)），黑白之间填完是否有冲突当成边 \(n^2*9\)，二分图最大权独立集板子。

其实 1 不是必要的，看成两种形式也是可以的，不过 2 冲突是二分图就不好想（？

把需要最大化的目标状态当成点感觉非常自然，但我想到 1 没想到 2，为啥。

为啥写了 200 行 35min？

https://qoj.ac/submission/290991

考场瞎编的贪心：\(A \le B\) 最短路。\(A \le B\)\(A\le B\)\(A>B\) 先转成 \(i\) 在 \(C_i\) 时刻以后可以被解锁。然后感觉判无解就是每次随便选一个能扩展的扩展看能不能到 \(n\)。所以我感觉能不能怎么贪心选个对的。然后我觉得二分答案 \(\le x\)。然后类似 \(A \le B\) 倒着从 \(n\) ，\(d[n] = x\)，倒着最短路出 \(d[i]\) 表示从 \(i\) 到 \(n\) 最晚从哪天开始能到。感觉每次选 \(d\) 最大的走就很对啊！就感觉有那股劲，就是怕可以快速到 \(n\) 还搁着积累力量，这里找到了当且可能最快的（？？？