联合省选 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 讨论

那么就把他从堆中删了，然后 $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 ，死透了