又做了几个杂题

CF1305F Kuroni and the Punishment

给定 $n$ 个数. 每次可以选择将一个数 $+1$ 或 $-1$ . 求至少多少次操作使得整个序列都是正数且全部元素的 $\gcd>1$ .
$n\leq 2\times10^5, 1\le a_i\leq 10^{12}$ .

答案不超过 $n$(全调成偶数).

值域很大, 直接做要求一些 $\sum a_i\bmod g$ 状物, 是困难的, 考虑因为答案不超过 $n$, 那么至少有一半的数被操作至多一次, 于是随一个数, 再随一种操作, 它被这么操作的概率有 $\dfrac{1}{6}$, 随错了的是 $\dfrac{5}{6}$, 那么只要随比如 $50$ 组就行, 然后对着这些可能的操作分解质因数, 只对它们的约数作为gcd去求答案即可.

哦, 一直以为cf的possibilities都是概率期望题, 结果是随机化

CF605E Intergalaxy Trips

  • $n$ 个点的有向完全图.
  • $i \to j$ 的边每天出现的概率均为 $p_{i, j}$, 若 $i = j$, 有 $p_{i, j} = 1$.
  • 每天可以选择一条存在的出边走过去或停留在原地不动.
  • 求最优策略下从 $1$ 到 $n$ 的期望天数.
  • $n \le 10^3$.

首先不考虑转移成环的问题, 你能列出一个式子:

$$
f_u=\min_q \sum_i f_{q_i}(p_{q_i}) \prod_{j<i} {1-p_{q_j}}
$$

然后考虑, $q$ 一定是比你当前更优的点(否则你选择停留而不是走), 于是当前值最小的点就已经确定了, 可以用它更新其它点, 于是复杂度就是 $n^2\log n$ 了.

重点是搞出一个转移顺序.

CF1093F Vasya and Array

给出一段长度为 $n$ 的整数序列, 一个正整数 $k$ , 一个正整数 $len$ , 序列中的所有数均在 $1$ ~ $k$ 之间, 或者等于 $-1$.

如果没有长度大于等于 $len$ 的连续相同数字则该数段是好的.

可以将 $-1$ 改为所有 $1$ ~ $k$ 之间的整数, 将该数列变为好的, 求出方案数, 对 $998244353$ 取模

$len, n\le 10^6, k\le 100$

看起来这是个 $nk$ 的复杂度, 那么想设 $f_{i, j}$ 表示 $i$ 的值为 $j$, 发现直接转移这个限制不好做, 联想起HNOI卡农那个题, 枚举一个 $l$, 用总的方案减去最后恰好长 $l$ 的相等段的方案, 那么总的方案直接从 $f_{i-1}$ 转移过来, 而长 $l$ 的第一反应应该是 $\sum_{k\ne j} f_{i-l, k}$, 要求 $k\ne j$ 是因为不然他们在 $i-1$ 处就已经爆了.

CF1556F Sports Betting

有 $n\ (n\le14)$ 个人, 两两之间会打比赛. 每人有一个实力值 $a_i$, 在 $i$ 与 $j$ 的比赛中, $i$ 有 $\frac {a_i}{a_i+a_j}$ 的概率获胜, 其他情况则是 $j$ 获胜. $i$ 在与 $j$ 的比赛中获胜则称 $i$ 打败了 $j$. 若 $i$ 打败了 $j$, $j$ 打败了 $k$, 则认为 $i$ 也打败了 $k$. 若 $i$ 打败了除了他自己以外的所有人, 则称 $i$ 是一个 Winner(是否打败了自己不要求), 注意 Winner 可能有多个. 现在你需要求出 Winner 的期望数量, 对 $1e9+7$ 取模.

$n\le 14$

容易想到累加每个点成为 Winner 的概率.

那一个点成为Winner相当于给边定向, 要求有一棵以它为根的根向树, 大概会想设 $f_{S, i}$ 表示以 $i$ 为根, $S$ 中的点都有到 $i$ 的路径的概率, 但是一次转移一个点不能处理当前被加进去的点先连到没被加进去的点再连到 $S$ 中点的情况, 所以你要一次转移一层, 设原来层为 $S$, 然后要转移到 $T\supset S$, 那么就要算 $T-S$ 中的点连向 $S$ 中的点的概率, 存在不好表示, 可以考虑转移 $T-S$ 中点都没连到 $S$ 中的概率, 这个就是其中每个点都没连过去的概率乘起来做完了.

另一个想法是, 这是竞赛图, 那么缩点成一条链, 个数就是链上第一个SCC的大小, 对这个dp.

CF1254D Tree Queries

给定一棵 $N$ 个节点的树, 有 $Q$ 次操作

$1\space v\space d$ 给定一个点 $v$ 和一个权值 $d$, 等概率地选择一个点 $r$, 对每一个点 $u$, 若 $v$ 在 $u$ 到 $r$ 的路径上, 则 $u$ 的权值加上 $d$ (权值一开始为 $0$)
$2\space v$ 查询 $v$ 的权值期望, 对 $998244353$ 取模
$1\leqslant N, Q \leqslant 150000$

容易想到, 对每个点分开看贡献, 则一次对 $v$ 的修改对 $u$ 的贡献是 $n-siz_v$ 或 $n-siz_w$, 其中 $w$ 为子树包含 $u$ 的 $v$ 的儿子.

于是你现在做这个修改是 $O(son\log n)$ 的, 考虑把修改上移一位记录在父亲上, 这样一个点的答案就是 $\sum siz_v w_{fa_v}$, 这种儿子关于父亲的显然只有一条链能维护, 树剖就赢了单log.

我认为点分也可以.

CF1737E Ela Goes Hiking

$n$ 只蚂蚁站成一排, 第 $1$ 只蚂蚁左边和第 $n$ 只蚂蚁右边各有一个挡板, 相邻两只蚂蚁的距离、第 $1$ 只蚂蚁与左边挡板的距离和第 $n$ 只蚂蚁与右侧挡板的距离相等. 初始时每只蚂蚁重量相等, 每只蚂蚁有 $\frac{1}{2}$ 概率向左运动, $\frac{1}{2}$ 概率向右运动, 每只蚂蚁速度相同. 中途蚂蚁不可主动改变方向, 如果碰到挡板则向相反方向运动, 若两只蚂蚁相遇, 重量大的蚂蚁会把重量小的蚂蚁吃掉, 重量变为两者之和, 如果重量相同, 向左运动的蚂蚁会吃掉向右运动的蚂蚁. 求对于所有 $i\le1\le n$, 第 $i$ 只蚂蚁成为最终的存活者的概率对 $10^9+7$ 取模.

$n\le 10^6$

注意速度一样和一开始重量一样. 于是过程是每只向左运动的都会干掉前面连续的向右运动的, 现在还剩下若干向左的, 然后每次前两个决斗剩下一个. 现在要求一个位置 $i$ 成为最后的概率, 要求它要能干掉前面的也就是 $\lfloor \dfrac{i}{2}\rfloor$ 到 $i$ 应该被分成一段, 前面的方案是 $2^{\lfloor i\rfloor}$, 然后它的重量会变成 $i$, 则它干掉后面的概率 $g_i$ 可以枚举它干掉的第一个人 $g_j, j\in [i+1, 2i-1]$, 就能dp了.

CF1835C Twin Clusters

给定 $2^{k+1}$ 个 $[0, 4^k)$ 内的整数, 请求出任意两个不交非空区间使得其异或和相等, 若无解则输出 -1.

$k\le 17$

首先鸽子原理是不是 $2^{k+1}(2^{k+1}-1)/2$ 比 $4^k$ 大将近一倍, 一定有解.

不要鸽子原理了随机你还学过生日悖论, 随一个区间期望 $2^k$ 次相同.

更好的是再砍一半看鸽巢, 你考虑前 $k$ 位有 $2^{k+1}+1$ 种, 那么至少有 $2^k+1$ 个前 $k$ 位相等的对, 又因为后 $k$ 位只有 $2^k$ 种于是又必然出现两个一样的, 于是就做完了.

CF513G123 Inversions problem

有长度 $n$ 的 $n$ 阶排列 $p_i$, $k$ 次操作, 每次等概率反转一个区间, 求最后逆序对的期望. 误差 $<10^{-9}$ 即可.

$\textrm{task} 1: n \le6 , k\le4$.

$\textrm{task} 2: n \le30 , k\le200$.

$\textrm{task} 3: n \le100 , k\le10^9$.

考虑套路, 把它转化成对两个数一个数在另一个数前的概率, 然后你设 $f_{i, j, k}$ 表示操作 $i$ 次, $j, k$ 两个数交换了的概率是多少, 这个直接枚举翻转区间再搭一个前缀和就是 $kn^2$, 然后比较离谱的是, 显然操作的越多就越接近随一个序列, 所以在答案变化量在精度以下时直接停, 大概1000轮就行了.

CF1218A BubbleReactor

基环树, 你可以先选中一个点, 以后每次选中一个与已经选中的点相连的点, 选一个点的贡献是与它连通的未选点个数.

$n\le 15000$

假设根已经确定, 则树上每个点的贡献是确定的, 只要考虑环的部分, 问题变成给一个环, 每个元素有权值, 选择起点会获得起点的权值, 以后每次从左或从右选一个删掉贡献是还在的权值的和, 容易做到 $n^2$, 然后你没想到的是这题std $n^2$ 过 $15000$

P4733 [BalticOI 2015] Tug of War

由于一共 $2n$ 名选手报名参赛, 所以一个队有 $n$ 名队员. 一根绳上左右两边各有 $n$ 个点. Byteland 的拔河精英们都很挑剔, 每个参赛选手在左右两边都有一个他们想要站的位置. 此外, 你知道每一个参赛选手的力量值 $s_i$.

组织者现在问你如下的问题: 给定一个整数 $k$, 能否分出两个队, 这两个队各有 $n$ 名选手, 并且他们站在他们想站的位置(当然不能有两名或以上选手站在同一位置), 双方力量和之差不超过 $k$?

$n\le 3\times 10^4, s_i\le 20$

考虑把两边的位置看成点, 选手看成边, 则就是要给边定向让每个点只有一个入度, 那条件显然是是基环树森林, 然后每个基环树森林只有两种选法要拿它们跑背包, 因为和为 $n$ 大小只有根号种, 多重背包就过了, 或者bitset也能直接冲.

基环树判定可以拓扑排序后判环.

CF335E

纯数学/fn题

CF1874D

$n$ 个点随机游走, 你一开始在 $0$, 你在 $i$ 有 $\dfrac{a_i}{a_i+a_{i+1}}$ 的概率走到 $i-1$, 其他情况走到 $i+1$, 请你分配 $a_i$ 使得总和不超过 $m$ 情况下期望时间最小.

$n, m\le 3000$

首先常规列式子 $f_i=\dfrac{a_i}{a_i+a_{i+1}}f_{i-1}+\dfrac{a_{i+1}}{a_i+a_{i+1}}f_{i+1}, f_n=0$, 展开它的系数, 列出是 $f_0=f_1+1, f_1=f_2+\dfrac{a_1}{a_2}$, 不断展开, 最后就是 $f_0=\sum_{j<i} \dfrac{a_j}{a_i}$

这个可以dp, 直接做就是 $n^3$, 另外注意到若 $j<i, a_j>a_i$, 那交换 $a_j, a_i$ 只会改变 $\dfrac{a_j}{a_i}$ 项其他项不变, 于是易得 $a$ 单增, 于是可以做到 $n^2\log n$

某PYYZ题

picture 0

求得分是简单的, 然后从头开始遍历, 每次看位置 $i$ 最大是多少, 二分这个位置的值, 就要判定后面的区间, 只要开值域线段树维护匹配, 注意到左子树到右子树又是都能匹配的, 于是直接维护 $a, b$ 中未匹配的数量和匹配数即可, 每次单点修改判断.

DWT某模拟赛题1

是https: //codeforces. com/gym/104114的I

有序列 $a_n$, 每次把 $a_i, a_{i+1}$ 设为设为 $\max (a_i, a_{i+1})-1$, 求最少次数变成 $0$

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

从大到小贪心做, 考虑让所有数都由 $x$ 变化为 $x-1$ 的次数, 则这些数构成若干连续段, 每个连续段需要用 $\lceil \dfrac{x}{2} \rceil$ 次操作, 就做完了.

DWT某模拟赛题2

同场的K

给定无向带权图, 保证对任意 $u\to v, \vert u-v\vert \le 10$, $q$ 次询问两点最短路
$n\le 10^5, q\le 5\times 10^4$

分治, 对于 $l, r$ 选出 $mid$ 左右各 $10$ 个点, 然后用它们跑区间中的点的单源最短路并更新询问两个点都在区间中的(不要求跨过 $mid$), 再把没跨过的递归下去即可.