CF 1418 题解
A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小...
A考虑分步做合成 coal 和合成 craft 。发现我们做 $n$ 次替换后拥有的 stick 数量是 $nx-n+1$，首先要凑出 $k$ 个 coal，然后还要剩下来 $k$ 个 stick 合成，所以我们造 stick 的限制就有 $nx-n+1 \geq ky+k$，这样 $n$ 就是交易 stick 用掉的次数了，再加上 $k$（交易 coal 的次数）B把未被锁定的位置从大到小...
A考虑 dp。设 $f_{i,0/1}$ 表示考虑到根是 $i$ 前缀，最后一次删除的串长度为 $2/3$ 的方案数。转移就判断一下两次长度相等是否子串相等即可。B这种最长的最短路链问题贪心超过两步都是错的。首先 $O(n^2)$ 预处理 $dis_{i,j}$ 表示 $i \to j$ 的最短路，注意到贪心一步是正确的，我们去枚举 $b,c$，预处理最远，次远，第三远的点即可（因为路径不...
A首先肯定位数越多越好，所以先用尽量多的放 $1$。然后看一下能否用最后一个把最高位上的 $1$ 换成更大的数字（实际上你只能换成 $7$）B处理处原串每个前缀的权值 $a_i$。如果 $a_n=0$ 并且存在权值为 $x$ 的前缀就有无数个，否则就是所有形如 $x+ka_n,k \in \mathbb{N}$ 的权值的前缀的个数。C如果 $s$ 的字符集不包含 $t$ 的字符集就无解。否则...
A设 $f_i$ 表示长度为 $i$ 的答案。考虑开头的元素：首先它只能选择 $\{1,2\}$。如果选择了 $1$，那么变成了 $n-1$ 的子问题；如果选择了 $2$，那么第二个数必须选择 $1$，变成了 $n-2$ 的子问题。所以 $f_i = f_{i-1}+f_{i-2}$，注意到斐波那契数列的通项公式是 $f_n = \frac{1}{\sqrt 5}[(\frac{1+\sqr...
A根据期望的线性性，现在转变成了求每个点有多少概率是被自己覆盖的：显然是要在子树内第一个被选中的，所以答案就是 $\sum_{i=1}^n \frac{1}{sz_i}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define...