【VP 记录】ABC256

KSCD_ · 2024-06-10 22:47:30 · 个人记录

记录

ABCD 切了，E 想了想切了，F 没想出来，G 看出是矩阵了没写出来，Ex 没看，但是也很板。总之全很板。

题解

A - 2^N

基本题，略过不表。

B - Batters

模拟基本题，略过不表。

C - Filling 3x3 array

发现确定四个格后就能唯一确定或填法，所以枚举 a_{1,1},a_{1,2},a_{2,1},a_{2,2}，之后判断是否能填出合法方案即可，复杂度 O(30^4)

D - Union of Interval

用差分前缀和维护每个点是否在最终的并集中，然后对于每个连续段输出即可。

E - Takahashi's Anguish

发现每个人只有一个 x_i 需要在其之后，如果这样连单向边，就是一个基环树森林。如果要尽量满足更多的条件，就只需要在每个环中选一个权值最小的不满足，拓扑排序处理环即可。

F - Cumulative Cumulative Cumulative Sum

推式子，c_x=\sum_{i=1}^x b_i=\sum_{i=1}^x(x-i+1)a_i，d_i=\sum_{i=1}^x c_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i

接着往下拆，d_i=\sum_{i=1}^x\sum_{k=1}^{x-i+1}ka_i=\sum_{i=1}^x\frac{(x-i+2)(x-i+1)}{2}a_i

拆开分子得 (x^2+3x+2)a_i-2xia_i+(i^2-3i)a_i，用树状数组动态维护前缀 a_i,ia_i,(i^2-3i)a_i 的和，系数直接计算即可。

G - Black and White Stones

考虑朴素 dp，首先要枚举每条边上的白石子数量 x，断环为链，设 f_{i,0/1,0/1} 表示考虑前 i 条边，第一条边开头是/否是白色，第 i 条边结尾是/否是白色的方案数，设 c_i=\binom{d-1}{i}，转移如下：

• f_{i,0/1,0}=f_{i-1,0/1,0}\times c_x+f_{i-1,0/1,1}\times c_{x-1}
• f_{i,0/1,1}=f_{i-1,0/1,0}\times c_{x-1}+f_{i-1,0/1,1}\times c_{x-2}

发现是线性转移，用矩阵加速即可，然后发现 f_1 的初始矩阵和转移矩阵相同，直接 n 次方即为答案，答案中有效的为 f_{n,0,0}+f_{n,1,1}，对于 x\in[1,d+1] 分别计算，最后加上 x=0 的一种情况即为结果，时间复杂度 O(2^3d\log n)

Ex - I like Query Problem

考虑把整除也转化为区间修改，发现若区间最大值和区间最小值整除 k 相等，就可以直接区间修改为相同的值。因此势能线段树，维护区间和以及最值，每次都暴力下到一个可以区间修改的区间进行修改，由于每个区间被除 \log V 次或被修改一次即可以保证整除相等，总复杂度为 O(n\log n\log V)