联合省选 2021 Day2 白给记

# Day 1 提前 15min 进场，然后开始码码码，公布密码的时候码完了缺省源和半个对拍 。 ~~密码输错x1~~看题ing，注意到了 t1 数据范围的~~毒瘤~~递增，ds 题，看完差不多有点思路了，瞬间信心倍增 t2 构造，还是我连 subtask1 都不会的那种，t3 更？，这真的能做？只会 16 分 。 然后花了 2h 写了个 T1，期间一边写一边优化一边拍~~（给高速行驶的车换轮子）~~，极限数据测了下 1.8s 艹，然后发现读入花了 1.2s 期间发现大样例 3 极其水，怎么写都能过。。。 然后写了个 T3 16分，分析了半天复杂度是 $\mathcal O(n^2m^2)$ 的？然后想了 10min 不会优化去写最不可做的 t2。 t2 这个 subtask1 是给啥算法写的。。。直接从部分分想起了，m=2 发现可以转换为一个 1 维的问题，瞎写了写然后过了拍， 吐槽没发checker，然后爆搜瞎剪枝就搁在那了。 还剩 30min。在 t2 的 0/1 和 t3 的 44 之间来回想，还是没啥。 顺便说下我 A 的做法： 枚举翻完卡牌后的最小值 $min$ ，如果存在一个 $a_i,b_i<min$ ，那么直接 break，否则分 $a_i<b_i$ 和 $a_i>b_i$ 讨论 $a_i<b_i$ 当然是能不翻就不翻，那么搞个能删除的堆 $pq$ 来维护这些的 $\max a_i$ ，当 $a_i<min$ 的时候说明这个卡牌必须翻了， 那么就把他从堆中删了，然后 $L=\max\{L,b_i\}$ ， $m\leftarrow m-1$ ，这部分在 $min$ 为最小值的时候最大值为 $A=\max \{L,pq.top()\}$。 $a_i>b_i$ 那当然是尽量让 $a_i$ 大的翻，那么就以 $a_i$ 为下标建立权值线段树，维护区间 $\max b_i$ 和数的个数，那么就是从 1e9 开始往前 $m$ 个取 $\max b_i$ ，剩下的都是 $a_i$ ，这两个的最大值记为 $trmax$ ，如果出现 $b_i<min$ 那么说明这个卡牌不能翻转， 那就从线段树中删了这个然后 $R=\max \{R,a_i\}$，这部分在 $min$ 为最小值的时候最大值为 $B=\max \{R,trmax\}$。 如果 $m<0$ 那么就 break，否则就 $ans\leftarrow \min\{ans,\max\{A,B\}-min\}$ 时间复杂度 $\mathcal O(n\log n)$ t2 第一个 subtask 直接写了爆搜 + 剪枝，$m=2$ 的 subtask 我的做法比较怪一点： 设 $S_i=a_{i,1}+a_{i,2}, M_j=b_{j,1}$，那么有 $M_i\le S_i+S_{i+1}\le M_i$ 设 $L_i\le S_i\le R_i$，那么我们显然可以通过 $L_i,R_i$ 来推出 $L_{i+1},R_{i+1}$，然后 $L_1=0,R_1=2e6$ ， 中间一旦推出 $L_i>R_i$ 那么直接输出 `NO`。然后我们来撕烤怎么构造方案。 由于 $L,R$ 越到后面约束越紧，所以显然是现决定后面的再倒推构造，大概就是这样（可能假了qwq）。 t3 只会暴力，所以省选 day1 就 $(70\sim100)+(0\sim 50)+16$ 白给了。 其他： t2没想到能差分约束，t3 n2m 的做法似乎是最短路？？？ t1 n2 对拍拍上的时候上了个厕所，t1 写完的时候上了个厕所，t2 50分写完的时候上了个厕所，时间分别是 1h 2h 4h（越来越逊）。 t1 连拍带写共 2h，感觉能再压一点？~~（重蹈csp覆辙）~~ 最后20min ， t2 想到了 2-SAT 的假做法，打了一半发现是错的，这似乎是个 4-SAT 问题。。。 # Day2 白给场，~~雨天感觉有点闷，拖了个外套，今天说不能提前写代码了，所以缺省源只写了一半~~ 看完题，t1 是个 ds，t2 看上去是个状压 dp，t3 图论， 先开的 t2 花了 15min 推了个 $\mathcal O(2^nn^2m^2)$ 的 dp 出来，码了一半突然一看部分分，直接全排列都有 60 分。。。于是弃了 dp 先写了个 60 分的暴力出来，样例全过，然后想了想这个 dp 也没啥可以优化的，去看 t1。 t1 读完题手玩了下发现就是求一个链上最长上升子序列，然后我发现向上爬很简单，向下爬怎么搞。。。想了一下直接二分就是 $\mathcal O(n\log n \log m)$ 的，估算了一下常数发现完全过不了，甚至只能拿 50 分，然后就写了个 25 分暴力，顺便想了想序列上的部分分的做法，好像有个分块的思路，先去看t3了。 ~~看完 t3 又感觉是维护动态图连通性~~，先写了个 30pts 暴力，然后感觉树的15分很可做，瞎猜了个结论，对拍 wa on test 1，上了个厕所（今天一个机房还得回来一个出去一个。。。）会来冷静分析了一下发现没那么简单。手玩了十多分钟讨论了 11 种情况，码了 100 多行过了对拍。。。 还剩 1h30min，t1 序列上的做法大概会了，直接分块维护就行 $\mathcal O(n\sqrt n)$ ，码了 1h 过了对拍。 还剩 30min，现在是 $45+60+45$ ，特别爆蛋，去想了下 t2 还是不会。 最后 20min 突然想到了 t1 两个 log 的做法是不是能过 $m\le 300$ 的。。。但是没时间了， 然后快速想了一个 $\mathcal O(nm\log n)$ 的做法，树剖 + set ，很好写， 最后 1min 过了样例 3，没时间卡常了qwq。 预估 $70+60+45$ 出来一问，果然人均切 t1，好多人 2log 真的不怕被卡成 50 分么。。。wcr写的 1log 都 400ms 了。 回 sxyz 测了测某人的数据，挂飞了。。。$100+30+20+60+60+35=305$，挂了 40 分 /px d1t2 0/1 和 sub1 一个都没拿到，果然随机数据都能卡掉搜索剪枝。。。d1t3 多了 4 分，数据问题 d2t1 果然被卡常，目测 ccf 机子得挂成 50，d2t3 没注意到 sub1 的 $q\le 2\times 10^4$ ，白给 10 分 最低可能标准分 $0.51$ ... 裂开 # Day N 出分了，$100+50+16+45+60+45=316$，算了下标准分 $0.56$ ，死透了