ZROI2022

Day1

22冲刺day1-匹配

给定 $n$ 个区间 $[l_i, r_i]$ , 两个区间之间的贡献是 $\max \vert a-b\vert , \ s. t. \ a\in [l_i, r_i], b\in [l_j, r_j]$ , 求把区间两两配对, 最大化贡献和.

$n\le 10^6, l_i, r_i\le 10^9$

[trick] $\vert x-y\vert =\max x-y, y-x$

[think]见到绝对值想拆贡献

绝对值都拆开, 每个区间的贡献一定是最大值 $ma$ 或最小值 $-mn$, 那么先全选最大值减去最小的 $\dfrac{n}{2}$ 个 $ma+mn$.

22冲刺day1-狼人

给定一个 $n$ 个点的树, 点有颜色 $c_i$ , 求有多少个连通块有绝对众数, 绝对众数指出现次数大于一半的数.
$n\le 3000, c_i\le n$ , 膜998244353

考虑一个连通块显然最多被一个颜色贡献. 那么对每个颜色计算连通块个数.

把当前颜色看成1, 其他颜色看成-1, 则相当于求有多少个和大于0的连通块, 这个问题直接dp, 设 $f_{u, s}$ 表示 $u$ 为根, 和为 $s$ 的连通块个数, 转移是树上背包, 于是这个可以用树上背包那个优化, 子树大小为 $a$ 的只保留 $\pm siz$ 的, 可以把树上背包优化到 $n^2$ , 但总复杂度是 $n^3$ .

不会了, 看题解, 思路完全一样, 除了说复杂度是 $n^2$ 的.

咋回事呢? 实际上每个节点的状态数是 $\min (siz, cnt)$ , 并且 $\sum cnt=n$ , 考虑多叉树转二叉树简化分析, 那么于是对于一个 $k=cnt$ , 考虑其所有极小的 $siz$ 大于 $k$ 的点(自己的两个儿子大小都小于 $k$ ), 那么这样的节点只有 $\dfrac{n}{k}$ 个, 每个节点内部代价可以视为 $k^2$ , 而上面以这些点为叶子的二叉树只会合并 $2\dfrac{n}{k}$ 次(因为二叉树叶子个数为 $\dfrac{n}{k}$ ), 于是复杂度成了 $\dfrac{n}{k}\times k^2+{\dfrac{n}{k}}k^2=nk$ , 然后因为总和是 $n$ 所以复杂度是 $n^2$ .

22冲刺day1-旅行

数轴上有 $n$ 个点, 点 $i$ 出发可以到达 $[i+1, i+t_i]$ 的点, 对每个位置 $p$ , 求 $p$ 到 $n$ 的路径的最大权值, 权值为经过所有点的权值 $h_i$ 和减去移动的代价之和, 从 $i$ 出发到 $j$ 的代价是 $\lfloor \dfrac{j-i}{K} \rfloor\times D$ .
$n\le 2\times 10^6$

考虑这个看起来直接dp, $f_i$ 表示点 $i$ 到最后的代价, 有

$$
f_i=\max f_j-\lfloor \dfrac{j-i}{K} \rfloor\times D +h_i
$$

主要问题是下取整, 因为 $\lfloor \dfrac{j-i}{K} \rfloor=\lfloor j \rfloor - \lfloor i \rfloor-[j\bmod K < i\bmod K]$ , 所以可以对每个 $j\bmod K$ 分类, 每次可以转移到 $i$ 的是一个前缀, 所以现在已经变成单点加矩形max, 可以用树套树2log, 一层存 $i\bmod k$ , 一层存 $\lfloor \dfrac{i}{K} \rfloor$ 即可.

考虑当 $\lfloor \dfrac{i}{K} \rfloor=\lfloor \dfrac{j}{K}\rfloor$ 时一定不需要减1, 所以把序列分成若干大小为 $k$ 的块, 在计算一块内的时候不需要插入, 等到一块结束后, 可以先直接算出本块内的前缀min, 然后再插入到矩形中. 单点插入从原来单点给出, 变成一次给出一行, 那么可以直接算出这一行的前缀max之后做了.

22冲刺day1-密码

给定正整数 $K$ . 请构造两个 $01$ 串 $S, T$ , 使得它们有恰好 $K$ 个本质不同的最长公共子序列.

我们额外给定参数 $L$ , 只有你构造的串满足 $max(\vert S\vert , \vert T\vert)\le L$ 时才能得分.
$L\ge 1000, K\le 10^5$

见鬼构造题.

考虑我们假设构造出来的有一个明显的循环节, 然后发现真的是, 在这个基础上进行调整.

[think] 限制不过强的时候自己钦定一个强性质结论

Day2

22冲刺day2-Relax

每天有 $h$ 小时, 每小时有 $m$ 分钟, 求有多长时间分钟数大于等于小时数.
$h, m\le 10^9$

智障题.

22冲刺day2-Permutation

Cuber QQ 会给你一个 1, 2, 3, ⋯, n 的全排列, 现在他要求你选出尽可能多的数, 并对选出的这些数重新排序, 使得任意两个相邻的数的最大公约数大于等于 2 .

$4\le n\le 10^6$

大于 $\dfrac{n}{2}$ 的质数显然放不进去, 大于 $\dfrac{n}{3}$ 的显然只能头和尾各放两个.

直接硬构造, 先放一堆2, 4, 6, 8, 那么所有小于 $\dfrac{n}{4}$ 的都可以放进去了(前面一个 $2p$ , 后面一个 $4p$ , 中间放所有 $kp$ ),

一开始以为 $[\dfrac{n}{4}, \dfrac{n}{3}]$ 的不行, 但实际也是可以的, 前面一个 $2p$ , 后面一个 $3p$ 即可. 于是

结果是
$$

P_0, 2P_0, 6, (2p_0, p_0, 4p_0, 5p_0\ldots 3p_0), (3p_1, p_1, 4p_1\ldots 2p_1), (2p_2\ldots), (3p_3\ldots)\ldots 12 2P_1, P_1
$$

其中, $P$ 是大于 $\dfrac{n}{3}$ 的质数, $p$ 是小于 $\dfrac{n}{3}$ 的质数, 发现这样可以把所有 $p$ 都放上所以是无敌的.

22冲刺day2-Hotel

无限旅馆的故事(一个旅馆有无限个房间, 来有限个人就让所有人往后挪腾出前几个, 来无限个人就让所有人到编号二倍的位置), 现在 $q$ 次:

  • 新加入 $k$ 个 $c_i$ 国人(或无限个).
  • 询问位置 $i$ 的人是哪国的.
  • 询问住着 $i$ 国人的编号最小的房间是哪个.

$q\le 3\times 10^5$

一开始试图把每次插入的位置看作一个一次函数, 但走不通(没法做询问2, 并且有限多的人做不了)

考虑无限是特殊的, 那就每次插入一个无限就分一段, 现在每一段前面是插入若干有限的, 后面跟了一个无限.

那么考虑查询位置 $i$ 的颜色, 判断是不是开头的有限的, 如果不是的话通过位置奇偶性看出是不是这次插入的无限的, 如果不是, 那就是上次乘2到部分, 就可以把编号除以2继续找, 单次询问 $\log n$ .

[think] 发现难办的操作很多, 但影响当前位置的难办的操作只有 $\log n$ 个. 更多的操作已经失去影响.

22冲刺day2-Tree

给定树 $T_1=Tree(n), T_2=Tree(n)$ , 边有边权, 设 $dis(T, u, v)$ 表示 $u$ 和 $v$ 在 $T$ 上的距离, 对每个 $i$ 求 $\min_j dis(T_1, i, j)+dis(T_2, i, j)$ 的 $j$ .

$n\le 10^5, w_i\le 10^9$

在两棵树上同时建点分树, 枚举一个点在两棵点分树上的 $\log^2$ 个祖先.

对于一个祖先对, 只要最小化 $j$ 到祖先的深度在两棵树上的和即可. 这个似乎需要 $O(1)$ 算了, 注意要踢出掉祖先的一个子树, 预处理子树前缀 $\min$ 和后缀 $\min$ 即可.

Day3

22冲刺day3-数字和

大王给了小王一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ , 对于序列中的每个元素 $a_i$ , 大王想知道在所有包含 $a_i$ 的子区间中求最大的子区间元素和.

$n\le 2\times 10^5$

预处理每个位置开始的前后缀max.

22冲刺day3-走迷宫

大小双王在闯迷宫, 尽快熟悉迷宫是一件很重要的事. 大王想知道迷宫中有多少条通关的路径.

迷宫是一个 $n \times m$ 的网格, 每个格子里面有一个数字. 一条通关的路径是满足以下条件的路径:

  1. 大小双王只能走上下左右4个方向的相邻格子;
  2. 大小双王只能走相邻数字比当前格子大2的格子;
  3. 大小双王走的路径长度(走过的格子个数)必须至少为4;
  4. 如果周围存在还能继续走的格子, 大小双王只能继续走;
  5. 起点周围不存在比它恰好小2的格子.

$n, m\le 1000, \vert v\vert \le 10^6$

第4条和第5条规定了路径是极长的, 第3条可以忽略, 因为单独数长度为4的可以随便做.

那么考虑如何计数极长路径, 直接 $f_{i, j}$ 表示走到 ${i, j}$ 的方案数即可. 是智障题.

对了, 可以不忽略第三条, 每个点存长度为1, 2, 3, 4即可, 复杂度不变.

22冲刺day3-多米诺

大小双王对于多米诺有独特的理解.

现在有一个 $n \times m$ 的格子大小的木板, 大王想用 $1 \times 2$ 的多米诺骨牌把格子填满. 大王不满足于普通的填法, 大王还想让每个格点都不能被 $4$ 个多米诺骨牌顶点覆盖.

大小双王想问你有多少个方案把他们填满呢. 如果答案太大, 对 $998244353$ 取模.

$n, m\le 10^7$

好困难啊, 而且极难用语言描述. . .

基本思路是分析骨牌的性质, 限制使得我们相当于用
picture 2
picture 4

两个图形来拼, 那么考虑边框是最不自由的位置, 看边框的拼法:

picture 5

手动补全, 发现只要确定了边框一定能补出一个矩形, 而关键是, 当我们拓展边框的时候, 发现它无论如何都填不满, 于是得到结论, $n\times m$ 的矩形是由若干 $n\times k$ 的矩形拼成的.

picture 6

于是对 $n$ 分奇数, 偶数讨论, 结论如下:

picture 7

重点是通过分析性质发现它其实是一维问题的这一步.

22冲刺day3-等差数列

给定数列 $a_n$ , 每次可以把一个数加2或减1, 求最少几次满足存在整数 $d$ 满足 $i\in [2, n], a_i-a_{i-1}=d$ 的 $i$ 至少有 $n-2$ 个.
$n\le 10^5, a_i\le 5\times 10^5$

条件相当于把序列变成两段公差相同的等差数列(看成三段了)

然后对于单独一段等差数列, 确定了斜率 $d$ 之后, 画出一条斜线, 如果都是 $+1$ 应该是直线经过所有点的截距的中位数, 有加2之后设每个点截距为 $c$ , 真实截距为 $x$ , 贡献是 $\sum_{c_i<x} \lfloor \dfrac{x-c_i}{2} \rfloor +2[(x-c_i)\bmod 2=1]+\sum_{c_i>x} c_i-x$

这个问题忽略那个 $(x-c_i)\bmod 2$ 的部分之后, 最优解显然是数列的 $\dfrac{2}{3}$ 处, 加上这个之后只要看看是最优解上下一个位置即可.

此外, 可能的公差其实非常少, 设两段中长的一段长度为 $l>\dfrac{n}{2}$ , 那么 $l\vert d\vert \le 5\times 10^5$ , 于是 $\vert d\vert\le \dfrac{v}{n}$ , 那么暴力枚举 $d$ , 每次遍历序列, 枚举划分点的时候动态维护最小值的是可行的. 因为 $nd$ 是和 $v$ 一个量级的.

考虑如何动态维护最小值, 其实就是不断添加/删除一个数求第 $k$ 大的值, 区间和, 区间奇偶数个数即可.

题解表示这个常数比较大, 用一个对顶堆维护, 因为我们的 $kth$ 的 $k$ 固定, 所以让一边始终存前 $k$ 个这样.

Day4

22冲刺day4-签到题

有 $n$ 台路由器, 按照 $1 \sim n$ 的顺序连接成一条链. 第 $i$ 台路由器向第 $i+1$ 台路由器传输 $1$ 比特的数据需要花费 $t_i$ 的时间. 多个路由器之间可以并发运行——即每个路由器可以同时给下一个路由器传递自己当前已经拥有的数据.

现在你需要从 $1$ 号路由器向 $n$ 号路由器发送 $m$ 比特的数据, 所花费的时间是多少?

直接想象一下这个过程, 只有最慢的那个会堵住, 所以就是第1bit走完全程的时间, 加上 $t_{max}(m-1)$ , 就行了.

22冲刺day4-简单题

定义一个长度为 $n$ 的数组 $A$ 的价值为

$$
\sum_{l=1}^n\sum_{r=l}^nQ_{l, r}\cdot\max{A_l, A_{l+1}, \cdots, A_r}

$$

其中数组 $A$ 的第 $i$ 个位置上的数字是 $V_{i, 1}, \cdots, V_{i, K_i}$ 中的一个, 并且选择 $V_{i, j}$ 的花费为 $C_{i, j}$ . 你需要求出一个数组 $A$ , 使得价值减去花费最大.

$n\le 300, \sum K_i\le 3\times 10^5$

考虑区间暴力dp, 设 $f_{i, j, k}$ 表示区间 $[i, j]$ , 最大值为 $k$ 的价值减花费. 前缀和优化复杂度 $n^2K$ . (最大值为 $k$ 这个条件同时记录了位置和大小)

删掉 $k$ , 设 $f_{i, j}$ 表示随便选最大值的情况, 仍然区间dp, 有

$$
f_{i, j}=\max_k f_{i, k}+f_{k, j}+V_{k, v}\sum_{l\le k\le r} Q_{l, r} -C_{k, v}
$$

我们计算 $f_{i, j}$ 的时候枚举了中间的最大值 $t$ , 如果 $f$ 实际值小于 $t$ 那么算的是对的, 如果实际情况是大于 $t$ 那么你会把它算小, 在取 $\max$ 的情况下不会错.

于是状态数 $n^2$ , 考虑优化转移到时候 $v$ 的取值, 发现 $\sum_{l\le k\le r} Q_{l, r}$ 是容易确定的二维数点, 所以成了优化 $\max vq-c$ ( $v, c$ 都是单调的因为我们可以把 $v_1>v_2, c_1<c_2$ 的 $2$ 直接删了再排序), 然后 $vq-c=b$ , 则 $vq-b=c$ , 把 $v, c$ 看成点就是斜率优化, 要在凸包上求切线, 二分即可.

22冲刺day4-数数题

给定一个长度为 $n−1$ 的数组 ${ai}$ 和一个长度为 $n$ 的数组 ${ci}$ , 我们根据以下过程可以随机建立一棵树:

$T_1$ 是一棵仅包含节点 $1$ 的树;

$T_i(i>1)$ 将 $i$ 号点连接到 $T_{i−1}$ 上, 其中连接到 $j(1\le j\le i−1)$ 号点的概率为 $\dfrac{a_j}{a_1+\ldots +a_{i−1}}$ , 边权为 $c_i+c_j$ .

接下来有 $Q$ 组询问, 每组询问给出 $(u, v)$ , 你需要回答 $u$ 到 $v$ 的期望距离, 膜 $10^9+7$

组合意义天地灭, 代数推倒保平安!

考虑距离转化成 $u, v$ 的期望深度减去 $lca$ 的期望深度. 于是要算求一个点的深度期望, 拆开贡献之后是要求一个点是另一个点的祖先的概率, 结论是不管第二个点是谁概率都是 $\dfrac{a_i}{b_i}$ .

证明可以考虑当前两个大小为 $a, b$ 的节点 $a, b$ , 节点 $d$ 现在插入, 为 $a$ 的子孙的概率是 $\dfrac{a}{a+b}$ , 如果中间来了一个大小为 $c$ 的节点 $c$ 插入, 再插入 $d$ , 则总方案数 $(a+b)(a+b+c)$ , 其中有 $a^2+ab+ac$ 种方案 $a$ 是 $d$ 的祖先, 所以说明了任意挂一个点, 概率不变, 于是任意一个点是其子孙的概率和紧邻的一个点是它儿子的概率相同.

qyc通过构造双射也证明了这一点, 通过考虑两个点 $u, v$ 交换它们的子树的比的变化得到.

于是一个点 $u$ 的期望深度是 $c_1+c_u+\sum 2c_v\times \dfrac{a_v}{b_v}$ .

但这个代数推导不是白说的, 考虑设点 $u$ 到根路径上点集为 $S$ , 则概率是

$$
\begin{gathered}
E(dep_u)=c_1+c_u+\dfrac{a_1}{b_{u-1}}\sum_{S} \prod \dfrac{a_i}{b_{i-1}}\sum_{i\in S} 2c_i\
=c_1+c_u+\dfrac{a_1}{b_{u-1}}\sum_{i\in[2, x-1]}\dfrac{2c_ia_i}{b_{i-1}}\prod_{j\in[2, u-1]\And j\ne i}\dfrac{a_j+b_{j-1}}{b_{j-1}}\
=c_1+c_x+2\sum_{i\in [2, x-1]}\dfrac{c_ia_i}{b_i}
\end{gathered}
$$

再考虑一个点是它俩 $lca$ 的概率, 考虑设 $l$ 为 $u, v$ 的 $lca$ , $l$ 到 $u$ 上的点集为 $S_1$ , $l$ 到 $v$ 上的点集为 $S_2$ , 于是类似的:

$$
\begin{gathered}
P(l, u, v)=\dfrac{a_l^2}{b_{u-1}b_{v-1} }\sum_{S_1}\sum_{S_2}\prod_{i\in S_1} \dfrac{2a_i}{b_{i-1} }\prod_{j\in S_2}\dfrac{a_j}{b_{j-1} }\
=\dfrac{a_l^2}{b_{u-1}b_{v-1} }\prod_{i\in[l+1, u-1] }\dfrac{2a_i+b_{i-1} }{b_{i-1} }\prod_{j\in [u+1, v-1] }\dfrac{a_j+b_{j-1} }{b_{j-1} }\
=\dfrac{a_l^2}{b_{u-1}b_{u} }\prod_{i\in [l+1, u-1] }\dfrac{2a_i+b_{i-1} }{b_{i-1} }
\end{gathered}
$$

于是答案就是 $E(dep_u)+E(dep_v)-2\sum_l P(l, u, v)$ .

qyc表演一个组合意义:

考虑怎么求 $i$ 是 $j$ 的祖先的概率, 设为 $\mathrm{anc}(i, j)$ . 设 $i$ 前面所有点的点权和是 $s_{i-1}$ , 定义一棵树的权值是每个点父亲的 $a_i$ 的乘积, 那么权值的比就是概率的比, 并且我们只关心 $i$ 是不是 $j$ 的祖先, 所以 $<i$ 的点可以看成一个权值为 $s_{i-1}$ 的点. 考虑一个双射, 对于一个 $i$ 是 $j$ 的祖先的情况, 我们把 $i$ 的包含 $j$ 的子树接到 $<i$ 的任何一个点上, 反过来也是一样的, 那么我们就得到了一个权值为 $ka_i$ 的方案和一个权值为 $ks_{i-1}$ 的方案的双射, 于是我们知道 $i$ 是 $j$ 的祖先的概率是 $\frac{a_i}{a_i+s_{i-1}}=\frac{a_i}{s_i}$ . 当然, 当 $i=j$ 它是 $1$ , $i>j$ 时它是 $0$ .

考虑怎么求 $l$ 是 $i, j$ 的lca的概率, 设为 $\mathrm{lca}(l, i, j)$ , 其中 $i<j$ . 还是双射, 我们把包含 $i$ 的子树接到前面, 包含 $j$ 的子树接到前面, 两个一起接到前面, 那么相当于把四种情况打了一包, 它们权值的比是 $a_l^2: a_l(s_l-a_l): a_l(s_l-a_l): (s_l-a_l)^2$ , 于是我们得到了一个 $l$ 是 $i, j$ 的lca和 $l$ 不是 $i, j$ 的公共祖先的双射. 设后者是 $\mathrm{ca}(l, i, j)$ , 就有 $\mathrm{lca}(l, i, j)=\frac{a_l^2}{(s_l-a_l)(s_l+a_l)}(1-\mathrm{ca}(l, i, j))$ . 感觉上只差最后一个方程了, 计算 $l$ 是 $i, j$ 的公共祖先的概率, 不太能直接算, 因为它不独立, 但是考虑这个等于它是 $i, j$ 的lca的祖先的概率, 所以我们得到 $\mathrm{ca}(l, i, j)=\sum\limits_{k=l}^i\mathrm{anc}(l, k)\mathrm{lca}(k, i, j)$ . 直接解, 可以得到 $\mathrm{lca}(i, i, j)=\mathrm{anc}(i, j), \mathrm{lca}(l, i, j)=\frac{a_l^2}{s_l^2}\left(1-\sum\limits_{k=l+1}^i\mathrm{lca}(k, i, j)\right)$ .

于是设 $\mathrm{slca}(l, i, j)=\sum\limits_{k=l}^i\mathrm{lca}(k, i, j)$ , 则有 $\mathrm{slca}(i, i, j)=\mathrm{anc}(i, j), \mathrm{slca}(l, i, j)-\mathrm{slca}(l+1, i, j)=\frac{a_l^2}{s_l^2}(1-\mathrm{slca}(l+1, i, j))$ , 也就是 $\mathrm{slca}(l, i, j)=\frac{a_l^2}{s_l^2}+(1-\frac{a_l^2}{s_l^2})\mathrm{slca}(l+1, i, j)$ .

接下来考虑答案是两个点深度的期望之和减去两倍的lca深度的期望, 于是考虑计算一个点 $u$ 深度的期望. 到根路径上, 自己和根贡献 $1$ , 此外每个祖先贡献 $2$ , 所以答案是 $\mathrm{dep}(u)=c_1+c_u+2\sum\limits_{i=2}^{u-1}\frac{a_ic_i}{s_i}$ , 可以预处理.

最终答案就是 $\mathrm{dep}(i)+\mathrm{dep}(j)-2\left(\mathrm{anc}(i, j)\mathrm{dep}(i)+\sum\limits_{l<i}(\mathrm{slca}(l, i, j)-\mathrm{slca}(l+1, i, j))\mathrm{dep}(l)\right)$ . 考虑 $\mathrm{slca}(l, i, j)$ 到 $\mathrm{slca}(l, i+1, j)$ 的变化, 注意到它们的转移相同只有初值不同, 于是考虑把它看成初值的一次函数, 相当于有一堆一次函数, 支持给每个在右侧复合一个一次函数, 并求所有的某个点点值的和. 拆一拆发现复合的和等于和的复合, 或者说这个是线性变换, 所以我们只需要维护一个和即可. 使用线性逆元, 复杂度线性.

PS: 他是糊的

22冲刺day4-最后一题

交互库里有一棵 $n$ 个点的树, 你可以通过做若干次如下询问来确定这棵树:

给定一个节点集合 $S$ 和节点 $x$ , 交互库会告诉你 $x$ 是否在包含 $S$ 的最小连通块中.

$n\le 1000, Q\le 22000$

交互库是 $O(S)$ 的

考虑一个暴力, 确定一个点是叶子只要问 $u$ , 和 $U-{u}$ , 就行, 可以一层一层剥叶子. 次数是 $n^2$ 的, $S$ 大小是 $n^3$ 的.

另一个想法是我们可以通过一次询问确定祖先关系.

询问次数看起来像是log的, 考虑二分?

树上交互题, 考虑归纳?

拼一拼, 假设我们要确定 $u$ 的子树, 先通过二分得到 $u$ 的子树和未知的点集的一个交 $y$ , 然后递归的求 $y$ 的子树, 于是 $x$ 子树内部都已经确定, 考虑确定 $x$ 的儿子, 由于我们同样知道哪些点没有父亲, 所以仍然二分看 $x$ 是谁的父亲就是 $n\log n$ 了.

Day5

22冲刺day5-组队

给定序列 $a_n$ , 选出一个长3的上升子序列最大化三个数的乘积.

$n\le 10^5, \vert a_i\vert \le 10^6$

$f_{i, j}=f_{i-1, j-1}*a_i$ , 随便维护

22冲刺day5-串

如果一个串 $S$ 中任意两个不同字符的出现次数都不相同, 就称 $S$ 是一个好串

如果一个串 $S$ 的任意一个前缀和后缀都是好串, 就称 $S$ 是一个大好串.

$q$ 次询问, 每次给定 $n, k$ , 求长度为 $n$ 且字符集为前 $k$ 个小写字母(每个字母必须出现)的大好串中字典序最小的串.

构造

看不懂的构造题

todo

22冲刺day5-树

给定 $Tree(n)$ , 初始时边权是1, $q$ 次询问若必须恰好 $k$ 次给一条边增加1, 最终直径的最小值. 询问独立.

$n\le 2\times 10^5$

考虑直径的中心.

那么上来给所有边之间加个点, 这样一开始和最后的直径的中心一定在某个点上.

那么我们一定把所有叶子都先加长到底, 并且能在底下加一定不在顶上加.

所以所有次数都用在连着叶子那条边上, 对于一个中心, 可以直接算出需要多少代价先补齐到最深的叶子, 再继续整上去.

于是每个节点为根对答案的贡献是一个一次函数: 每若干次操作答案加1, 前若干次不变这样的.

那么这样一堆折线可以直接离线询问扫, 或者在线李超树之类的做.

22冲刺day5-排列

给定 $n$ 个节点的树, 要给每个顶点赋值 $c_i$ 满足 $c$ 是一个 $n$ 排列, 且对于相邻两点 $u, v$ , $\vert c_u-c_v\vert \le 2$ . 求方案数

$n\le 60$ , 膜 $10^9+7$

好离谱的题啊

正解是, $f_{i, j, k, S}$ 表示填了 $1\ldots i$ , 其中第 $i$ , $i-1$ 次分别填到了 $j, k$ 上, 当前 $S$ 中的点已经被填上了的方案数, 要求 $k$ = $u$ 的时候其邻接点都被填了, 猜测状态数其实很小(限制很强)于是去写发现能过.

考虑, 首先度数都不大于4, 其次对于状态 $i, j, k, S$ , 如果删掉 $j, k$ 两个点, 剩下的森林中每一棵树要么都被填了, 要么都没被填, 否则一定有一个小于等于 $i-2$ 的点与一个没染色的点相邻, 这两个点必然不合法. 于是对每个 $u$ , $S$ 只有 $2^7$ 种. 其中 $7$ 是删去两个点之后的连通块数.

Day6

22冲刺day6-并王

给定一个长为 $n$ 的数组 $a_i$ , 求

$$
\sum_{1\leq i\le j\le k\le p\le q\leq n}(((a_i\otimes a_j)\vee a_k)\otimes a_p)\wedge a_q
$$

膜 $2^{64}$ .
$n\le 4\times 10^5, a_i\le 2^64$

太愚蠢了! ! !

为什么瞪了半天没想到每一位独立

[think] 全是二进制操作考虑每一位独立.

于是直接独立就做完了

22冲刺day6-最小最大

给定 $a_n$ , 求 $a$ 的子序列 $b_k$ , 最小化 $value=\max (b_1+b_2, b_2+b_3, \ldots, b_{k-1}+b_k, b_k+b_1)$ , 输出最小值.

$n, k\le 5\times 10^5, a_i\le 10^9$

二分答案判定.

考虑最小值一定在答案里, 于是从最小值出发转一圈, 维护 $f_i$ 表示以 $i$ 结尾的情况下最多选了几个.

那么每次遇到一个新的值, 这个位置的值就是一个区间的max加1. 最后绕一圈判定即可.

但这个是2log的, 应该过不太去, 看看砍谁.

觉得二分答案砍起来过于离谱. 考虑干掉这个dp.

考虑不dp, 一开始开一个链表把所有数都加进去, 每次如果相邻两个数之和大于二分店答案就删了大的, 直到全部合法.

此时如果长度小于 $k$ 就死了, 大于 $k$ 就可以, 可以是因为考虑从最小值往外删删一定正确的.

22冲刺day6-括号序列

给定一个长为 $2n$ 的正整数序列 $p$ , $1\leq p_i\leq n$ .
其中 $1$ 到 $n$ 每个值出现恰好两次, 将值相同的元素进行配对. 要求给每对元素赋上同一种括号(或者), 使得最终序列构成一个合法的括号序列.
当然这个问题对你来说有点过于简单, 于是加上一个限制: 要求你给出的括号序列是所有可能的最终序列中字典序最小的(这里认为(的字典序小于)的).
$n\le 2\times 10^6$

[think] 见到字典序想贪心!

但发现我们也不知道一个括号钦定之后是否有解.

[think] 有后效性, 考虑钦定+反悔.

发现我们不知道什么时候反悔. 可以考虑先选择最靠前的括号对 $\dfrac{n}{2}$ 当成(, 然后从左往右扫:

  • 如果当前前缀和小于0, 那么一定要调成正的, 从左边选一个最靠右到)变成(, 右边选一个最靠左都(变成)即可.

于是把每个对都塞到堆里即可. 要一个堆维护左边的, 一个堆维护右边的.

22冲刺day6-脉冲星

给定 $L, R, x$ . 要求出一个整数序列 $A$ , 满足 $L\leq a_i\leq R$ , 并且 $\otimes_{i=1}^n a_i=x$ , 使得其能够最大化 $\sum_{i=1}^n a_i$ . 求最大值.

$T\le 10^6, x, L, R\le 10^9$

考虑从高位开始贪心, 那么最高位如果能选一定选上, 并且根据 $x$ 这一位是0还是1选奇数/偶数个, 然后每一位有可能有3个数不选满.

有亿点细节.

Day7

22冲刺day7-A

给定两个数的 $x\mathrm{and} y$ 和 $x\mathrm{xor} y$ , 求 $x\mathrm{or} y$

$x, y\le 2^{64}$

直接做

22冲刺day7-B

给定一个无自环无重边的无向图, 求其最大团. 团的定义是一个点集使得其中任意两个不同的点之间都有一条无向边相连.

p. s. 出题人比较懒, 为了方便, 数据中所有的图都是由两个不相交的团, 两个团之间再连一些无向边构成的.

$n\le 500$

考虑最大团是补图的最大独立集, 因为这个性质所以补图是二分图, 于是要求二分图最大独立集, 这个等于最小点覆盖, 考虑如何最小点覆盖, 可以求一个二分图建成网络流的二分图, 中间边设inf, 两边边设1, 求最小割, 那么任意两个有边的点的源汇边必然割了一条, 割了哪个就选哪个点即可.

图论功底太拉啊.

22冲刺day7-C

给定 $Tree(n)$ , 边有边权, 求选 $k$ 个点, 任意顺序, 使得按顺序走到这 $k$ 个点的距离和最大.

$n, k\le 2\times 10^5$

就是选 $k$ 个点最大化虚树边权和. 啊, 不对, 顺序是重要的.

考虑dp, 设 $f_{u, i}$ 表示子树 $u$ 内选了 $i$ 个点, 每次算上 $u$ 到父亲这条边的贡献为 $\min(i, k-i)\times w$ 即可.

$$
\begin{gathered}
f_{u, i}: =\max f_{u, j}+f_{v, i-j}\

f_{u, i}: =\max f_{u, i}, f_{u, i-1}\\

f_{u, i}: =f_{u, i}+\min(i, k-i)\times w

\end{gathered}
$$

于是考虑三个转移, 第一个是做max-加卷积, 也就是闵和, 第二个是平移, 第三个是加一次函数, 发现对于同一个 $u$ , $f_i$ 函数是凸的于是SlopeTrick维护即可, 闵和可以启发式合并, 复杂度2log.

22冲刺day7-D

给定一个DAG和 $k$ 条路径, 对每个 $i$ 求有多少条路径到1且不包含这 $k$ 条中的任意一条. 膜998244353.

$n, m, \sum l_i\le 10^5$ , $l_i$ 为第 $i$ 条路径长度.

把所有边取反变成到1的方案数dp, 那么一个点的方案数是所有其出边的方案数之和, 但还要考虑那些以这个点为起点的路径, 考虑如果只在这里删掉后面仍然会影响, 所以直接把图改了: 把这个点开始的这条路径上的所有点 $u_1\ldots u_l$ 复制一份成 $u_1’\ldots u_l’$ , 然后复制出边, 把原来 $u_i’\to u_{i+1}$ 这一条出边改成 $u_{i+1}’$ , 在最后一个位置删掉 $u_{l-1}\to u_l$ , 最前面改成 $u_1\to u_l’$ , 那么以后的每次dp都是对的了.

考虑用数据结构维护这个可持久化, 于是对每个点开一个主席树存出边即可.

Day8

22冲刺day8-括号序列

给定一个括号序列, 求最少添加几个括号才能把它变成合法的括号序列. 可以在任意位置添加括号, 左括号和右括号都可以添加.
$n\le 10^6$

那么我们只要把所有前缀和调成正的即可, 于是发现直接在最前面/最后面加一定不劣.

22冲刺day8-游戏

A, B玩游戏, 有 $n$ 个石子, A显瘦, 每人每次最少拿一个石子, 最多拿 $k$ 个, A要求取完石子之后剩余质数个, B取完之后剩余合数个, 无法操作的人输, 问两个人都按照最优策略的情况下会进行多少轮. 最优策略指必胜的希望快点赢, 必负的希望慢点死的策略.

$n\le 5\times 10^6$

直接dp

22冲刺day8-树

给定排列 $p_n$ 和 $n$ 个点, 求满足若 $i\to j$ , 则 $p_i\to p_j$ 的无向无根生成树数量. 两棵树不同指不同构.

$n\le 3\times 10^5$

仍然考虑排列形成的若干个环, 如果一个环大小超过2环内不能连边.

如果两个环之间连边, 当且仅当其中一个是另一个的倍数. (画一画可知)

一个环只能与一个比它小的连边, 因为一个环的与其因数 $d$ 连边时是膜 $d$ 的每个余数连到一个点上, 于是如果有两个连的位置同余直接死, 但环是绕一圈所以总会死. 而和等于的或大于的没事可以任意多.

一个大小 $ka$ 的环连到大小 $a$ 的环上有 $a$ 种方案. (具体的, gcd).

然后就是对着数了, 刚才的性质让我们想到直接从小到大, 对每个点决定向比它小的部分连的是谁. 于是按照大小分为若干组, 每一组假设有 $k$ 个环要向比它小的连, 每个是独立的, 设大小为 $i$ 的环的个数为 $cnt_i$ , 组 $i$ 向前连的方案数就是 $\binom{n}{k}(\sum_{j<i} cnt_j\times j)^k$ , 组内连的是把这些环分成 $k$ 棵生成树, $x_1\ldots x_k$ 不在同一棵的方案数, 是 $k\times n^{n-k-1}$ . 就做完了.

22冲刺day8-序列

给定 $a_n$ , 每次单点修改, 或者询问对于区间 $a_[l, r]$ 提取成 $b$ , 任意次操作, 每次可以 $b_i: =b_i-2, b_{i+1}: =b_{i+1}+2$ , 或者若 $b_{i+1}=0$ , $b_i: =b_i-1, b_{i+2}: =b_{i+2}+1$ , 问最后最多有多少个0.

$n\le 2\times 10^5$

考虑可以先通过1操作变成01数组在最后跟一个数 $x$ .

发现然后对于所有不是最后位置的0都可以把0搬运到前面. 于是就成了一串0接一串1接一个s.

那么考虑两个区间的合并, 左区间的 $x$ 先被变成01加到右区间的 $x$ 上, 然后合并01段, 发现如果中间有奇数个0两个1段可以两两消去, 左边的1如果多还可能与s2再消一次. 偶数个则什么也做不了. 于是用这个去合并两个区间, 线段树即可.

Day9

22冲刺day9-逆序对

这就是JOI冒泡排序或LOJ花火点弱化啊?

ZR退钱

22冲刺day9-排序

给一个序列 $a_n$ , 每次可以选择相邻三个, 把第一个插入到最后一个位置( $a_i, a_{i+1}, a_{i+2}\to a_{i+1}, a_{i+2}, a_i$ ), 求不超过 $n^2$ 次将序列排序的方案数.

$n\le 1000$

想一想 $n^2$ 排序有啥算法, 直接一个选择排序(每次选择最大值, 把它用操作移动到最后)拍上去就行了. 最后可能会剩下两个没法用操作移动, 那么在无重复元素的情况下就死了, 因为操作不改变逆序对奇偶性.

如果有相同元素, 那就直接有解了, 因为我们改变两个相同元素的顺序就必然有解.

交, 为啥FST20分啊? 又是 $n^2$ 的操作开 $n$ 的数组

22冲刺day9-旅行

给定数组 $c$ , 求所有重排方案中, 每个方案的权值和, 一个位置的权值和定义为, 最小的 $i$ 满足从 $i$ 开始走一圈, 除了一开始在 $i$ 的时候走过的元素之和都大于0.
$n\le 20$

有点类似Raney的考虑, 如果和小于0直接寄, 否则一定是选择了第一个最小值开始走.

于是枚举最小值左右都放了哪些 $c$ , 也就确定了最小值的位置, 那么接下来要求右边前缀和大于0, 左边前缀和大于 $\sum c_i$ , 直接 $dp_S$ 表示选了 $S$ 内的点的方案数就行了. 复杂度 $n2^n$

22冲刺day9-计数

求有多少长为 $n$ , 任意两个相邻数和不为 $m$ 或 $m+1$ 的方案数.

$n\le 10^9$ , $m\le 10^7$ , 膜 $10^9+7$

qyc场切题. 15k.

考虑和为 $m$ 和 $m+1$ 的数, 可以连出 $m \to 1\to m-1\to 2\to m-2\to 3\ldots$ , 行成一条长 $m$ 的链, 要求链上不相邻的两点在位置上不相邻, 以及后面大于 $m$ 的部分点随便排.

于是考虑容斥, 钦定我们连出若干条边行成若干条链, 那么每条链有一种(长度为1)或两种(长度大于1)方案, 问题变成了要求把 $m$ 个元素划分成 $i$ 个链, 剩下随便放的方案数(把链看成元素做排列), 方案数为

$$
\sum_{i\in [0, m]} f_{m, i} (i+n-m)! (-1)^{m-i}
$$

$f_{i, j}$ 表示 $i$ 个元素划分 $j$ 个链的方案数.

dp计算 $f$ 可以做到 $m^2$ , 然后剩下的部分趋近于玄学, 官方题解猜测在 $n-m$ 一定时答案是关于 $m$ 的整式递推并且整式的次数和递推的阶数都很小, 直接暴力计算前几项然后解方程(高消)发现满足一个递推式, 做到 $O(m)$ .

另一个方法是在dp那一步写成生成函数用ODE自动机跑

Day10

22冲刺day10-距离

给定 $Tree(n)$ , 边权 $w_i$ , 求哪个点为根的时候根到其他节点的距离和最小, 距离指两点间边权最小值.

$n\le 10^6$

上来都没看见距离定义, 和qyc一人一个换根dp往上冲

最小值可合并, 不可差分, 不可减, 贡献可合并, 可差分, 可减. 最小值毙掉了换根dp, 于是考虑从贡献角度考虑:

对于一个最小值把树分成两半, 那么两边之间的贡献都要经过它, 再加上内部贡献即可.

分割不好做做加边, 想了想配个启发式合并, 就行了.

于是我的做法是从大到小排序, 维护一堆联通块(一个vecotr记录联通块, 一个加法标记), 每次合并的时候加上贡献.

写了一发过不去? 把vector换成链表, 加个火车头和快读, 卡进1s, 时限开到2s.

看了看, 智障了, 这里启发式合并是不必要的, 可以换成Kru重构树, 可以直接Kru.

22冲刺day10-哈夫曼树

哈夫曼树常用于解决最优编码问题: 即给定若干种不同字符在文本中的出现次数(频率), 试为每个字符给出一个 $\texttt{01}$ 串作为编码, 使得 $频率\times 码长$ 之和最小, 且没有任何一个编码是另一个编码的前缀.

本题中, 需要解决的是一个非常类似的问题: 按字典序从小到大, 给出 $n$ 种不同字符及其频率, 试为每个字符给出一个 $k$ 进制字符串(即, 字符串中的每个字符为 $0\ldots k−1$ 中的一个)作为编码, 使得 $频率\times 码长$ 之和最小, 且没有任何一个编码是另一个编码的前缀. 同时, 你还需要保证给出的编码在字典序上是保序的, 即, 不会出现两个字符 $a, b$ , 使得字典序上 $a$ 比 $b$ 小, 但是 $a$ 的编码比 $b$ 的编码的字典序大.

只需输出最小的 $频率\times 码长$ 之和即可.
$n\le 500, k\le 60$

首先考虑一个模型转化, 这个问题等价于在一个数组上石子合并, 每次可以合并至多 $k$ 个, 数组上对应值为频率算答案. 因为石子合并就是在搜一棵最优搜索树.

然后可以写一个 $n^3k$ 的dp, 设 $f_{l, r, i}$ 表示 $[l, r]$ 分 $i$ 段的方案区间dp转移即可.

注意到树上任意节点一定恰好有 $k$ 个儿子(除了儿子都是叶子节点的), 所以不用算出每一个 $i$ , 而是倍增只算一个 $f_{l, r, k}$ .

这题决策单调性是假的

这玩意倍增怎么写? 好像是预处理每个位置由哪些dp值拼起来, 看到有些实现写的类似线段树.

[think] 倍增优化dp别忘了

22冲刺day10-欧拉

本题要解决的问题是, 给定一个正奇数 $n$ , 试找到一个数 $x\le 10^18$ , 使得 $x-\varphi(x)=n$ .

$n\le 10^9$

$x-\varphi(x)$ 没什么性质, 而且不要求最小化, 考虑构造一些特殊的 $x$ .

考场上尝试了 $x$ 为一堆小质数拼起来, 再搭一个巨大的质数, 但巨大质数太大没法弄, 但实际上只要构造 $x=pq$ 即可, 因为 $pq-\varphi(pq)=pq-(p-1)(q-1)=p+q-1=n$ , 也就是 $n+1=p+q$ , 注意 $n+1$ 是偶数, 根据哥德巴赫猜想一定可以有这样的解.

于是直接枚举判断 $i$ 和 $p-i$ 是否都是质数.

[think] 第二次碰见哥德巴赫猜想数论题

[think] 构造题, 自己给方案钦定一个性质

22冲刺day10-子图

给一个简单无向 $Graph(n, m)$ , 求所有导出子图中有几个边数为偶数.
$n\le 46$

把偶数转化成乘法, $[c\bmod 2=0] = \dfrac{(-1)^c+1}{2}$ .

那么折半, 需要考虑跨过中间的贡献, 先搜左边, 注意到在左边的集合固定的情况下,右边的单个点的贡献是可合并的, 于是处理出右边到左边有奇数条边的单点组成, 左边为 $S$ 时这个点集设为 $P(S)$ .

于是考虑合并两边, 处理 $f_S$ 表示 $P(T)=S$ 的 $T$ 的权值之和, $g_S$ 表示右边为 $S$ 的权值, 则要求

$$
\sum_{S, T} f_Sg_T (-1)^{\vert S\cap T\vert }
$$

于是对 $f$ 做FWT即可.

被教育了, 这个是FWT-XOR的定义.

[think] 看看什么情况下贡献是可合并的.

这个题是可以 $n^3$ 的, 在榜上脱颖而出

picture 1

离奇故事是, 这个可以多项式复杂度. 首先改成如果边数是 $c$ , 则贡献 $(-1)^c$ . 考虑找一条边 $(u, v)$ , 先假设 $u, v$ 都没有自环, 考虑它对剩下的部分的贡献. 对于剩下的部分的一个方案, 设单独再选 $u, v$ 的贡献是 $x, y$ , 那么选 $uv$ 是 $-xy$ , 不选当然是 $1$ , 那么总共是 $x+y-xy+1$ . 如果 $x=1, y=1$ 它是 $2$ , $x=1, y=-1$ 它是 $2$ , $x=-1, y=-1$ 它是 $-2$ . 所以乘个 $2$ 先.

那么也就是至少一边邻接偶数个点则贡献是 $1$ , 否则是 $-1$ . 考虑构造一个这个东西, 容易想起来偶数乘任何数都是偶数, 所以我们在剩下的点中, $u$ 的邻接点和 $v$ 的邻接点连成完全二分图(如果一个点同时邻接 $u, v$ , 则连一个自环), 那么选了 $c_u, c_v$ 个 $u, v$ 的邻接点, 贡献就带一个 $(-1)^{c_uc_v}$ , 于是可以把 $u, v$ 删掉了. 显然删掉一对重边不影响答案.

考虑有自环的情况, 我们让 $x, y$ 仍然是不考虑自环的贡献, 那么如果 $u$ 有自环而 $v$ 没有, 则贡献 $-x+y+xy+1$ , 如果 $x=1, y=1$ 它是 $2$ , $x=1, y=-1$ 它是 $-2$ , $x=-1, y=1$ 它是 $2$ , $x=-1, y=-1$ 它是 $2$ , 也就是 $c_u$ 是奇数而 $c_v$ 是偶数的时候贡献 $-1$ , 别的时候都是 $1$ . 还是连成完全二分图, 此时不对的贡献在 $x=1, y=-1$ 和 $x=-1, y=-1$ , 于是它可以看成 $(-1)^{c_uc_v+c_v}$ , 我们给 $v$ 的邻接点都连一个自环, 就把它调成对的了.

考虑 $u, v$ 都有自环, 此时贡献是 $-x-y-xy+1$ , $x=1, y=1$ 它是 $-2$ , $x=1, y=-1$ 它是 $2$ , $x=-1, y=-1$ 它是 $2$ . 可以感觉到应该把贡献写为 $(-1)^{(c_u+1)(c_v+1)}$ , 那么还是给 $u, v$ 的邻接点都连一个自环, 如果一个点同时是 $u, v$ 的邻接点则不连, 这样我们得到 $(-1)^{c_uc_v+c_u+c_v}$ , 再整个取反一下即可.

复杂度 $O(\frac{n^3}{w})$ .

Day11

22冲刺day11-A-Subsequence

给定序列 $a_n$ , 其中若干位置已经确定, 要求你在所有空着的位置上填上数, 使得所有区间和是质数.

$n\le 10^5$

诈骗题.

考虑直接求前缀和 $s_n$ , 那么若 $s_i-s_{j-1}$ 为偶数当且仅当差是2, 而因为 $n\ge 2$ 就一定有偶数(而且偶数个数为 $\dfrac{n}{2}$ ), 所以 $n\ge 4$ 的时候无解, 写个爆搜验证一下, 确实.

22冲刺day11-B-Battle

给定空间中 $n$ 个点 $(x_i, y_i, z_i)$ , 每一轮, 若对于一个点不存在点 $j$ 满足 $x_j\le x_i, y_j\le y_i, z_j\le z_i$ , 且两点不相等则点 $i$ 被删掉, 求每个点在哪一轮被删掉.

保证数据随机

$n\le 10^5$ , $x_i, y_i, z_i\le 2^64$

观察大样例发现答案很小( $3\times 10^4$ 的时候答案为 $68$ ), 于是猜测轮数不多.

于是暴力模拟, 把点按 $z$ 排序, 用set维护一个 $y$ 在 $x$ 上的前缀 $min$ (不存在两点 $x_1<x_2, y_1<y_2$ )即可.

注意一开始应该把点离散化.

QYC证实了猜测的正确: 随机数据下三维LIS的长度期望为 $\sqrt[3]{n}$ .

22冲刺day11-C-Competition

$n$ 个人比赛, 每个人有实力 $a_i$ , $i$ 战胜 $j$ 的概率是 $\dfrac{i}{i+j}$ , 没有平局, 现在排成一队, 每次队头的两个人比赛, 赢的人回到队尾, 最后留下的人胜利. 现在你知道你和其余 $n-1$ 个人的实力, 其余 $n-1$ 个人的相对位置确定, 求你插进每一个空的获胜概率.

$n\le 4096$

想到BZOJ4985评分那个题, 于是可以建出一个树的结构.

朴素dp, 设 $f_{i, j}$ 表示点 $i$ 是第 $j$ 个人的概率, 可以做到 $n^3$ (算一个位置 $n^2$ , 一次转移是 $siz^2$ 的).

考虑虽然你自己的位置变了, 但树的结构不会变, 实际上你走一步只是交换了你和另一个相邻人而已.

于是现在只需要更新两个点到根的链上的dp值j即可. 复杂度仍然是 $n^3$ .

考虑实际上不需要算所有点的dp值, 如果这个点是 $x$ 的祖先那么只要保留 $x$ 的, 其他的点只有两种情况( $x$ 在它前面, $x$ 在它后面), 所以复杂度 $n^2$ 了.

22冲刺day11-D-Tree

给定 $Graph(n, m)$ , 求有多少种把 $1\ldots m$ 的全排列分配到 $m$ 条边上作为边权, 求对于所有前 $n-1$ 条边恰好是图的最小生成树的方案中最小生成树的边权和.

$n\le 20$

想起Star MST那个题, 设 $f_{i, S}$ 表示加入了边权前 $i$ 小, 此时要求的前 $n-1$ 条边加入的集合为 $S$ , 转移则枚举新加的边是哪一条, 复杂度是 $n^32^n$ , 这个卡常可过.

优化状态, 考虑只记录 $f_S$ 表示从小到大, 树边状态是 $S$ 的方案数(不会显示枚举值域了), 每次转移往里面添加一条树边, 会让若干条非树边可以在大于这条树边的权值里随便选. 考虑假设最终状态已经确定, 设从倒数第 $i$ 条树边之后又多了 $c_i$ 个边可以随便选, 则方案数是:

$$
\prod_i (\sum_{j\in [1, i]} c_j+i)^{\overline{c_i}}
$$

这个的组合意义是考虑, 一条直线被树边分成若干段, 想象这是一个序列, 那么从后往前的过程中, 每次是push_front一条树边, 然后再后面任意位置insert若干边, 发现插入一条边之后可以选的位置是增加了的所以是上升幂.

于是这个可以dp, 预处理 $cnts_S$ 表示状态为 $S$ 时已经可以随便选的边数, 就能算出这次转移到时候以后的边数.

设 $g_S$ 表示状态 $S$ 的权值和, 然后你发现这个东西完全不会转移权值和.

考虑和从前往后转移是困难的, 因为在加一条边的时候我们不知道前面还有多少条边, 所以无法确定这个边的边权, 但是从后往前的时候, 插入一条树边的贡献是已有的树边个数, 而插入一条非树边时, 设 $a_i$ 表示第 $i$ 条树边现在都权值, 在这一条边可选择的所有位置中, 它有 $a_i$ 种方案插入到第 $i$ 条树边前面, 所以贡献是 $a_i$ , 因为每条树边可以是独立的(我们可以没有必要的跑 $n$ 遍, 每次求所有方案中第 $i$ 条树边的权值和, 最后加起来得到答案, 把这个累加的过程分摊到求和的各步骤同样正确. 另一种考虑方式是转成期望, 用期望的线性性), 所以插入的贡献就是 $\sum a_i=g_S$ .

[think] 期望的线性性对应了排列中贡献拆分后独立性

于是就是说, 由于我们在都已经确定的情况下, 两种方案的计算模型都是从大到小的, 于是从小到大走的时候, $f$ 记录的是一个贡献, 但这个贡献不是当下的, 而是和未来穿插的, 所以对当下的转移就一点用也没有. 而顺着模型走的时候贡献是有其实际意义的–从大到小, 最小生成树的边已经确定了 $S$ 的方案数和权值和.

[think] 当dp时包含的贡献有对应状态的实际意义的时候是更容易思考的.

$g$ 的转移还是困难, 从大到小枚举 $S$ , $S’$ 表示转移到的状态, $cnt$ 是这次变化新的能随便选的树边, $det$ 是插入这些新的非树边的方案数, $x=((m-n-1-cnts_S)+(n-1-\mathrm{popcount}(S))+1)$ , 意思是我们往后插入一条边的时候能插的空的数量:
$$

\begin{gathered}
g_{S’}: =g_{S’}+(g_S+(n-1-\mathrm{popcount}(S)+1)f_S)det\\
g_{S’}: =g_{S’}+cnt \times \dfrac{det}{x}\times g_S
\end{gathered}
$$

第一行是添加一条树边, 第二行是添加 $cnt$ 条非树边. 问题主要在非树边, 考虑一条边加在已经存在的边的所有间隔的方案数相同的, 所以因为我们一共加了 $cnt$ 条边, 一共有 $x$ 个空, 所以每个空里会插入 $\dfrac{cnt\times det}{x}$ 次, 而 $g_S$ 是每个空插一次的贡献, 所以答案就是这个了. 这个先乘再均摊的技巧好像很经典, 但确实不容易被我想到

数数都是神仙题

Day12

评价: C < D < A < B

22冲刺day12-串串匹配

给定长 $n$ 串 $s$ , 再给定 $q$ 个串 $t_{10}$ , 可能有通配符 $\texttt{? }$, 一个 $t$ 种最多有 $4$ 个 $\texttt{? }$ , 字符集是9, 对每个模板串求出现次数.
$n, q\le 2\times 10^5$

降智题, 固定长度的子串只有 $O(n)$ 个. 于是预处理出长度为 $n$ 的有两个问号的所有串, 然后询问的时候也枚举两个问号的位置, 算一下发现能过了.

22冲刺day12-博弈游戏

给定有向图 $Graph(n, m)$ , A, B轮流操作在图上走, A先手, A要最大化经过点的最大值, B希望最小化, 如果一个位置没有出边或者走了 $10^100$ 就结束.
对每个位置走一遍

如果没有环, 可以直接dp设 $f_{u, 0/1}$ 表示从 $u$ 出发, 谁先手的方案, 这个dp用spfa型更新就能过题.

如果有环, 考虑只算一个节点的情况, 二分答案, 把点拆成两个状态表示谁先手, 维护一个 $S$ 表示A获胜的点集, 如果一个A先手的点能走进S就加入S, 如果一个A后手的点所有出边都指向S就也加入S不断做就可以了, 最后所有S以内的点就是A获胜的.

现在考虑可以同时对所有节点处理, 去掉二分, 从大到小枚举答案, S肯定是越来越大的, 就行了.

22冲刺day12-时空限制

给 $a_n$ , 求第 $k$ 小, 数据随机, $n\le 2. 5\times 10^8$ , 内存限制1Mb(不算程序自身), 值域 $v=2^{64}-1$

简单题, 显然分布均匀, 于是值域上相邻两个数间隔期望 $\dfrac{v}{n+1}$ , 那么第 $k$ 小期望在 $\dfrac{kv}{n+1}$ , 于是就读的过程中把值在这个数上下 $C\dfrac{v}{n}$ 的数全存下来, 记录小于这个区间的数的个数, 然后直接求就行了.

STD用了两个堆.

22冲刺day12-弹跳声呐

给树 $Tree(n)$ , 每次在 $t$ 时刻插入一个点 $u$ , 或询问 $t$ 时刻, 对于点 $u$ , 有多少个次在 $(v, t’)$ 的插入满足 $dis(u, v)=t-t’$ .

$n\le 10^5$

点分树, 模板

每层开2个 hash_table 即可. 注意 map 会 TLE. 如果不会去做 “震波”.

Day13

22冲刺day13 子串

给定 $s$ , 对每个 $i$ 求 $s_{1\ldots n}$ 与 $s$ 的 lcp在s中出现的次数.

$n\le 2\times 10^6$

直接看出, 先求每个前缀和 $s$ 的lcp, 然后就是一个前缀在 $s$ 中的出现次数.

第一步直接Z函数, 第二步考虑lcp为 $j$ 表示从 $i$ 开始的有前 $j$ 个前缀, 直接给这些出现次数加1即可. 总复杂度线性.

直接字符串hash+二分也能直接冲.

22冲刺day13 最大子矩阵

给定 $a_n$ , 对每个 $i$ 求不包含 $i$ 的区间的最大权值, 一个区间的权值为区间最小值乘区间长度.

$n\le 2\times 10^5$

求每个前缀和后缀的是相同的. 只考虑前缀.

考虑从左往右扫, 对于一个右端点, 考虑其和每个左端点匹配, 那么首先左端点是当前前缀的后缀min, 所以其出现时间是一个区间, 于是冲一个线段树分治+李超树的2log, 全T了. 不该啊

考虑不用线段树分治, 在线做砍掉这个log: 维护每个左端点的一次函数组成的凸包, 就写一个单调栈, 再同时维护一个凸包, 就行了.

22冲刺day13 匹配

给定 $a_{2n}$ , 进行完美匹配, 对每个 $k$ 求有多少个完美匹配的方案满足有 $k$ 个相交对, 两个匹配 $(a, b), (c, d)$ 相交指 $a<c<b<d$ 或 $c<a<d<b$ .
$n\le 100$ , 膜 $10^9+7$

考虑dp, $f_{i, j, k}$ 表示前 $i$ 个, 其中已经形成 $j$ 个对, 有 $k$ 个左端点在 $i$ 前面而还没找到右端点即可.

22冲刺day13 波波牛的星系

给定 $Graph(n, m)$ 的仙人掌, 根为 $r$ , 无奇环, 有重边, 将边定向从距离 $r$ 小的到距离 $r$ 大的, 求形成的DAG的拓扑序个数.

$n\le 5000$

仙人掌? 考虑圆方树上dp, 那么圆点的dp值代表圆方树的树内的方案数, 然后合并是一个组合数, 硬做就行(

Day14

22冲刺day14-灰烬十字

求 $n\times n$ 的国际象棋棋盘上放 $k$ 个象使得它们无法互相攻击的方案数, 对所有 $k$ 输出答案.

$n\le 4000$

简单dp.

众所周知象棋的象分为黑格象和白格象, 两种是完全独立的.

此时单独拿出来所有黑格/白格去, 那么把它相同长度的行放在一起递增的重排是等价的, 然后dp就行了.

22冲刺day14-斗鸡

给定 $2m$ 个互不相同的区间, 求构造 $a_n$ 使得其中恰好有 $m$ 个区间包含至少两个相同的数.
$2m, n\le 2\times 10^5$

考虑互不相同这个条件, 发现那么让一个区间包含只要给两个端点处相等, 其他区间没有一个会同时包含这两个点.

那么得到一个做法: 按区间长度最大的 $m$ 个的两个端点设为相同的值, 其他的赋成互不相同的即可.

但这个不显然的是假的, 考虑如果有两个区间的端点相同后面的会把前面的覆盖了.

那么修补上这个好像就真了.

22冲刺day14-猪尾巴

求字符集为 $C$ 的 $s_n$ 中不包含长 $k$ 的回文串的有几个. 膜998244353.

$n\le 5000, k\le 25, C\le 998244353$

容斥, 带着系数dp, 设 $f_{i, U}$ 表示前 $n$ 个, 容斥后最最后 $k$ 个位置的并查集为 $U$ , 这里并查集指的是哪些位置值相同, 每次决策当前位置是不是一个回文串. 要预处理 $U$ 的转移. 看起来很爆炸但实际上 $U$ 的种类很少. (因为并查集中每次加 $k$ 条边)

22冲刺day14-香蕉公司

给定排列 $a_n$ , $p_n$ , 一开始 $a_i=p_i=i$ , $A$ 为排列的序列, 满足 $A_1=a, A_{i, j}=A_{i-1, p_j}$ , 若干次操作, 每次交换 $a$ 中两个数, 交换 $p$ 中两个数, 或求 $A_x$ , $A_y$ 的字典序谁更大.

$n\le 2\times 10^5, x, y\le 10^18$

好像还挺容易? 但根本写不动.

由于是排列的置换, 经典的把它拆成环, 考虑 $A_{x, i}=A_{y, i}$ 不同当且仅当这个位置的环长 $l$ 满足 $a_x\equiv a_y \pmod l$ . 考虑线段树维护环的大小, 每个环存在其中下标最小的元素的位置, 这样只要看 $x, y$ 膜一个前缀的lcm是否同余就可以确定是否相同, 于是用这个线段树上二分处理查询, 再经典的用平衡树维护环, 因为维护lcm所以复杂度是 $\log^2 n$ .

lcm可能会溢出, 但是没有关系, 考虑因为取模运算大于被取模的数的数都不用管, 那么就记录成inf即可.

另外考虑, lcm的值域段只有 $\log$ 段, 通过这个可以做到1log.

值得注意的是平衡树维护序列, 支持串接和拆分当然众所周知, 实现的时候平衡树节点是没有满足二叉搜索树性质的键的, 就是我们合并, 拆分的操作不依赖对键值的判断维护其正确性, 而是天生满足了BST的结构, 这样做就不用纠结一开始该给节点赋什么下标, 或者后来需要对BST键值整体加的操作之类的了.

考虑另一种思路是不需要维护lcm, 只要判断 $\vert x-y\vert$ 是否被其中所有数整除, 所以直接维护gcd即可.

最后一个方案是直接根号, 不同的长度只有根号种, 暴力遍历, 因为数据是随的这个跑到比其他的都快.

Day15

22冲刺day15 面试

给定 $a_n$ , 求把它们分成若干组, 每组任意重排, 要求最后没有相邻两元素相同. 最小化组数.

$n\le 10^5$

考虑, 如果出现次数最多的没有出现一半以上, 那一定可以用一组搞定, 因为让两个不相等的数变的相等只会让问题更困难, 而出现次数正好一半的十分好做: 直接插开即可. 而如果那个出现了一半以上, 就把多的部分每个单放一组, 剩下的一起一组.

于是对出现次数排序, 先把最大值插进去, 然后用一个链表一个指针维护着每次往里插入一个颜色的所有位置即可.

22冲刺day15 对赌

打赌, 有 $p$ 的概率赢, $1-p$ 的概率输, 输 $m$ 次你就重开, 不输 $m$ 次但你想开了也可以重开, 重开后会清空胜利和失败记录, 求最少期望多少次可以赢 $n$ 次.

$n, m\le 1000$

直接dp, 就是 $f_{i, j}$ 表示赢 $i$ 次, 输 $j$ 次的期望次数, 于是 $f_{i, j}=\max (pf_{i+1, j}+(1-p)f_{i, j+1} , f_{0, 0})$ , 转移成环, 但只取决于 $f_{0, 0}$ 这一个位置, 直接二分 $f_{0, 0}$ 的值直到推出的值和实际相同即可.

这个题要求期望与实际值绝对误差或相对误差不超过 $10^-6$ , 成功的因为卡绝对误差 $100\to 40$ , 不过qyc也被骗了

如果要求取模, 可以先用实数跑出来实际上每个位置选择重开还是不重开, 然后再用取模的跑出答案.

22冲刺day15 探险

给定 $a_n, b_n$ , 表示了两条折线 $(1, a_1), (2, a_2)\ldots, (1, b_1), (2, b_2)\ldots$ , 保证 $a_i>b_i$ , 于是求现在你选择两条平行线, 要求你可以在平行线内从线段 $(1, a_1), (1, b_1)$ 走到 $(n, a_n), (n, b_n)$ , 中途不穿过折线(可以沿着在上面走), 求平行线之间的最小距离.

$n\le 10^6$

考虑把上折线的下凸壳和下折线的上凸壳求了, 那么一个凸壳要求你选的线必须在凸壳以外, 于是你就枚举上/下凸壳上的边, 去另一个上面求即可.

22冲刺day15 狮子

给定 $a, b, c, p, q, n$ , 求 $\sum_{i\in [0, n]} \sum_{1\le cj\le ai+b} i^pj^q \pmod 998244353$

$n, c, a, b\le 10^9$ , $p, q\le 50$

万欧冲!

Day16

太拉了, 会0题.

22冲刺day16-石头

给定序列 $a_n$ , 每个数有颜色 $c_i\in [0, 1]$ , 每次可以删掉一个数, 此时若相邻两个数和它颜色都不同并且它不在最边上你会获得 $a_i$ 分, 最大化得分.

$n\le 3\times 10^5$

考虑首先一开始序列有若干个连续段, 可以等价把一个连续段看成一个点, 然后其价值是里面数的最大值. 你发现你干的事是每次删掉一个段, 然后合并与它相邻的两个连续段,这个操作等价于每次删掉相邻的两个连续段, 获得其中大的那个的贡献.

现在仍然不会dp/贪心, 发现实际上通过这个策略可以得到原序列的任意一半的连续段, 于是答案是前一半大.

22冲刺day16-序列

给定 $s_n, t_m$ , 求 $s$ 的最长子序列 $s’$ 的长度, 使得 $LCS(s’, t)\le 1$ .

$n, m\le 5\times 10^5$

考虑题目的限制, $a$ 可以在 $b$ 前面出现当且仅当 $a$ 最后一次出现比 $b$ 第一次出现晚.

于是可以接在后面这一关系是传递的. 我天我居然没发现这一点.

那剩下就是线段树优化dp板子.

22冲刺day16-工厂

有 $n$ 个工厂, 每个需要 $1$ 的资源启动, 启动后每 $a_i$ 天生产 $b_i$ 的资源, 中间时刻不生产资源. 一开始你有 $1$ 个资源, 求最短时间把所有工厂启动.

$n\le 16, a_i\le 5\times 10^7, b_i\le n$

考虑假设确定了工厂的依赖关系(谁用谁产的资源启动), 那么时间计算可以是树形dp, $f_u$ 表示 $u$ 子树内的答案, 于是因为由同一个启动的你肯定从时间长的开始启动, 所以就是

$$
f_u=\max_i { a_u \lfloor \dfrac{i}{b_u} \rfloor + f_{v_i} }, \ s. t. \ v_i\le v_{i-1}
$$

于是对着这个dpofdp, 设 $f_{S}$ 表示 $S$ 内点的最小时间, 那么有

$$
f_S=\min_{u, T_1\ldots T_l, \ s. t. \ T_1\cup T_2\ldots T_n \cup {u} } \max_i { a_u (\lfloor \dfrac{i}{b_u} \rfloor + 1) + f_{T_n} }
$$

复杂度是子集内再dp的 $3^n n^2$

可以优化, 考虑设 $h_{u, S}$ 表示以 $u$ 为根, 不算 $u$ , 其余节点的代价, 再把 $b_u$ 个 $T_i$ 一起考虑, 设 $g_{k, S}$ 表示用 $k$ 个子集拼成 $S$ 的 $\min f_T$ , 于是用 $g$ 转移 $h$ , 用 $h$ 转移 $f$ . 复杂度就是 $n3^n$ .

这题有诸多乱搞, 包括什么shuffle点亮次序(这个是对的是因为同时点亮的部分是不计顺序的, 所以可以除掉不少阶乘), 退火, 还有神秘的爆搜和贪心性价比.

22冲刺day16-火柴

$(n-1)\times (m-1)$ 个格子的网格图, 每根火柴可以放在边上或对角线上, 任意两根不能在非端点处相交, 火柴看作边, 与格点形成连通图, 求有多少种方案把一个火柴移动到另一个位置让图仍然连通.

$n, m\le 700$

首先跑个边双缩点成树, 缩起来的点都可以任意连, 现在只考虑树边.

于是对每个树边, 要计算有多少种方式从子树内连出去, 那么用平衡树/hash启发式合并维护子树的外边界, 并且记录不能放置朝外的对角线的边界的个数(如果一个对角线火柴横在子树内外之间你不能放一个跨过它的), 就行了.

Day17

22冲刺day17-磁铁

给定区间 $[l, r]$ , 求区间中使得各位数码乘积最大的数(十进制).

$l, r\le 10^18$

数位dp-模板

22冲刺day17-假牙

Alice 和 Bob 在进行一局酒馆战棋游戏. 他们想让你帮他们算出最后的胜负情况. 每个人初始会有不超过 7 个随从, 这里我们认为每个随从的初始攻击力等于初始血量.
游戏流程如下:
拥有随从数较多的一方会优先发起攻击, 如果随从数相同, 那么双方各有 50% 的概率优先发起攻击.
双方轮流发起攻击, 每一次攻击方发起进攻时, 会选择未被消灭的随从中最左侧的发起过攻击次数最少的随从, 让其随机攻击一个敌方未被消灭的随从. 若 $x/y$ 表示一个攻击力为 $x$ , 当前血量为 $y$ 的随从. 当一个 $x_1/y_1$ 的随从攻击 $x_2/y_2$ 的随从时, 它们会互相造成等同于攻击力的伤害, 即 $y_1$ 会变成 $y_1-x_2$ , $y_2$ 会变成 $y_2-x_1$ . 在一个生物血量小于或等于 $0$ 时, 这个生物被消灭.
当有至少一方的随从全部被消灭时, 游戏结束, 还剩有随从的一方胜利. 若均无剩余随从, 该局游戏为平局.
你需要输出 Alice 胜利, Bob 胜利, 平局分别的概率.

保证 $1\leq n, m\leq 7, 1\leq a_i, b_i\leq 10^9$ .

猜一手状态少, 爆搜过了!

22冲刺day17-冰块

给定 $s_1\ldots s_n$ , 求有多少个本质不同 $(p, q)$ 满足回文串 $p, q$ 均出现在至少一个 $s$ 中且 $p+q$ 是回文串.

$n\le 10^6$ , 3s

考虑 $p, q, p+q$ 都为回文串的条件, 发现此时 $p+q$ 有三个对称轴, 就能产生出许多平移的条件, 结论是:

[trick]若 $p, q, p+q$ 为回文串, 则 $p, q$ 拥有共同的最小整周期.

[trick] 一个字符串本质不同回文子串有线性个.

这个可以考虑SAM的每个等价类, 发现若包含两个回文串则对称两下一定出现次数不一样, 不是一个等价类.

[trick] 回文串的整周期也是回文串.

可以直接感觉一下.

于是就直接hash求所有本质不同回文子串, 再遍历每一个本质不同回文串当做最小整周期, 看它最多重复多少次即可.

22冲刺day17-飞毯

给定正整数 $n$ , 你需要找到一个长度为 $n$ 的 $01$ 串使得本质不同子串个数最大.
$n\le 4\times 10^5$

[trick] 存在 $k$ 满足最优解长度不超过 $k$ 的所有串均出现, 超过 $k$ 的所有区间互不相同. 其中 $k$ 为最大的满足 $2^k+k-1\le n$ 的数.

于是构造长 $k$ 的串均出现的字符串, qyc口中的经典结论是, $2^k$ 个点, 点 $x$ 连向 $2x$ 和 $2x+1$ (以下均在膜 $2^k$ 意义下), 则存在一个欧拉回路. 构造方式是, 因为 $x$ 与 $x+2^{k+1}$ 的出边相同, 均为 $2x, 2x+1$ , $2x, 2x+1$ 这两个都入边集合均为 $x, x+2^{k-1}$ , 所以可以分配出边使得每个点出度, 入度为1. 于是现在有若干个环, 发现一定存在 $x$ 和 $x+2^{k-1}$ 不在同一个环(反证, 如果所有 $x$ 和 $x+2^{k-1}$ 在一个环, 于是所有 $2x, 2x+1$ , 于是所有 $4x+1, 4x+2, 4x+3, 4x+4\ldots$ ), 于是交换两点出边合并环, 最后一定能合并到一个环.

当 $2^k+k-1<n$ 时, 就是要在 $2^{k+1}$ 个点的有向图上找长 $n-k$ 的路径, 每个 $x, x+2^k$ 至少包含一个, 于是先找一个 $2^k+k-1$ 的环, 然后对于每个 $x\in [0, 2k)$ , $x, x+2^k$ 中有一个出边确定, 可以固定另一个的出边, 于是形成若干个小环和找到的答案, 那就用刚才的方式把小的不断合并到大的上, 最后从大环上取包含没有合并的那个大环的一个区间作为答案.

Day18

22冲刺day18-A-Typewriter

求尽可能少的 $k$ 个十进制下不含01的整数加起来为 $n$ .

$n\le 10^100, T\le 1000$

看起来是见鬼分类讨论构造.

首先很容易看成最多用3个, 可能用2个.

不想分类讨论, 选择dp: 直接 $f_{i, j, k}$ 表示最低的 $i$ 位, 向上进位为 $j$ , 现在还有 $k$ 个数不全为 $0$ (意思是, 剩下的数后面的部分都是前导0). 暴力转移.

分类讨论也是可以的, 打个表发现只有某些情况不能用两个, 就构造一个三上去, 反正怎么做都很麻烦.

22冲刺day18-B-Graph

给定 $Graph(n, m)$ , 点有权值 $v_i$ , 所有边权值都是 $1$ . 若 $v_i\mathrm{and} v_j=v_j$ 则加边 $i\to j$ .

$n, m\le 2\times 10^5, v\le 2^20$

看后面那个加边条件考虑FMT, 发现这是个子集和关系, 于是直接FMT优化建图+bfs即可.

来自dwt: 不用FMT, 直接值 $S$ 向 $S-2^i$ 连边即可.

22冲刺day18-C-Cactus

如果一个无向联通简单图的每个点至多在一个简单环中, 我们就称之为点仙人掌.

我们现在定义一个新的概念有根外向点仙人掌, 如果一个有向图是有根外向点仙人掌, 它需要满足:

对于一个有向图, 将其所有的边全变为无向边后是一个点仙人掌;
从某一个节点(根)出发, 可以到达图中的任意节点;
图中的所有环(有向环)与无向图的环一一对应.
其实可以发现, 有根外向点仙人掌就是外向有根树的节点还可以是一个环.

现在 Cuber QQ 要在一个有根外向点仙人掌上随机游走了, 现在这个有根外向点仙人掌的根为 $1$ , 而且他有一个终点顶点的集合 $S$ , 他游走的流程是:

一开始位于节点 $1$
如果当前所在的顶点是 S 中的顶点, 则他会结束游走
如果从当前所在的顶点开始无法走到任意的 $S$ 中的顶点, 则回到节点 $1$ (也相当于都一条边); 否则, 从当前所在的顶点的出边中等概率的选择一个点作为下一个点
返回第二步
Cuber QQ 每走一条边都需要花费一个单位时间(包括回到节点 $1$ 的过程), 现在 Cuber QQ 想知道他随机游走的期望时间模 $p$ 的结果.

$n\le 10^5$ , $p$ 是质数.

考虑树怎么做, 直接dp, $f_i$ 表示从 $i$ 出发的期望, 确定起点dp值 $x$ 之后每个点dp值是 $ax+b$ , 直接dp完解方程即可.

现在有了环, 考虑对于一个环, 设其离根最近的点为 $u$ , 每个点 $v$ 设下一步在环上的概率为 $p_v$ , 走出去期望答案为 $e_v$ , 在设从 $u$ 走到 $v$ 的概率是 $h_v$ , 于是直接 $f_u=\sum_{0}^k h_i(1-p_i)(i+e_i)+\prod p_i(f_u+(s+1))$

22冲刺day18-D-Melody

求 $a_n$ 满足 $a_i\in [1, v_i]$ 且 $\forall i, a_{[1, i]}\ne a_{[n-i+1, n]}$ 的数量, 膜998244353, $n\le 2\times 10^6$ .
$v_i\le v_{i+1}$

它让我们求一个无border串个数.

考虑dp, 设 $f_i$ 表示长 $i$ 的串的方案数, 考虑用总共的减去有border的, 钦定只有最长/最短的有贡献, 发现这里最短的border是性质好的: 一定是一个无border串. 于是就有

$f_n=s_n-\sum_{2i\le n} \dfrac{f_i}{s_i}\times s_{n-i}$ , 其中 $s$ 为 $v$ 的前缀积.

然后所有人都知道下一步分治FFT可以2log, 如果没有这个 $2i\le n$ 的限制我们会直接转求逆1log.

好吧, 分治fft没敢写, 但std确实是在搞2log过 $2\times 10^6$ 啊.

[think] 钦定为最短的发现最短的一定无border这一步是经典trick.

Day19

22冲刺day19-k宝

给定排列 $p_n$ , 有若干位置不确定, 问填数方案使得其最少被 $m$ 个奇偶性相同的子区间完全覆盖.

$n\le 300$

直接dp, $f_{i, j, k, 0/1}$ 表示前 $i$ 个数, 分 $j$ 段, 已经用了 $k$ 个奇数, 最后一段的奇偶性, 暴力转移即可.

22冲刺day19-什么时候

定义一个数列 $c$ 是良好的, 对于整数 $k$ , 当且仅当它满足以下条件:

  1. $0\le c_i\le b_i$ .
  2. $\sum c_i=\sum a_i$
  3. $c$ 数组中至少 $k$ 个 $0$ .

令 $f(k)$ 表示对于所有良好的整数数列 $c$ , $\sum \vert c_i−a_i\vert$ 最小值. 对于 $k\in [0, n)$ , 求 $f(k)$ . 如果不可能满足输出 $−1$ .

$n, a_i, b_i\le 200$

首先一个暴力dp: $f_{i, j, k}$ 表示前 $i$ 个数, 和为 $j$ , 已经有 $k$ 个0的最小值.

考虑因为 $\sum a_i=\sum c_i$ , 答案为 $c_i<a_i$ 部分的两倍, 又因为如果 $c_i<a_i$ , 一定是 $c_i=b_i<a_i$ , 于是贡献就确定了.

$f_{i, j, k}$ 表示前 $i$ 位, 钦定了 $j$ 位是 $0$ , 不等于0的部分 $b_i$ 和为 $k$ , 复杂度 $n^3v$

22冲刺day19-带我上

给定 $n\times m$ 的矩阵, $q$ 次给第 $x$ 行, 第 $y$ 列加1, ( $(x, y)$ 被加两次), 求最后有多少种操作序列使得矩阵中恰好有 $k$ 个格子为奇数.

$n, m\le 2000, T\le 50, k\le nm, q\le 10^{18}$

考虑行和列的相对合并, 设 $f_i, g_j$ 表示操作 $q$ 次后有 $i$ 行翻转, $j$ 列翻转的方案数, 那么显然若 $im+jn-2ij=k$ , 则答案加上 $f_ig_j$ .

于是考虑怎么求 $f_i$ , 一个 $nq$ 的dp是简单的: $f_{i, j}$ 表示 $i$ 次操作, 现在有 $j$ 行被翻了奇数次, 直接转移.

考虑EGF去算组合数, 如果第 $i$ 行是翻转, 那么被覆盖的次数是 $1, 3, 5\ldots$ , EGF应该是 $\dfrac{e^x-e^{-x} }{2}$ , 否则是 $\dfrac{e^x+e^{-x}}{2}$ . 于是最后 $i$ 行翻转的方案数是

$$
z^q^i(\dfrac{e^x-e^{-x} }{2})^{n-i}
$$

$q$ 很大, 但容易看出最后的结果一定是 $\sum a_ie^{ix}$ 形式, 就是说我们没必要把它拆开, 而是直接带着 $e^x$ 算, 此时算出 $k=0$ 之后每次就是卷上一项再除掉一项, 单次线性, 于是复杂度就是 $n^2$ 的.

22冲刺day19-炒饭大师

定义图 $Graph(n, m)$ 的线图 $L(G)$ 为 $G$ 边看作点, 与同一个点相连的边连一个团(就是做朴素点边互换)得到的图. $L^k(G)$ 表示变换 $k$ 次, 问 $L^k(G)$ 的最大独立集, 膜998244353

$n, m\le 2000, k\le 7$

todo

Day20

22冲刺day20-薰衣草

给定序列 $b_n$ , $a_n$ , A, B博弈, A先手轮流, 第 $i$ 次操作可以选择删掉所有 $j$ 为 $b_i$ 倍数的 $a_j$ 或者所有不为 $b_i$ 倍数的 $a_j$ , 游戏结束后得分为剩下的 $a$ 中数之和, A希望最小化, B希望最大化, 求最后得分.
$n\le 10^4, m\le 10^5$

考虑一个人什么时候可以把结果变成0, 考虑一个人操作的数, 如果前面一个数是其他数的lcm的因数, 那么只要让那个数删是倍数, 其他数都删不是倍数, 就全是0了, 如果没有这种情况, 那么考虑必然每个数都要贡献整体的lcm(就是, 每个数都作为整体的lcm的至少一个质因子的最大值), 于是lcm最小是前若干个质数的乘积, 而且若lcm大于值域, 只要每个数都删不是倍数的就删空了. 所以一个人最多操作14次, 两个人28次就会全0.

于是如果 $m>27$ , 那么两个人都有能力把结果变成0, 此时结果显然是0.

于是现在 $m\le 27$ , 可以直接写爆搜, 因为一个数每次只会进入一个分支, 所以搜的每一层的总数都是 $n$ , 复杂度是 $nm$ .

22冲刺day20-风信子

求下图的最大流: 源点为 $S$ , 汇点为 $T$ , 包括源汇总共 $n+2$ 个点. $S$ 向 $i$ 连边, 流量为 $a_i$ ; $i$ 向 $T$ 连边, 流量为 $b_i$ ; $i$ 向 $p_i$ 连边, 流量为 $c_i$ . 保证 $p_i\ne i$ .

$n\le 10^6$

考虑这是内向基环树森林, 那么显然可以直接确定叶子: 先尽可能流汇点, 多的流到父亲, 于是现在剩下若干个环, 只要让每个环推流两遍就一定都推完了.

22冲刺day20-栀子花

给定 $a_n$ , 单点修改, 或者询问区间 $[l, r]$ 中有多少子区间 $[l’, r’]$ 满足 $a_{l’+i-1}\ge i$ .

$n, q\le 10^6$

先给每个位置减去下标, 判定标准变成 $\forall i\in [l, r], a_i\ge -l$

考虑类似CF1736C, 设 $r_i$ 表示一个左端点对应最大右端点位置. 发现我们只会改小不会改大, 改小是把前面一个区间取 $\min$ , 发现改大的时候左边的 $r$ 会延伸到我们也不知道哪, 但你应该意识到这就说明考虑 $r$ 的变化是走不通的, 不如考虑 $r$ 实际上是什么. 因为限制是 $a_i\ge -l\Longleftrightarrow -a_i\le l$ , 所以把 $a_i$ 取负似乎更好, 此时发现每个 $r$ 就是前缀最大值, 设第 $i$ 个前缀最大值为 $m_i$ , 则对应左端点为 $m_i-m_{i-1}$ .

于是我们要求的就是

$$
\sum_{j=2}^k (m_i-m_{i-1})\times p_i
$$

那么可以用数据结构维护前缀max, 比如楼房重建线段树, $calc(x, y)$ 表示 $x$ 对应区间左边插一个 $y$ 的答案, 那么情况就是左区间最大值大于它, 就是左区间的这个和右区间维护的以左区间最大值位 $x$ 的, 左区间最大值小于就只有右区间, 去算就行了. 说是可以线段树套可持久化平衡树. 复杂度也是2log.

考虑因为只有单点修改, 所以扫描序列维维护时间维, 那么要做的就是每次区间取max, 查询是问一个点历史的这个信息, 问题是不是前缀询问啊?

发现实际上从某个左端点开始相当于赋初值 $l-1$ 即可, 每个查询都在一个单独的时间上即可.

22冲刺day20-郁金香

给定 $k\times k$ 网格图, $(x, y)$ 与 $(x+1, y), (x, y+1)$ 连长1的边, 另有 $n$ 条边从 $(x_i1, y_i1)\to (x_i2, y_i2)$ , 边长为距离减1, 求每个无序点对的最短路长度之和.
膜 $998244353$ , $n\le 500, k\le 10^9$

从 $(a, b)\to(c, d)$ , 假设 $a<c, b<d$ .

那么这是一个向右下走的过程, 容易发现因为特殊边只能节省1, 所以我们确实只会向右下走而不会有向左向上.

于是把横纵坐标离散化, 现在分别只有 $n$ 个, 一共就有 $n^2$ 个点和 $n^4$ 个点对, 在这上面算, 复杂度 $n^4$ .

考虑只枚举一个左上角, 此时第 $i$ 个特殊边的终点相当于对一个右下角矩形取max $dis_i$ , 其中 $dis_i$ 是左上角能到它经过的最多特殊边数, 最后查询全局和. 此时发现取同一个 $max$ 的一定是一个阶梯状, 于是扫描线扫max用set维护这条阶梯状分界线的所有拐点, 维护圈起来的面积, 每次插入一个矩形的时候就是从这条轮廓线上找到对应位置把这个矩形的轮廓并进去, 删掉里面的并更新面积, 复杂度 $n^3\log n$ .

考虑问题的性质, 发现若一个位置被取max了 $a$ , 一定在这之前被取max了 $a-1$ , 因为能走 $a-1$ 条特殊线的终点一定可以到达走 $a$ 步的, 于是可以对每一层分别算矩形面积并再加起来, 这个面积并不用线段树维护扫描线, 因为扫描线上区域只变多不变少(每一层都是阶梯). 复杂度 $n^3$ .

Day21 赠送赛

打开题, 怎么是XIX OpenCup Grand Prix of Gomel原题.

[19金华普及线下]串

给定 $s_n$ , 求有多少有序对 $(i, j, k)$ 满足 $[j+1, k]$ 可以由 $[i, j]$ 拓展而成, $t$ 的拓展是串 $a_1, a_2, \ldots a_k$ 串接起来, 其中 $a_1=t$ , $a_i, a_{i-1}$ 至多只有一个字符不同.

$n\le 10^5, \vert \Sigma\vert \le 10^6$

考虑 $n^2$ 做法, 枚举一个 $[l, r]$ , 若 $[l, r]$ 与 $[r+1, 2r-l+1]$ 只差一个, 则以 $[l, r]$ 开头的方案数等于 $[r+1, 2r-l+1]$ 的方案数加1.

考虑枚举长度 $L$ , 每 $L$ 个分一块, 那么按照求平方串的经典科技求一下这种差1的平方串(只要多求一次lcp, lcs), 表示为若干起点在 $[l, r]$ 的串, 因为 $[l, r]$ 只有 $\dfrac{n}{l}$ 个, 然后上面那个dp的转移旨在膜 $L$ 等价类内进行, 所以按照余数从小到大扫描线, 用set维护起点形成的连续段, 总复杂度2log.

[19金华普及线下]树

todo

[19金华普及线下]图

就是线图的线图