Asusetic
0%

2021.10.06模拟赛

发表于 分类于 Valine：
本文字数： 695 阅读时长 ≈ 1 分钟

Somewhere surrounded by the night, the sun will shine

2021.10.06 模拟赛

A. string

string

很像是 HEOI2016 排序，但是有 2626 个字母 开26个线段树

开二十六个线段树或者每个节点开一个 2626 大小的数组是可行的，不过我常数太大了，所以用了奇怪的方法

线段树上如果当前段全是一个颜色就记录一下，数量就是 r−l+1r-l+1 ，如果不是就继续递归

直觉上排序之后会变得有序，所以不会暴力扫的太多，大概可以用势能一类的证明复杂度？(或者Hack我)

code

B. water

water

比较优秀的想法是最小生成树，不过可以有不优秀的想法

考虑每个点能蓄水就是他四周的最低的比他高的那个 vv 减去他的hx,yh_{x,y} ，所以我们开个小根堆去 BFS，但是要考虑蓄水状态可以继承，所以每次放到堆里的是 max⁡(hx,y,v)\max(h_{x,y},v)

code

C. number

number

设一个暴力的状态 (i,S,k)(i,S,k)表示当前第 ii 位，0...90...9 的次数状态为 SS ,  mod m=k\bmod m =k 的方案

第一个问题是 SS 怎么压，因为题目保证了 n≤20n \le 20 ，可以考虑变进制状压，每一位的进制是出现的次数，这样最多是 3103^{10} 的状态

然后发现复杂度过不去，要跑 55 s，但其实发现没必要记录 ii 这一维，因为 SS 必然是从小到大转移，这样就是 O(31010m)O(3^{10}10m) 的复杂度

code