当前位置：网站首页>8.9模拟赛总结

8.9模拟赛总结

2022-08-10 16:41:00 【Flame*】

我最近好嗜睡啊…

今天睡眠10h+甚至

晚上八小时+ 早上断断续续打瞌睡 中午一小时 嘎嘎（

时间安排

7.30-9.30

看题 不时打瞌睡） 看了半天2只会暴力 看了半天T3 感觉很sosdp 但是没啥想法）

9.30-11.30

打了T2 40 T3 20

11.30-12.30

猛地想明白T1的dp 然后猛冲）

题目分析

T1

f i , j , s f_{i,j,s} fi,j,s​ 考虑完第 ( i , j ) (i,j) (i,j) 位置 状态为 s s s

状态为：考虑上面往下有没有封口，前 j − 1 j-1 j−1位表示第 i i i 行 [ j , n ] [j,n] [j,n] 位表示第 i − 1 i-1 i−1 行

比如| | 这个就是0 因为没封口

比如|_| ，____这些就是1 因为封口了

然后转移有三类

对于一个封口/没封口的地方 往下形成一个| |

对于一个没封口的地方 封口 形成|_|

对于一段封口的[i,j] 形成_____

根据给出的原边 讨论一下能不能这么转移 代价是多少

upd

网络流 需要注意到性质 一个90度角的边至少要用一边

T2

赛场上感觉应该是按照n/(n+1) 先切割成若干段再做

但不知道具体怎么做

upd

很妙的贪心 考虑分成n段 没段维护最大次大 每次取次大值最大的那一段 然后把那一段删去，其他段的最大值ban掉

T3

要求就是 p ∈ x ∈ q p \in x \in q p∈x∈q

只会 p = 0 p=0 p=0 的sosdp

upd

毒蛇越狱 要注意到 sosdp是可以容斥容斥容斥的

原网站

版权声明
本文为[Flame*]所创，转载请带上原文链接，感谢
https://blog.csdn.net/m0_50170681/article/details/126266647

边栏推荐

猜你喜欢

随机推荐