JOI 2018 Final 简要题解
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
博主已经退役，评论可能会审核很久才能通过。
博主已经退役，评论可能会审核很久才能通过。
寒冬暖炉 同 CF1110B Tape。 先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。 代码 美术展览 显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。 设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。 因此我们从后往前扫，维护 ...
Codeforces Luogu 分析 容易想到设 $dp_{i,j}$ 表示 $j$ 次操作后 $i$ 的期望大小，转移直接枚举约数即可。然而这样子显然是会 T 的... 注意到当 $\gcd(i,j)=1$ 时有 $dp_{i\times j,k}=dp_{i,k}\times dp_{j,k}$，因此我们可以将 $n$ 分解为 $p_1\!^{c_1}p_2\!^{c_2}\cdots...
Luogu LOJ 分析 这个东西显然是有循环节的。 假设 $t_1$ 和 $t_2$ 两时刻 $x,y$ 相等，那么有 那么如果输入的区间中有长度 $\geq$ 最小循环节长度的，直接输出最小循环节长度；否则问题变为区间覆盖，按左端点排序后扫一遍即可。 代码 // =================================== // author: M_sea // we...
UOJ 分析 我们先假装原图是个二分图。 我们可以先想办法求出原图的一棵生成树，那么对其黑白染色即可求出答案。 一个暴力的做法是尝试删掉所有边，如果删掉某条边后连通性发生改变则这条边在生成树上，保留这条边，否则删掉这条边。这样子询问次数是 $\frac{n(n-1)}{2}$。 事实上我们可以每次二分下一条树边的位置：如果删掉 $[L,mid]$ 中的边后图仍连通则下一条树边在 $(mid,...
BZOJ 分析 $[l,r]$ 的非空子集数为 $2^{r-l+1}-1$，而子集贡献数至多为 $1000(r-l+1)$。 当 $2^{r-l+1}-1>1000(r-l+1)$ 即 $r-l+1>13$ 时，根据抽屉原理显然有解，因此直接输出 Yuno 即可。 先考虑操作 $1$ 怎么做。用树状数组维护每个点被修改的次数，然后倍增即可求出答案。 再考虑操作 $2$。设 $dp...
LOJ 分析 我们把 $i$ 向 $p_i$ 连边，这样子会有很多环。可以发现，如果有奇环则无解，所以我们只考虑偶环。 显然一个偶环上只会是一个 (、一个 )、……，但是如果直接搜的话复杂度最大会达到 $\mathcal{O}(2^{\frac{n}{2}})$，无法接受。 考虑一个大小为 $2$ 的偶环，显然小的那个填 (、大的那个填 ) 更优，因此我们只需要搜大小 $\geq 4$ 的环...
BZOJ 分析 首先我们可以得到 $k$ 至少为 $\frac{n}{2}$，构造方式是令 $m=2$。 也就是说，在最优解中每个数被选中的概率是 $>\frac{1}{2}$ 的。 考虑 rand() 一个在最优解中的数 $x$，我们把其它的 $\neq x$ 的数与 $x$ 作差并分解质因数，那么所有质因数中出现次数的最大值加上 $=x$ 的数的数量就是当前最大的 $k$。 这里有...
Codeforces Luogu 分析 首先可以知道，我们执行操作的顺序一定是赋值 $\to$ 加 $\to$ 乘。 先考虑只有乘的情况。因为我们要最大化所有数的积，因此直接选最大的 $m$ 个即可。 再考虑有加的情况，我们想办法把加转化为乘。对于每一个位置，我们把对它的加操作按权值从大到小排序，显然我们选的会是一段前缀，因此我们可以转化为一些乘 $\displaystyle\frac{\s...
传送门 勇者比太郎 看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。 预处理前缀和后枚举每个 J 计算即可。 代码 画展 先以 $V_i$ 为第一关键字、$S_i$ 为第二关键字对所有画排个序，以 $C_i$ 为关键字对所有画框排序。 然后从后往前扫，如果当前的画能装进没有装画的 $C$ 最大的画框里，就把它装进去。 正确性比较显然？反正我不会证 代码 有趣的...
Codeforces 分析 题目给的操作就是区间异或。考虑将原数组差分，那么我们相当于每次可以将两个距离为 $a_i$ 的位置异或 $1$，然后求从全 $0$ 数组生成原数组的最小步数。 我们将这个东西反过来，变为求原数组的差分数组生成全 $0$ 数组的最小步数。 注意到原数组的差分数组至多有 $20$ 个 $1$，因此可以考虑状压 DP。 设 $dp_{S}$ 表示 $S$ 中的 $1$...