2020 沈阳补题记录（8 / 13）
2020 沈阳补题记录与部分题目题解
说起来 20 沈阳可能是唯一一场（没有算 EC）线下打的 xcpc 了，首先祝贺 TS1队四题拿银证明自己。
D. Journey to Un’Goro
tag
DFS
前缀和
题意
给定数 nnn ，要求求出满足条件的只含 b,rb, rb,r 的字符串的数量和字典序前 100100100 小的字符串。
其中字符串需满足的条件为：其中恰好包含奇数个 rrr 的子串数量最多。
其中 1≤n≤1051 \leq n \leq 10^51≤n≤105 。
思路
首先考虑如何计算给定串的满足条件的子串数量。
考虑用 0,10, 10,1 替换 b,rb, rb,r ，条件即转换为求和为奇数的字串数量。对转换后的串做一遍模 222 意义下的前缀和，满足条件的子串数量即为前缀和中的 0,10, 10,1 匹配对数（包括表示空前缀的 000 ）。
那么显然数量最大即为前缀和中 0,10, 10,1 数量最接近时，即前缀和中 111 的数量应为 n+12\frac{n + 1}{2}2n+1 或者 n2+1\frac{n}{2} + 12n+1。
那么这里已经找到了一个定量，因为只要求字典序前 100100100 小的字符串，暴力 DFS 时维护 111 的数量满足条件即可。
复杂度约为 O(100⋅n)O(100 \cdot n)O(100⋅n) 。
代码
123456789101112131415161718192021222324252627282930313233343536373839404142#include
F. Kobolds and Catacombs
tag
思维
题意
最多将给定长为 nnn 的序列分成多少段，使得每一段分别升序排序后整个序列是不降的。
其中 1≤n≤1061 \leq n \leq 10^61≤n≤106 。
思路
维护一个后缀最小值，从前往后贪心地划分，如果当前段的最大值小于等于当前后缀的最小值，就划分出一段即可。
代码
略。
G. The Witchwood
tag
排序
题意
输出给定长为 nnn 的序列的前 kkk 大的数之和。
其中 1≤k≤n≤1031 \leq k \leq n \leq 10^31≤k≤n≤103 。
思路
输出即可。
代码
略。
H. The Boomsday Project
tag
DP
双指针
题意
给出某人在 mmm 天内的租车情况 →\rightarrow→ 第 pip_ipi 天租了 qiq_iqi 辆车。
给出某人可以的租车方案 →\rightarrow→ 花费 rrr 块单独租一辆车或者花费一定价格买一张优惠卡。其中第 iii 张优惠卡需要花费 cic_ici 块，使用可以免去接下来 did_idi 天里最多 kik_iki 辆车的花费，总共有 nnn 种不同的优惠卡，同一种卡可以重复购买。
其中 1≤n≤5⋅102,1≤m≤105,1≤r≤109,1≤di,ki,ci≤109,0≤pi≤109,0≤qi≤3⋅105,∑i=1mqi≤3⋅1051 \leq n \leq 5 \cdot 10^2, 1 \leq m \leq 10^5, 1 \leq r \leq 10^9, 1 \leq d_i, k_i, c_i \leq 10^9, 0 \leq p_i \leq 10^9, 0 \leq q_i \leq 3 \cdot 10^5, \sum_{i=1}^{m} q_i \leq 3 \cdot 10^51≤n≤5⋅102,1≤m≤105,1≤r≤109,1≤di,ki,ci≤109,0≤pi≤109,0≤qi≤3⋅105,∑i=1mqi≤3⋅105 。
思路
首先观察到总共的租车数量比较小 →∑i=1mqi≤3⋅105\rightarrow \sum_{i=1}^{m} q_i \leq 3 \cdot 10^5→∑i=1mqi≤3⋅105 ，可以考虑将所有租的车按时间顺序排列出来 DP 。
具体实现为：
用 aia_iai 表示排序后第 iii 辆车被租的时间（单位为天）， dpidp_idpi 表示排序后租前 iii 辆车的最小花费，那么转移有两种情况：
不用优惠卡 →dp[i]=dp[i−1]+r\rightarrow dp[i] = dp[i - 1] + r→dp[i]=dp[i−1]+r 。
用优惠卡 →dp[i]=minj=1n(dp[x[j]]+c[j])\rightarrow dp[i] = \min_{j=1}^{n} (dp[x[j]] + c[j])→dp[i]=minj=1n(dp[x[j]]+c[j]) ，其中 xjx_jxj 表示对于第 jjj 张卡最小的 xxx 使得第 x+1x+1x+1 到第 iii 辆车都能被第 jjj 张卡作用到。考虑到 dpidp_idpi 本身是单调不降的，所以在最小的 xxx 处转移一定是最优的。
对于第一种情况直接转移即可。对于第二种情况，观察可以发现对于同一张卡 jjj ， iii 增大时 xjx_jxj 也是单调不降的，所以对于每一个 jjj 单独双指针维护一个 xjx_jxj 进行转移即可。
总复杂度为 O(n⋅∑qi)O(n \cdot \sum q_i)O(n⋅∑qi) 。
代码
1234567891011121314151617181920212223242526272829303132333435#include I. Rise of Shadows tag 数论 同余方程 题意 某地一天有 HHH 小时，一小时有 MMM 分钟，给出角度 α=2⋅π⋅AH⋅M\alpha = \frac{2 \cdot \pi \cdot A}{H \cdot M}α=H⋅M2⋅π⋅A ，问一天中有多少个整数分时刻时针与分针的夹角小于等于 α\alphaα 。 其中 2≤H,M≤109,0≤A≤H⋅M22 \leq H, M \leq 10^9, 0 \leq A \leq \frac{H \cdot M}{2}2≤H,M≤109,0≤A≤2H⋅M 。 思路 考虑固定时针不动，只考虑分针相对于时针的运动位置。 方便考虑将时钟展开成长度为 H⋅MH \cdot MH⋅M 的线段，时针始终位于坐标 000 位置，展开后时针的速度为每分钟 111 个单位长度，分针的速度为每分钟 HHH 个单位长度，分针相对于时针的速度即为每分钟 H−1H - 1H−1 个单位长度。 那么可以算出 ttt 分钟时刻分针的坐标为 t⋅(H−1)mod H⋅Mt \cdot (H-1) \mod H \cdot Mt⋅(H−1)modH⋅M 。因为 α=2⋅π⋅AH⋅M\alpha = \frac{2 \cdot \pi \cdot A}{H \cdot M}α=H⋅M2⋅π⋅A ，转换到线段上可以得到分针位置需要满足的条件为： t⋅(H−1)mod H⋅M≤At \cdot (H-1) \mod H \cdot M \leq A t⋅(H−1)modH⋅M≤A t⋅(H−1)mod H⋅M≥H⋅M−At \cdot (H-1) \mod H \cdot M \geq H \cdot M - A t⋅(H−1)modH⋅M≥H⋅M−A 两个条件满足一个即可。 由于两个式子所表示的区间互不相交，可以分开计算，这里我们令 G=gcd(H−1,H⋅M)G = \gcd(H - 1, H \cdot M)G=gcd(H−1,H⋅M) 。 对于第一个式子 满足条件的 ttt 的数量即为 ∑i=0H⋅M−1[t⋅(H−1)mod H⋅M≤A]\sum\limits_{i=0}^{H \cdot M - 1} [t \cdot (H-1) \mod H \cdot M \leq A]i=0∑H⋅M−1[t⋅(H−1)modH⋅M≤A] 。 这里可以分成两种情况来计算： G=1G = 1G=1 时， t∈[0,H⋅M)t \in [0, H \cdot M)t∈[0,H⋅M) 所构成的是一个模 H⋅MH \cdot MH⋅M 的完全剩余系，由剩余系的性质可以得到 t⋅(H−1)t \cdot (H - 1)t⋅(H−1) 也是一个模 H⋅MH \cdot MH⋅M 的完全剩余系，所以只需要算出 [0,H⋅M)[0, H \cdot M)[0,H⋅M) 内小于等于 AAA 的数量即可，答案显然是 A+1A + 1A+1 。 G≠1G \neq 1G=1 时，由同余方程的性质 a⋅c≡b⋅cmod d ⟺ a≡bmod dgcd(c,d)a \cdot c \equiv b \cdot c \mod d \iff a \equiv b \mod \frac{d}{\gcd(c, d)}a⋅c≡b⋅cmodd⟺a≡bmodgcd(c,d)d 可以把原式子转换为 ∑i=0H⋅M−1[t⋅(H−1)Gmod H⋅MG≤⌊AG⌋]\sum\limits_{i=0}^{H \cdot M - 1} [\frac{t \cdot (H-1)}{G} \mod \frac{H \cdot M}{G} \leq \lfloor \frac{A}{G} \rfloor]i=0∑H⋅M−1[Gt⋅(H−1)modGH⋅M≤⌊GA⌋] 。这相当于是把线段 [0,H⋅M)[0,H \cdot M)[0,H⋅M) 均分成了 GGG 份， 其中每份都是一个模 H⋅MG\frac{H \cdot M}{G}GH⋅M 的完全剩余系，也就是上一种情况，因此每一段都对答案有 ⌊AG⌋+1\lfloor \frac{A}{G} \rfloor + 1⌊GA⌋+1 的贡献，总贡献即为 G⋅(⌊AG⌋+1)G \cdot (\lfloor \frac{A}{G} \rfloor + 1)G⋅(⌊GA⌋+1) 。 对于第二个式子 除了 t=H⋅Mt = H \cdot Mt=H⋅M 处不能取到外其余和第一个式子相同，因此对答案的贡献为 G⋅⌊AG⌋G \cdot \lfloor \frac{A}{G} \rfloorG⋅⌊GA⌋ 。 所以最后答案即为 G⋅(2⋅⌊AG⌋+1)G \cdot (2 \cdot \lfloor \frac{A}{G} \rfloor + 1)G⋅(2⋅⌊GA⌋+1) 。 注意 A=H⋅M2A = \frac{H \cdot M}{2}A=2H⋅M 的情况下所有位置都满足条件，特判答案为 H⋅MH \cdot MH⋅M 。 总复杂度为 O(log(H⋅M))O(log(H \cdot M))O(log(H⋅M)) 。 代码 123456789101112131415161718192021#include J. Descent of Dragons tag 主席树 二分 题意 给定长为 nnn 的序列，初始全为 000 ， qqq 次操作，每次操作将区间 [l,r][l,r][l,r] 内等于 xxx 的数加 111 或者查询区间 [l,r][l,r][l,r] 的最大值。 其中 1≤n,q≤5⋅1051 \leq n, q \leq 5 \cdot 10^51≤n,q≤5⋅105 。 思路 其实赛后重新看也没有什么思路，题解给出的似乎是 5⋅1055 \cdot 10^55⋅105 棵平衡树的合并加维护区间标记？不是很理解。最后是参照了另一种主席树的做法，重新梳理一遍。 由操作 111 将所有 xxx 的值加 111 可以联想到版本更新操作，考虑对值域可持久化，第 iii 棵树维护所有值大于等于 iii 的下标。 考虑查询操作，查询区间 [l,r][l,r][l,r] 的最大值时可以考虑二分答案，查询对应树维护的区间内是否有值，二分加查询复杂度为 O(log2n)O(log^2n)O(log2n) 。 考虑更新操作，每次更新区间 [l,r][l,r][l,r] 内的数 xxx 即考虑将第 xxx 棵树在 [l,r][l,r][l,r] 区间内的节点复制到第 x+1x + 1x+1 棵树内，因为考虑的维护的是值大于等于 xxx 所有位置，所以第 xxx 棵树内的值一定是第 x+1x+1x+1 棵树的超集，直接复制节点是对的。因为树包含在区间 [l,r][l,r][l,r] 内的节点数量是 O(logn)O(logn)O(logn) 级别的， qqq 次操作总共增加的节点个数是 O(n⋅logn)O(n \cdot logn)O(n⋅logn) 级别的，空间给了 1024MB1024 MB1024MB ，完全足够。同理更新操作的总复杂度也是 O(n⋅logn)O(n \cdot logn)O(n⋅logn) 级别的。 更新加查询的总复杂度为 O(n⋅log2n)O(n \cdot log^2n)O(n⋅log2n) 。 代码 注意节点空间大小。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include K. Scholomance Academy tag 模拟 题意 大模拟。 思路 略。 代码 略。 M. United in Stormwind tag fwt sosdp 题意 有 mmm 个问题，每个问题的结果为 AAA 或 BBB ，有 nnn 份答案，每份答案可以用一个长为 mmm 的只含 A,BA, BA,B 的字符串表示，求有多少个问题的非空子集使得有不少于 kkk 对答案不完全相同。 其中 1≤n≤2⋅105,1≤m≤20,1≤k≤n⋅(n−1)21 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 20, 1 \leq k \leq \frac{n \cdot (n - 1)}{2}1≤n≤2⋅105,1≤m≤20,1≤k≤2n⋅(n−1) 。 思路 考虑到 mmm 的范围只有 [0,20][0, 20][0,20] ，考虑用 0,10, 10,1 替代 A,BA, BA,B ，则问题转换为有 nnn 个 mmm 位 222 进制数，求有多少个位的子集使得有不少于 kkk 对数字对应位上异或起来不为 000 。 考虑两个数 x=(101)x = (101)x=(101)222， y=(110)y = (110)y=(110)222，则 x⨁y=z=(011)x \bigoplus y = z = (011)x⨁y=z=(011)222。则可以发现只要我选择的集合里包含了 zzz 中 111 所在的位置（ 000 位和 111 位），那么这一对数 (x,y)(x, y)(x,y) 就会对我选择的这一集合产生贡献。 那么我可以先考虑求出原数组中的数两两异或后每个结果出现的次数，即： F(S)=∑x=02m−1∑y=x+12m−1[x⨁y=S]F(S) = \sum_{x=0}^{2^m-1}\sum_{y=x+1}^{2^m-1} [x \bigoplus y = S] F(S)=x=0∑2m−1y=x+1∑2m−1[x⨁y=S] F(S)F(S)F(S) 表示异或后结果中 SSS 出现的次数，很明显这可以用一次 fwtfwtfwt 处理出来。那么所有与 SSS 有交集的集合都会得到 F(S)F(S)F(S) 的贡献，容斥一下把所有与 SSS 不相交的集合减去相应的贡献即可，这里也可以用一个 fwtfwtfwt 或者 sosdpsosdpsosdp 处理好。 fwtfwtfwt 或者 sosdpsosdpsosdp 的总复杂度为 O(m⋅2m)O(m \cdot 2^m)O(m⋅2m) 。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include