Atcoder Code Festival 板刷

· · 个人记录

你都在刷些什么啊

下面所有题目中标 [★] 的代表比较有趣或者比较 educational，值得一做的题，标 [!] 的表示我还不会做，基本是巨大毒瘤题。

2014

code-thanks-festival-2014-a-open

A - カメツル算

输出 4A+2B。

B - バッジ

显然前面一直是若干个 ABC 的循环节，因此无论怎么交换顺序都无所谓，只有最后一个不超过 A+B+C 的部分需要尽量快完成，于是将 ABC 按照效率从高到低排序，然后模拟即可。

C - コンテスト

直接求和。

D - 定期券

对于每个询问直接计算有多少个铁路是免费的，用剩下的数量乘上 100 即可。

E - 儀式

直接枚举忘记了哪个操作，对剩下的操作直接二维差分并最后再二维前缀和回来即可。

F - 順位表

数出有多少个人一定比高桥的排名靠前（直接 dfs 即可），这个人数 +1 就是高桥的排名。

G - 通勤電車と気分

因为两种都是选择编号最小的座位，所以容易归纳证明对于所有当前的选择状态，相邻两个被选的位置差不超过 2。所以遇到一个一类的时候就优先填充前面的空位，遇到二类的时候就填在原先的 \max+2 处。

于是可以设计一个 dp：f_{i,j,k} 表示考虑了前 i 个人后，下标 \max=j 且前面还有 k 个空座位的概率。直接暴力转移即可，总时间复杂度 O(NK^2)。

[★]H - 模様替え

考虑枚举符合条件的中心点。首先判断两个矩形是否是旋转后相等的可以使用哈希 O(1) 解决。

于是现在只需要看一个方向（如左上方向），直接把右下角当作是中心点。考虑求出周围一圈所有符合条件的矩形的外轮廓，这样任何一个轮廓内的矩形都是符合条件的。

如何求出外轮廓呢？从最左侧开始找到第一个合法位置，每次尝试往上移动，如果往上移动会导致不合法就考虑往右移动（显然此时一定仍然合法）。

于是这题就做完了，时间复杂度 O(RC(R+C))，稍微有一些细节。

code-thanks-festival-2014-b-open

A - 朝食

输出 \max(a,b)。

B - 電卓ゲーム

枚举一下两个符号，四种情况取 \max 即可。

C - 人気投票ゲーム

对于每一个地区判断一下是否过半直接加起来。

D - 足ゲーム

开个桶，对于每个 a_i 在所有 ka_i 处全都 +1 然后统计最大值即可。

E - マスゲーム

直接暴力染色然后判断起点和终点是否在同一个连通块里。

F - 太鼓ゲーム

直接暴力匹配检查出哪些位置可以匹配一个 S 或一个 T，然后直接从前往后 dp 一遍。

G - 石取りゲーム

记 f_{i,j} 表示剩余 i 个石子，第一次最多能取 j 个时先手必胜还是后手必胜，转移时暴力枚举第一次取多少个。

H - しりとりゲーム

众所周知无向图存在欧拉路径需要满足以下条件：

  1. 所有的边都在同一个连通块里（即只能有一个连通块和一堆孤点）
  2. 只能有 0 或 2 个点的度数为奇数

于是直接加边即可，注意连接连通块的时候优先使用奇点连接。

code-festival-2014-morning-hard

A - eject

容易推得答案为 \dfrac{1-(1-2p)^n}{2}。

B - ぽよぽよ

令 f_{i,j} 表示考虑到第 i 个数且值为 j 的方案数，直接做是对的，但是会超时。

发现 p 大 l 小，于是把 j 的含义改为 a_i-p_i，再前缀和优化。

C - 宝探し 2

维护每种颜色出现次数的前缀和，这样查询时直接 O(K) 回答，修改时发现交换最多对一行或一列产生影响，因此也直接修改那一部分，总复杂度 O(NMK+Q(N+M+K))。

[!]D - Rail Tour

大构石计算几何，下次再补。

code-festival-2014-final

A - 50m走

输出 \dfrac{50}s。

B - 暗算ゲーム

按题意模拟。

C - N進数

显然 f 是不减的，而我们又知道 10^{16} 的答案是 10000，因此直接在范围内暴力枚举。

D - パスカルの三角形

众所周知 \binom n1=n。

E - 常ならずグラフ

从第三项开始枚举，如果 a_{x-2},a_{x-1},a_x 不形成一个波浪，那么这三个中一定要删去一个，显然删去 a_{x-1} 最优，于是做一遍到结束就是答案。

F - 誤情報

发现 b 合法的充要条件为 \forall i,\gcd(b_{i-1},b_{i+1})\mid b_i。于是分别以 1,2,3 为起点扫一圈，遇到 \gcd(b_{i-1},b_{i+1})\nmid b_i 就把 b_{i+1}\gets\gcd(b_i,b_{i+2})。

[★]G - 魔方陣

第一反应肯定是分解质因数然后把问题转化成指数上的，也就是与 sum 相关的问题。

对于一个中心是 n 的 3\times 3 网格，能填入的合法的 sum 矩阵数量是容易计算的。注意这个时候并不需要满足元素互不相同。

但是问题就出在这里——如果把所有的方案全都相乘，其实最终答案就会算到含重复的情况。我们需要去掉这些情况。

仔细思考一下，我们发现会出现重复的矩阵只有以下几种：

\begin{array}{|c|c|c|}\hline A&A&A\\\hline A&A&A\\\hline A&A&A\\\hline \end{array}\quad \begin{array}{|c|c|c|}\hline B&D&B\\\hline A&A&A\\\hline C&E&C\\\hline \end{array}\quad \begin{array}{|c|c|c|}\hline B&C&A\\\hline C&A&B\\\hline A&B&C\\\hline \end{array}\quad \begin{array}{|c|c|c|}\hline D&B&B\\\hline F&A&G\\\hline C&C&E\\\hline \end{array}

容易发现这些情况的数量都是好算的（因为在 A 确定时后三种情况只与 B 和 C 的取值有关，所以可以根据这个计算出 B 和 C 的范围），于是把它们全都减掉即可。

注意我们算出的方案数是带有旋转和翻转的，最后再除以 8 就是答案。

H - 部屋割り

容易发现其实如果把房间人数当作一个可重集，那么它就一直是确定的，变化的只有相同人数的房间的下标。

因此直接记录所有人数为 x 的房间数，编号和等然后模拟。

[★]I - Shapes

看到斜着的正方形先把它用类似曼哈顿距离转切比雪夫距离的方法转成与坐标轴平行的正方形。因为正方形的边不相交，所以我们可以建出由直接包含关系（即 i\to j 等价于 i 包含 j 且不存在 k 满足 i 包含 k 且 k 包含 j）构成的森林。

容易发现这个时候答案为两个点在正方形森林上的距离（边数）。对于不连通的情况，可以认为整个平面就是一个巨大的正方形，即加一个虚点连接所有根。

[★]J - 2つのカップ

首先显然对于 a,b 不互质的情况，可以令它们同时除以 \gcd(a,b) 而不影响答案。于是下面默认 a,b 互质。

特判掉 k=0 的情况，于是我们用一步可以做到 0,a,b。不妨设 a>b。

对于当前两个水杯分别装了 x 和 y 的水的情况，把它视作一个点 (x,y)。这样所有的状态就是一个 (0,0) 为左下角，(a,b) 为右上角的矩形上的所有整点。注意矩形内部的点是无法取到的。

这个时候三种操作对应到网格上就是左右、上下、以及左上或右下方的移动，而且必须从矩形的边界一直移动到下一个边界。

那么因为 0,a,b 一步就能取到，所以沿着边界移动到四个角的操作都是没有意义的。那么每个点实际上就只有两种移动方向。

于是，我们发现从左上角出发，每次沿着之前没走过的方向移动，直到右下角，就可以经过网格中除了 (0,0) 和 (a,b) 以外的所有点，而且不会重复经过。可以参考一下官方题解的图。

我们发现一旦到了最右边的那条线我们就会立即向左回到最左边那条线，所以我们不如把整个网格复制无数遍，于是我们的操作就是不断向右下和向上移动。

考虑什么时候的状态会得到新的 c。因为我们已经知道它不会经过重复的点，而且总共经过了 a 个不同的 y=0 点。那也就是说每次到达一个 (x,0) 时 x 都是一个新出现的 c。

当然其实也会出现例外，如果在到达 (x,0) 之前碰到了一条边界上的竖线穿过了 (0,x)，那么 (0,x) 处就是出现 x 的第一个地方了。

容易发现我们能够到达这些状态的方法只有从这条折线的左边或右边出发向另一侧移动。显然答案应该是左边能得到的个数加上右边能得到的个数（如果左右出现重合那答案就是 a+1，其实这个可以提前判掉）。这里就只说怎么从左边算，右边同理。

但是因为竖线产生的干扰，我们无法很容易的算出 k 次操作内能得到的 c 的个数（其实可以做到，只是比较麻烦）。于是不妨倒过来，考虑二分答案，计算从左边开始出现 n 个不同的 c 所需的次数。

记 f(n) 表示上面的这个问题，不难发现

f(n)=\begin{cases}1&n=1\\2n+2\left\lfloor\dfrac{b(n-1)}a\right\rfloor&n>1\end{cases}

于是我们就可以求出我们从左边出发能够到达的个数和从右边出发能够到达的个数，加起来就是答案。

于是就做完了。

code-festival-2014-relay

A - haruki、気になります！

众所周知偶素数只有 2！

B - もう1年遊べるドン？

直接判断。。。

C - amylasemania IIDX

玩 maimai 玩的

直接除。

D - FU

直接统计双方所有棋子的移动步数，如果出现 Y 在 X 正上方、两个人步数和之差超过 2 或者相同则无解，否则移动步数多的一定是先手。

E - 変な足し算

把所有数加起来。

F - ループを探せ

直接 dfs 一遍。

G - haruki の覚醒め

我会背包！

H - アクセス頻度

单调队列扫一遍做完了。

I - 信号待ち

你发现到某个点更早的话答案不会变劣，于是魔改一下最短路即可。

J - Color Game

容易发现只要第一步无法击败对方就只能等到所有石子都涂成黑色，直接判断。

code-festival-2014-china-open

A - Lock

注意到密码锁 0 和 9 是相邻的，所以直接随便转，低位都转完之后高位再转一下，无论怎么转一定能经过所有数字。

B - n-th Points

首先发现 |x|+|y|=k 的 (x,y) 组数在 k=0 时为 1，否则为 4k。于是可以快速算出第 n 个点的 |x|+|y|。

所有 |x|+|y|=k 的点构成一个菱形，简单分讨即可得出具体位置。

C - Regular Polygon

由于题目中保证了输入的点都是整点，所以我们不妨来考虑整点正多边形的性质。

定理 1. 不存在一个正三角形 ABC 满足 A,B,C 都是整点。

证明：假设存在，那么考虑包含 \triangle ABC 的与坐标轴平行的最小的长方形，它的面积一定是整数而且恰好是 \triangle ABC 的两倍，这也就是说 \triangle ABC 的面积是有理数。

从另一方面看，众所周知 S_{\triangle ABC}=\dfrac{\sqrt 3}4AB^2，而显然 AB^2 是有理数，所以 S_{\triangle ABC} 是无理数，与上面矛盾。因此不存在满足条件的正三角形。\square

定理 2. \forall n\ge 5 不存在正 n 边形 P_1P_2\dots P_n 满足 P_1,P_2,\dots,P_n 都是整点。

证明：仍然假设存在，那么因为整点是有限小的，所以一定能找到一个最小的正 n 边形 P_1P_2\dots P_n。

考虑构造 A_1A_2\dots A_n，其中 A_i 为 P_i 关于 P_{i-1}P_{i+1} 的对称点（P_0=P_n,P_{n+1}=P_1）。那么：

那么对于 n\ge 5 的情况，我们就得到了一个比原来严格更小的正 n 边形，与前面的假设矛盾。因此不存在最小的正 n 边形，即不存在格点正 n 边形。\square

这个东西在 n=4 的时候不受影响是因为此时 A_1A_2A_3A_4 只是 P_1P_2P_3P_4 换了下顺序。

于是我们发现如果存在格点正多边形就只能是正方形，于是直接暴力枚举两个点检查是否存在以它们之间的边为边的正方形即可。

D - Maze

保留所有可能在 S 到 A 和 B 最短路上的点跑最大流。

E - Game

直接三维 dp 表示三种关卡的剩余数量，硬转移有 3^4\times 5 种，实际能过。

F - Yakiniku

实际上只需要考虑 i 在 t_i 时刻仍然存活的概率就可以计算答案，而这等价于 i 在 [s_i,t_i) 时刻一直没被拿走。

计算 $n_x$ 是容易的。为了避免除法可以使用线段树计算区间积。 ### G - Ammunition Dumps 容易发现问题等价于一个图的生成树计数，直接矩阵树定理即可。 ### [★]H - Dungeon 注意到你其实可以来回走，所以你可以等到需要开宝箱的时候再回去拿钥匙开宝箱。 对于钥匙 $i$ 和宝箱 $j$，用 $i$ 开 $j$ 的收益为 $i$ 的代价加上 $\max(i,j)$ 后面的怪物个数乘上 $j$ 产生的增量。 于是直接进行二分图最大权匹配。 ### I - Obstruction 考虑维护集合 $S$ 表示一定能够到达终点的网格，那么： - 终点在 $S$ 中； - 如果一个格子相邻的黑格在 $S$ 中则它也在 $S$ 中； - 如果一个格子相邻的至少两个白格在 $S$ 中则它也在 $S$ 中； $S$ 中的所有元素容易通过 bfs 得到。可以证明能够到达终点当且仅当起点在 $S$ 中。 ### [★]J - XORAND 众所周知以 $L$ 为左端点的区间中至多有 $\log V$ 种不同的按位与结果，每一个结果对应一个右端点的连续段 $l\sim r$。记 $B_i$ 为后缀异或和数组，问题可以转化成求 $\min\limits_{l\le i\le r}(B_i\oplus x)$，其中 $x=B_{r+1}$。这个问题可以直接上可持久化 Trie，总时间复杂度 $O(n\log^2 V)$。 # 2015 ## code-festival-2015-okinawa-open ### A - Automatic Map Generator 在所有行列都为奇数的地方放上一个岛屿，如果最后还不够就倒闭了。 ### B - Beware of the Sogginess! 发现 a 的限制可以直接改为 $a+b$ 的限制，而 $a+b$ 是定值，这样相当于去掉了变换造成的影响。 于是直接 dp，$f_{i,j}$ 表示前 $i$ 个数的 $b$ 之和为 $j$ 时，最大的 $\sum(a+b)$。 但是 $j$ 可能会达到 $10^6$ 量级，所以把 $\ge B$ 的部分都转移到 $B$ 处即可解决问题。 ### C - Cat versus Wolf 每一层的状态是独立的，所以求出每层的 SG 函数后异或起来即可。每层的 SG 函数可以手算。 ### D - Dictionary for Shiritori Game 根据“只要能到达必败态就是必胜态，只能到达必胜态的就是必败态”，可以进行拓扑排序然后检查 $1$ 处的状况。 ### E - Enormous XOR Rectangle 记 $n$ 为满足 $2^{n-1}\le HW-1<2^n$ 的值，则答案一定小于 $2^n$。 如果 $2^{n-1}$ 与 $2^{n-1}-1$ 在同一行，那么一定是相邻两个，则答案为 $2^n-1$。 否则说明 $W$ 一定是形如 $2^m$ 的形式，显然答案至少为 $(2^{n-1}-1)\oplus(2^{n-1}-1+2^m)=2^n-2^m$。能够证明此时不存在更优的答案。 ### F - Falconry 考虑 $f_{t,i,j}$ 表示第 $t$ 只鸟经过点集 $i$ 最后停到 $j$ 的最小距离和。直接转移即可。统计答案的时候先枚举前两只鸟经过的集合的并再枚举其子集作为第一只鸟经过的集合，总复杂度 $O(3n^22^n+3^n)$。 ### G - Gorgeous Vases 问题可以转化为从 $(0,0)$ 走到 $(A,B)$ 且不穿过直线 $x=y$ 以及 $A-x=B-y$ 且不经过若干给定点的方案数。 直接考虑 $f_i$ 表示到达第 $i$ 个给定点的满足其他限制的方案数。则 $f_i=calc(0,i)-\sum\limits_j(f_j+calc(j,i))$，其中 $calc(i,j)$ 表示第 $i$ 个点走到第 $j$ 个点不穿过那两条直线的方案数，第 $0$ 个点为 $(0,0)$。 $calc(i,j)$ 可以用反射容斥计算。 ### H - Happy 2015 将 $l,r$ 离散化。记 $f_{i,0/1}$ 表示覆盖到 $i$，$i$ 是否进行覆盖时的方案数。 那么 $f_{i,0}=f_{i-1,0}+f_{i-1,1}$，$f_{i,1}=\sum\limits_{cov(k,i)=1}f_{k-1,0}$，其中 $cov(i,j)$ 表示是否存在方案使得只有 $[i,j]$ 被覆盖。 $cov(i,j)$ 可以通过枚举 $i$ 然后从左往右推 $j$ 算出所有 $cov$。 总复杂度 $O(n^2)$。 ### I - Implementation Addict 钦定一些时间必须休息相当于把问题分成若干个子问题，所以只需要考虑 $n$ 天没有钦定的情况。 假设分 $x$ 段，那么肯定是分的尽量平均的，即若干段为 $t$ 天工作，剩下的段为 $t+1$ 天工作。而每一段内部的答案可以用等差数列求和。 发现答案关于 $x$ 是单峰的，所以可以三分求出 $x$。 ### J - Jungle 记 $sum_i$ 为以 $i$ 结尾的长为 $k$ 的段的和，$mx_i$ 为最大的包含 $i$ 的长为 $k$ 的段的和减去 $a_i$。 二分答案 $x$ 之后，问题变为是否存在一种砍树的方法使得所有长度为 $k$ 的连续段的和都不超过 $x$。 用 $f_i$ 表示前 $i$ 棵树中符合这个条件且必须砍第 $i-k$ 棵树时最少需要砍多少棵树。 转移可以枚举下一棵砍的树 $i+j$。发现 $j\ge k$ 时可以先转移到 $i+k$ 的位置再转过去，于是这个的总复杂度 $O(nk\log V)$。 考虑另外一个 dp：$g_{i,j}$ 表示前 $j$ 棵里砍了 $i$ 棵的最小答案，枚举 $i$ 后记 $Mx_j$ 表示前 $j-1$ 棵中砍了 $i-1$ 棵且最后一棵 $\le j-k$ 时的最小答案。$Mx$ 的转移和 $g$ 的计算都是简单的，总复杂度 $O(nm)$。 发现 $m\ge\left\lfloor\dfrac nk\right\rfloor$ 时答案和 $m=\left\lfloor\dfrac nk\right\rfloor$ 的答案相同，所以直接根号分治，把两种做法结合起来即可通过。 ## code-festival-2015-morning-hard ### A - 一次元オセロ 问题等价于在序列一边最靠边的两个数合并再 +1，而白方的操作永远是唯一的，所以每次黑方贪心从两边选两次操作后造成贡献更小的那个进行翻转。 ### B - 立方体とペンキ 直接贪心好像是对的，即每次选择最高的一个方块取走。直接模拟这个贪心过程，优化一下即可。注意最后如果一层只取了一部分，就需要优先取短的连续段。 ### C - 数列の組み替え 直接去贪心尝试以当前状态为前缀时是否存在一个合法的答案，注意一些细节即可。 ### D - ありんこ 二分答案，容易发现不存在相撞等价于最初时刻和最终时刻的蚂蚁相对前后位置都不变，把序列按照处是位置排序后等价于一个最长上升子序列问题，直接树状数组或者二分解决。 ## code-festival-2015-final-open zzp 可爱 ### A - コード川柳 直接做 ### B - ダイスゲーム 直接做 ### C - 寿司タワー 直接做 ### D - 足ゲームII 最小链覆盖等于最长反链，所以达到 $n$ 分的话需要的人数为最多的覆盖次数。但是可以去掉一个，所以如果最多的那个覆盖次数在多个位置都取到了答案就不变，否则 -1。 ### E - ショートコーディング 首先两个 - 可以消掉。另外 ! 后面的所有 - 都可以消掉，然后三个 ! 可以变成一个 !。 ### F - 歩くピアニスト 发现一个点的被经过次数的两倍等于它附近的两条边的经过次数之和。于是假设 $1$ 和 $2$ 之间的边经过了 $x$ 次，那么可以用这个性质算出其他所有边的经过次数，而根据 $7$ 和 $1$ 之间的经过次数和 $x$ 又可以解出 $x$ 的具体数值。 于是把每条边复制那么多次然后计算出每个点的度数，检查这张图是否存在欧拉回路即可。 ### G - スタンプラリー 发现一个子树在 dfn 中是连续的，而且子树之间按照根的大小排序，所以直接区间 dp 即可。 ### [★]H - 焼肉の達人 首先发现一个点不会被覆盖 $3$ 次及以上，因为此时把靠中间的区间删掉答案不会变小。 所以一个点最多被覆盖 $2$ 次。我们希望 $1$ 产生 $1$ 的贡献，$2$ 产生 $2$ 的贡献，所以我们令 $0$ 也产生 $2$ 的贡献，这样答案就是 $2m$ 减去贡献和。 将贡献转化为图论模型，每个区间都从起点向终点连边，距离为区间长度，$i$ 向 $i+1$ 连距离为 $2$ 的边代表跳过，$i$ 向 $i-1$ 连距离为 $0$ 的边代表相交部分，这样每一条 $0\to m$ 的路径就代表一种覆盖方案，最短路径就是最终答案。 ### [★]I - 風船ツリー zzp 秒了这题，好牛 qwq 从上往下考虑每个点 $i$。如果最终保留 $i$ 到根的路径作为答案，那么所有 $i$ 的祖先的其他 maxdep 超过 $i$ 的深度的子树都需要砍掉。把这个东西改成从那些子树贡献到 $i$，于是可以树状数组维护。 ### [★]J - N個のバケツ 首先可以把 2 的常数拖到另一边变成每个点相邻的两条边权之和不能超过 $2p_i$。 发现 $n$ 是偶数，也就是说环是二分图。把环黑白染色之后一边连源点一边连汇点，容量为 $2p_i$，原有的边容量为 $\infty$，最大流就是答案。 又发现最大流等于最小割，而回到环上，每一条 S 到 T 的路径代表相邻两个节点中间的边。所以说我们需要选择若干个点使得剩下的点两两没有边，而且最小化我们选择的点权和。那么考虑剩下的点，其实就是最大独立集。而环上的最大独立集可以 dp 解决，于是用数据结构优化这个 dp。 ## code-festival-2015-relay ### A - チーム分け ？ ### B - 全完 全都完辣！ ### C - 円周率 $\pi=3.14159265358979323846264338327950\dots$，这就够了。 ### D - ピザ ？？ ### E - 反転時計 去尼玛的钟表题 ### F - グラフの個数 去尼玛的打表题 ### G - 主菜と副菜 真不是奶龙题？ ### H - 塗りつぶし 问题等价于 $(1,1)\to (n,m)$ 路径上的最小连续段数，直接 dfs 即可，复杂度 $O(9nm)

I - Platoon Match

来点二维背包

J - 石山ゲーム

如果两个数都 >1 或者都 =1 就是 snuke 获胜。

2016

code-festival-2016-quala

A - CODEFESTIVAL 2016

这么签到哦

B - Friendly Rabbits

这么若之哦

C - Next Letter

如果只剩下一位那就全操作到上面，否则如果能操作到 a 就操作到 a，否则就不操作了 qwq

D - Grid and Integers

条件可以转化成 a_{i,j}-a{i,j+1}=a_{i+1,j}-a_{i+1,j+1}，所以 a_{i,j}=x_i+y_j。于是有一些 x_i+y_j=v 的限制，直接乱构造一下就行。

[★]E - LRU Puzzle

无敌题！

设 f(a) 表示对一个长度为 M 的序列按照 a 中的元素依次操作得到的结果。容易得到一个求 f 的方法：从后往前找到一个数，如果是第一次出现就加到答案的末尾，否则忽略。最后把没出现的数从小到大接在后面。

于是我们需要让所有子序列的 f 相等，另外能够注意到如果需要都相等那么一定都等于 f(a)。于是现在问题是怎么让它们都等于 f(a)。

设 b_1\sim b_N 为 f(a_1)\sim f(a_N)，考虑倒过来遍历 a，每次找到一个不含 a_i 且加入 a_i 后仍然是前缀的序列 b_j 然后加入，最后把所有 b 都扩展到 M 的长度并检查是否相等。

直接实现太慢了。因为我们一直让 b 是前缀，所以其实不需要记录 b 的具体东西，只需要记录长度即可。记 freq_k 表示当前 b 中有多少个长度为 k 的前缀。对于每个 a_i 枚举所有出现位置 k，如果 freq_{k-1}\ge 1 就令 freq_{k-1} 减一，freq_k 加一。之后对于最后的比较部分，实际上只需要比较大小最小的那个即可，因为如果它合法了其他的也合法。

总复杂度 O(M+Q)。

code-festival-2016-qualb

A - Signboard

谁家奶龙

B - Qualification simulator

直接做

C - Gr-idian MST

对所有行和列的权值排序，之后每次选择最小的那个看它最多能放多少个。

D - Greedy customers

直接贪心从前往后考虑当前这个位置能被操作的最多的次数，加起来即可。

[★]E - Lexicographical disorder

简单题，把所有串全扔到 Trie 上，记录 f_{i,j,k} 表示节点 i 处如果 j 的字典序在 k 前面会造成的贡献。

预处理时直接在每个节点处把所有子树两两贡献一遍然后把当前节点已有的答案“下传”下去，查询的时候对于对应串的终止位置把任意两个之间的贡献求和。

code-festival-2016-qualc

A - CF

666

B - K Cakes

只考虑众数比别的所有数的出现次数之和多了多少即可。

C - Two Alpinists

显然所有前缀最大值以及后缀最大值发生变化的位置的值是确定的，剩下位置只要不超过它位置的两个最大值的 min 即可。

D - Friction

可以想办法使得贡献之间互不影响，所以只需要分开考虑任意两列之间产生的贡献即可。考虑目前相邻的两列，记 f_{x,y} 表示左边一列推了 x 个，右边推了 y 个，产生的最小代价，直接 dp 即可。

E - Encyclopedia of Permutations

考虑排列的排名如何计算。i 的贡献是 i 后面比它大的数的个数乘上 (n-i)!，最终 +1。分四种情况计算贡献即可。

cf16-final

A - Where's Snuke?

Here

B - Exactly N points

直接找到 1+2+\dots+x\ge n 的最小的 x 然后用 x+1 到 1 逐个减即可。

C - Interpretation

把所有能说同一种语言的全都连在一块，最后如果所有点都在一个连通块就可以。并查集实现。

D - Pair Cards

优先将已经成对的拿走，剩下的按照 \bmod m 分类后贪心匹配。

E - Cookies

考虑生产、消耗、生产、消耗的过程，假设总共进行了 k 次的生产，第 i 次花了 t_i 秒，那么相当于花费 \sum t_i+(k-1)a 的时间生产出 \prod t_i 块饼干。

考虑枚举 k，这样 (k-1)a 就是固定的，于是问题变为 \prod t_i\ge n，最小化 \sum t_i。容易解得 \sum t_i\ge k\sqrt[k]n，取等时 t_1=t_2=\dots=t_k=\sqrt[k]n。不过因为 t 需要是整数，所以需要其中一些 t 向下取整，另一些向上取整，直接枚举个数即可。

F - Road of the King

设 f_{i,j,k} 表示走了 i 步，经过了 j 个点，其中与 1 强连通的点有 k 个的方案数。

直接转移即可。

[★]G - Zigzag MST

欸咋是这个题

对于一次操作 (A,B,C)，考虑一个很牛逼的操作：

这样的话这些边会形成一个环，环上每条边其实都是无限条边，不过显然只需要保留边权最小的那条。

发现这种边都是从 S 出发，以 x 为初始权值，S+i 和 S+i+1 之间边权为 x+2i。考虑把这种边先放在 S 和 S+1 中间，所有边加完之后尝试用 S\leftrightarrow S+1 的边更新 S+1\leftrightarrow S+2 的边，容易发现只需要更新两圈即可。

于是我们只需要带着这一个环的边和 q 次操作里 A\leftrightarrow B 的边跑 Kruskal 即可。

[★]H - Tokaido

记先手为 A，后手为 B，因为所有 a_i 都非负，所以容易发现最终的状态一定是由若干个 A 段和 B 段构成，每段的开头由自己决定，结尾由对手决定。

考虑暴力 dp。因为结尾由对手决定，所以倒过来 dp。

记 f_{i,0/1} 表示 [i,n] 被取完，最靠前的一段是 A 还是 B 取的，此时的得分差。

容易得到 f_{i,0}=\min f_{j,1}+s_{i,j-1}，f_{i,1}=\max f_{j,0}-s_{i,j-1}，前缀和优化可以做到单次 O(n^2)。

不难发现 f_{i,0} 和 f_{i,1} 互为相反数，所以可以省去第二维。

然后把前缀和拆开之后发现其实可以直接记录 s_{i-1}-f_i 的最小值直接转移，然后这样连 f 都不需要了，只需要最小值和前缀和。

现在的式子是 mn\gets\min(mn,2s_{i-1}-mn)，初值为 s_{n-1}-f_n。注意到 \sum a_i\le 10^6，所以说 mn 如果是正的就只有 10^6 种值，如果是负的就不会在后面发生变化，因此不考虑。

考虑预处理一遍 mn 的所有取值会变成什么。枚举到一个 s_i 时会产生变化当且仅当 2s_i-mn<mn，即 mn>s_i。所以把每个值看作一个点，从前往后枚举每一个 s_i 并把当前值到上一个值之间的所有点都连向其变化后的点，最终会形成一个森林。在森林上 dfs 就可以知道每个位置的最终取值了。

[★]I - Reverse Grid

注意到一个格子 (i,j) 只能够到达 (i,j),(i,w-j+1),(h-i+1,j),(h-i+1,w-j+1) 四个位置。

考虑这四个位置之间的关系。假设记这四个位置的值为 a,b,c,d，注意到可以对 (i,j) 依次进行行、列、行、列操作，使得 a,b,c 轮换。因此应该有 12 种不同的结果，这同时也说明如果翻转了这其中的某行或某列就会导致结果变为另外 12 种。但是如果出现了相同元素，那么一定存在方法使得两个相同元素在同一行或同一列，此时就不需要 \div 2。

之后考虑能否翻转的问题。给每行和每列建一个点，对于一个互不相同的四元组 (i,j),(i,w-j+1),(h-i+1,j),(h-i+1,w-j+1)，连接 i 行和 j 列。之后对于一个连通块 S 容易发现它的合法翻转方案有 2^{|S|-1} 种，于是并查集维护再全乘起来即可。

[!]J - Neue Spiel

事实上可以把推动之前的格子改成直接放到目前第一个空位上，反正是一样的。

容易想到一种简单的方法判断有解：给 4n 个方向和 n^2 个点建点，每个点从四个对应的方向连容量为 1 的边，源点给每个方向连容量为对应限制的边，每个点到汇点也连容量为 1 的边，这样流满等价于有解。而且能知道每个位置是从哪个方向塞进来的。

之后考虑钦定顺序问题。直接进行 dfs。搜索到某个格子的时候强制钦定它前面的点都需要被选，直接递归下去搜索。但是其实这样会出现环，例如下面的情况：

DL
RU

这个时候只需要稍微交换一下顺序，变成

LU
DR

容易发现每个点还在原来的方向限制上，于是这么改不会出问题。

能够证明复杂度是对的。

cf16-exhibition-final

A - 1D Matching

观察样例，其实每个电脑都可以和前面未匹配的电源匹配，因此答案就是每一个能匹配的时候的方案数全乘起来。

B - Inscribed Bicycle

容易发现两个圆在离的尽量远的情况下应当是各与两条边相切的，也就是说一定在某一条角平分线上。然后看起来就没什么思路了，因为不好描述距离关系。

但是这是个 oi 题啊！仔细想一下，r 显然是具有单调性的，于是我们直接二分不就做完了！！！

C - Cheating Nim

后手必胜的条件是异或和为 0，所以我们从高到低考虑每一位，如果存在一个数该位为 1 且低位为 0，那么就让它 -1，如果不存在就无解。

D - Dice Game

从 Petr 的角度考虑。如果它选择第一个骰子的概率为 x，那么 tourist 猜对的概率为 \sum\max(p_ix,q_i(1-x))。显然这是一个单谷函数，三分即可找到最终答案。

[★]E - Water Distribution

首先显然跟 0 取 \max 可以直接扔掉，不影响答案。于是把传递水的两个城市 x,y 连无向边，边权为负代表反向传水。

容易发现此时出现环一定不优，因为去掉其中最大边即可。所以最终形态一定是一个森林。对于每棵树 T，它的答案上界是 \dfrac{\sum a-\sum e}{T}，而且可以卡到这个上界。先随便让所有点都达到平均值，然后对进行多次的路径进行合并。

因为 n\le 16，直接状压。先枚举出所有连通块的答案，这时 \min(\sum e) 就是最小生成树，最后再枚举子集把连通块的答案合并起来。

F - Intervals

因为所有区间都相交，所以不难注意到最终状态一定是所有区间互相挨着。证明可以考虑中间的区间，如果它移动过就尝试将所有区间平移使中间的区间移回来，这样答案不会变劣。

于是现在有区间固定了，贡献可以分开计算。另外我们发现移动区间的时候优先移动长度小的更优，因为后面的区间都要跨过它。所以按长度排序后设 f_{i,j,0/1} 表示前 i 个区间，有 j 个在左边，是否已经确定固定的区间。

转移直接枚举每一个区间考虑它的状态即可。

G - FESTIVAL

这么喜欢不按难度排序。。。

构造若干个形如 \text{FFF\dots ESTIVAL} 的串拼起来，假设第 i 部分有 x_i 个连续的 \text F，那么方案数为 \sum\limits_{i=1}^n x_i\binom{i+6}7=k。考虑直接从大到小枚举 i，尽量最大化 x_i。n 开到 500 左右即可。

[!]H - AB=C Problem

怎么你们 atcoder code festival 还有线性代数题的。。。。不会做，不想学。

I - 90 and 270

首先考虑是否存在符合条件的多边形。显然如果内角和不等于 (n-2)\times 180\degree 就无解了，而且还能发现 90\degree 应当比 270\degree 多四个。

之后考虑如何构造。首先如果遇到相邻的 90\degree 和 270\degree，因为经过这两个角之后方向不变，所以可以考虑去掉这两个角之后递归下去处理，直到只剩四个 90\degree，直接返回一个矩形即可。

还原回来构造的时候可以先把坐标全都扩倍，然后处理完拐角问题之后再离散化回去即可。

[★]J - 123 Pairs

对于一个合法的答案，可以将 1\sim 2n 分为若干个段使得不存在任何一个数对的两个数在两个段内且各个段都无法再分。例如 (1,3),(2,4),(5,6),(7,10),(8,9) 就会划分为 \{(1,3),(2,4)\},\{(5,6)\},\{(7,10),(8,9)\}。于是我们对每个段进行考虑。

每个段内的所有数对差仍然不能超过 3。经过手玩其实能够发现构成一个段的数对划分方式并不多，实际上一共只有以下几种：

  1. 类别 1：(1,2)；
  2. 类别 22：(1,3),(2,4)；
  3. 类别 232：(1,3),(2,5),(4,6)；
  4. 类别 2332：(1,3),(2,5),(4,7),(6,8)；
  5. ……
  6. 类别 31：(1,4),(2,3)；
  7. 类别 333：(1,4),(2,5),(3,6)；

容易发现只有 1、31、333 这三种类别以及所有 2333...32 的类别。

当给定差为 1,2,3 的组数时，考虑枚举 333 和 31 的个数，这样就能 O(1) 算出剩下的总方案数，总复杂度 O(n^2)。

cf16-relay-open

又是最喜欢的摆烂时间

A - Equivalent Resistance

直接做

B - Mirror String

直接做

C - Kode Festival

Kobe（雾

直接做

D - Magic Square 2

直接解出每个位置的值即可。

E - Segment on Grid Paper

考虑线段穿过横竖线的次数，每次穿过一条线对应经过一个网格，注意有 \gcd(d-b,c-a) 个位置的网格会穿过一个角从而被算两次，直接减去。

F - Trichotomy

直接做。

G - Magician

直接模拟记录每个位置是可能被到达还是一定能到达。

H - Early Bird

记录所有醒着的时间，直接找出一个长为 10800 的区间最多能包含多少醒着的时间。

I - 3y3s Challenge

直接令每个人从自己下一个开始轮流看向所有人，但是偶数的时候后面会爆炸。所以在 2\mid n 的时候交换一下后面一半的人的中间两轮看向的人即可。

J - Connected Checkerboard

三排一组，随便构造一下即可。

K - Problem on Tree

考虑树形 dp。显然所有叶子都是可以同时选择的，先假设根为 1。那么一棵子树中，如果要选择一些不在开头或结尾的点，那么选叶子一定最优。于是记 f_i 表示 i 子树内进入之后不再回来的最多可选点数，g_i 为叶子数量，将所有路径放在起点和终点的 LCA 处统计答案即可。

2017

code-festival-2017-quala

A - Snuke's favorite YAKINIKU

直接做。

B - fLIP

选 x 行和 y 列时答案为 xn+ym-2xy，直接枚举即可。

C - Palindromic Matrix

发现如果 H 和 W 都是奇数，那么正中间的位置的出现次数可以是奇数；

如果 H 是奇数，那么中间一行的出现次数只需要是偶数即可；

如果 W 是奇数，那么中间一列的出现次数只需要是偶数即可；

对于其他的网格，就是四个四个出现的。

判这些即可。

D - Four Coloring

哇这个好可爱鸭

首先将曼哈顿距离转化成切比雪夫距离，这样整个坐标系都是斜过来的了。

然后考虑将其分成若干个 d\times d 的块，同一块中的点染同种颜色，然后对块进行整体染色。块的染色可以考虑按照行和列的奇偶性分成四种，直接同种染同色。

[★]E - Modern Painting

首先把没有机器人的行和列都删除，因为它们不会造成任何影响。如果没有机器人则答案显然为 1。否则一定会有一个人第一个行动。不妨假设它是上下移动的。

那么它就会将网格划分为左右两部分，而中间这一整列都被它涂上了颜色。实际上，中间整列被竖着涂上颜色的可能不止一列，而是一个包含当前这一列的区间 [L,R]。枚举 L,R，那么当前的方案数分为三部分：

  1. 左边 L-1 列以及最左侧的机器人能够产生的不同方案数，注意此时第一个行动的机器人必须是左侧的。
  2. 右边 M-R 列以及最右侧的机器人能够产生的不同方案数，注意此时第一个行动的机器人必须是右侧的。

那么，只要我们对于每个 L 和 R 都分别求出对应部分的答案，我们就可以最终在 O(M) 的时间内求出答案。

左右是对称的，我们就只看左边如何计算。对于一个 L，假设 X 为左侧的机器人个数，Y 为左边 L-1 列中上面的机器人个数，Z 为左边 L-1 列中下面的机器人个数。

如果 X=0，那答案在 Y=Z=0 时为 1，否则为 0。如果 X>0，那么至少要有一个人占领一整行。考虑继续对左侧的这个子网格进行压缩：总共有 X 行，其中上半部分有 Y 列，下半部分有 Z 列，中间部分只有一列。

把这个图形的最终形态画出来，并将下半部分沿着当前子网格的最右边翻转到最右侧，我们会发现一个惊人的事实：每一个符合条件的最终形态与唯一的一条从左上角 (0,0) 到右下角 (X,Y+Z) 的路径对应！

容易计算出路径共有 \binom{X+Y+Z-1}{X-1} 条，结合上面的一点点分讨，我们就解决了如何对于所有 L 和 R 计算对应答案。

于是这道题就被我们在 O(N+M) 的时间复杂度内解决。

[★]F - Squeezing Slimes

来点经典套路。注意到对于两个相邻的数，如果它们的操作次数为 a 和 b，那么其中其实有 \min(a,b) 次操作都是可以同时进行的，于是问题可以转化为给定一个序列，每次选择一个区间同时 -1，变成全 0 的最小次数，直接求差分数组绝对值之和的一半。

code-festival-2017-qualb

A - XXFESTIVAL

直接做。

B - Problem Set

排个序，然后直接做。

C - 3 Steps

如果一个图是二分图，那么每个点最终连接的边一定都是另外一侧的，原因显然，于是最终答案等于两边点数相乘。

如果图不是二分图，说明存在奇环，容易发现此时最终图是完全图，也容易计算答案。

D - 101 to 010

看到对 01 串相邻位操作考虑对奇数位翻转

设 f_i 表示以 i 为结尾最多能操作多少次。

发现 10111\dots 1 这样的串的贡献为右边 1 的个数，操作后会变为 000\dots 010，左右翻转后同理，记这些串为好串。

找出以 i 为右端点的最长的好串，显然最多有两种。

但是注意可能会有 10111101 这种的情况，最优应当分成 101 和 11101，于是在最靠近的 0 就在左边一位的时候加一个这个特判即可。

E - Popping Balls

从 0 拿球等价于 s,t 向右移动一格，从 s 拿球等价于 t 向右移动一格。

考虑判断一个状态是否合法。拿到第一个蓝球之后，$t$ 选在蓝球的头上一定不劣，之后 $B$ 次每次都有两种选择，直到 $B$ 次之后 $t$ 超出末尾。$s$ 同理。 枚举从 $t$ 拿走了 $i$ 个蓝球，$s$ 拿走了 $j$ 个蓝球，固定第一个拿的蓝球，那么从 $t$ 拿走了 $B-i$ 个红球，$s$ 拿走了 $B-i-j$ 个红球，还有 $A-2B+2i+j$ 个红球要在 $0$ 处拿球的那三段时间内拿走，插板法计算贡献即可。 ### F - Largest Smallest Cyclic Shift 把每个字符都加入字符串集合，每次选出字典序最小的和最大的拼接在一起，直到只剩下一个串就是答案。 正确性可以归纳证明。 ## code-festival-2017-qualc ### A - Can you get AC? Yes ### B - Similar Arrays 不如求积为奇数的情况，因为这时所有数都需要是奇数。那么一个 $a$ 附近要不然就一个要不然就两个，方案数乘起来即可。 ### C - Inserting 'x' 这位更是直接做。 ### D - Yet Another Palindrome Partitioning 对于一个字符串，如果它能重排成回文串则至多有一个字符出现奇数次。 考虑一个朴素 dp：$f_i$ 表示 $1\sim i$ 至少要分多少段，那么 $f_i=\min\limits_{can(j,i)}f_j+1$，其中 $can(l,r)$ 表示 $l\sim r$ 可以重排为回文串。 因为是奇偶性相关问题，所以考虑用一个 int 维护每个前缀里每个字符当前出现次数的奇偶性 $s_i$。这样 $can(l,r)$ 就可以表示为 $(s_r\oplus s_{l-1})\in\{0,1,2,\dots,2^{25}\}$。那么把所有 $f_i$ 都存到 $s_i$ 上，于是就可以 $O(26n)$ 解决了！！！！！！ ### [★]E - Cubes 因为 $a,b,c$ 互质，所以一条线段不会穿过任何一个立方体的棱或角。 所以一条线经过的相邻两个立方体都是共面的，因此可以用一个面对应一个立方体。考虑三种方向的面，总经过立方体数量为 $a+b+c-2$。 如果中间填满了小立方体，相当于要把线经过的点为中心的棱长为 $2d+1$ 的立方体之间的点全都挖出来。 因为是共面的，所以考虑多出来的部分。在无限个小立方体的时候多出来的一小片的大小为 $(2d+1)^2$。 但是实际上我们需要计算一维 $+d$ 大于对应维度大小以及 $-d$ 小于 $0$ 的情况。直接把每一维 $<d$ 的点全都村下来，按照到达这个立方体的顺序排序。 把这个三维的东西分成三部分，于是可以确定每个立方体的位置，然后就可以直接模拟了。 ### F - Three Gluttons 考虑最后一次取数。假设三个人分别取 $x,y,z$。那么在第三个排列中 $x$ 和 $y$ 就应该在 $z$ 后面。再往回退一步也是一样的。 于是我们得到每次 A 和 B 选的值要排在 C 选的值后面。那么 C 的可能序列有 $\prod\limits_{i=1}^n(3i-2)(3i-1)$ 种。现在问题是 C 的操作序列个数。 我们发现要求是： 1. A、B、C 的操作序列不重复。 2. A 的选择不会被 B、C 选择，另外两个同理。 3. 一共要选 $n$ 次。 于是可以考虑 dp：$f_{t,i,j}$ 表示第 $t$ 次，A 选了 $i$，B 选了 $j$，C 的选择数量。 前缀和优化即可。 ## code-thanks-festival-2017 ### A - Time Penalty 直接做。 ### B - Concatenated Palindrome 随便做都行。 ### C - Factory 用优先队列维护，每次取出队头然后加入下一项。 ### D - Bus Tour 容易发现答案为 $m-\gcd(n,m)$。 ### E - Coin Authentication 可以把 $8\sim 12$ 等价转化为 $0\sim 4$。这样问题变成五进制。 一次查询 $625a+125b+25c+5d+e$ 可以用五进制确定五个袋子里的情况，所以只需要 $10$ 次。 ### F - Limited Xor Subset 注意到和不超过 $10^5$，也就是说本质不同的数值只有 $\sqrt n$ 种。 于是考虑 $f_{i,j}$ 表示不超过 $i$ 的数凑出 $j$ 的方案数，直接跳过无用状态暴力转移即可。 ### G - Mixture Drug 一般图最大独立集是 NPC，但是 $40$ 的数据范围让我们联想到了 meet in the middle。搜出前后两部分的答案之后，枚举前面的答案，算出后面能选的集合，取其子集 max 即可。而取子集 max 可以预处理做到 $O(n2^{\frac n2})$，总复杂度同样为 $O(n2^{\frac n2})$。 ### H - Union Sets 第 $i$ 次合并 $a_i$ 和 $b_i$ 的时候在 $a_i$ 和 $b_i$ 之间加一条边权为 $i$ 的边（如果已经连通则不加），那么容易发现此时两个点的路径 max 就是答案，直接树上倍增即可。 ## cf17-final ### A - AKIBA 还是直接做。 ### B - Palindrome-phobia 原来字符集只有三。。。那么直接排成若干个 `abcabcabcabc` 的形式，这个时候最后剩下的无论是 `aba` 的形式还是 `aa` 的形式都会寄，因此只要出现次数的 $\max-\min\ge 2$ 就倒闭了。 ### C - Time Gap 注意到一种数如果出现三次及以上就必定寄了，如果出现两次那么一定是一次 $x$ 一次 $24-x$，这个时候只出现一次的数只有至多 $13$ 个，直接暴力枚举是否翻转即可。 ### D - Zabuton 假设当前有 $W$ 块砖，两个人是 $(H_1,P_1)$ 和 $(H_2,P_2)$。 如果 $H_1$ 在前，就需要有 $W\le H_2-P-1$ 才会使另一个人加砖。 如果 $H_2$ 在前，就需要有 $W\le H_1-P_2$ 才会使另一个人加砖。 那么显然 $H+P$ 更小的那个会给后面的人留更多机会。因此按照 $H+P$ 从大到小排序，之后每次尝试选 $i$，如果爆了就把原来加的最多的踢掉。 ### [★]E - Combination Lock 第一步差分，这样修改就变成两个单点，要求变为对于任意两个在 $1\sim n$ 中对称的元素的和为 $0$。 容易发现对于一次这样的操作，并不会改变这两个变化的位置的和。所以把所有能操作的 $l$ 和 $r+1$ 都连边，这样每一个连通块的点只要和为 $0$ 就一定合法。并查集或者 dfs 均可。 ### F - Distribute Numbers 因为每个数都出现 $k$ 次，而每个数都会产生 $\dfrac{k(k-1)}2$ 个相交，所以有 $\dfrac{n(n-1)}2=n\dfrac{k(k-1)}2$，也就是说 $n=k(k-1)+1$。 那么考虑先钦定一个数在前 $k$ 个集合里出现过，然后让它们和剩下的 $(k-1)^2$ 个集合配对，最后再把其他数补上。 于是问题可以转化为有 $x^2$ 个数，用 $x$ 种方法把它们分成 $x$ 组，每组 $x$ 个数，且不能有两个数在两种分法中都在同一组。 可以考虑将这些数列成一个 $x\times x$ 的表。第一种分法为每行一组，另外 $x-1$ 种分法中第 $i$ 种分法的第 $j$ 行的第 $(ij+t)\bmod n$ 属于第 $t$ 组。容易发现这个对于所有素数都是正确的。 那么 $k-1$ 就需要是素数，所以 $k(k-1)+1$ 要在 $1000$ 到 $2000$ 之间，枚举后发现 $k=38$ 或 $k=42$ 都合法。 ### G - Mancala 注意到如果 $i$ 位置堆了 $i+1$ 颗或者更多石子之后，就再也无法对其操作了，我们称这种情况为“溢出”。 为了避免“溢出”，在我们可以操作多个位置的时候，应当每次都选择最小的可操作位置，这样就不会产生额外的“溢出”情况。 于是我们发现每个数对答案的贡献只与后面的总操作次数有关。 设 $m_i$ 表示 $i\sim n$ 的总操作次数。那么只要 $a_i\le i$，它就可以产生 $(m_{i+1}+a_i)\bmod i$ 的贡献以及 $\dfrac{m_{i+1}+a_i}i$ 的操作次数，否则只会产生 $m_{i+1}+a_i$ 的贡献。 考虑怎么计数。因为 $n,k\le 100$，所以总的操作次数不会超过 $nk$。 所以设 $f_i$ 表示从后往前考虑到 $i$ 时的最小得分和，$g_{i,j}$ 表示从后往前考虑到 $i$ 且操作次数为 $j$ 的方案数。 转移直接按照上面的结论暴力转移，复杂度 $O(n^2k^2)$。 官方题解里有一个神秘数字 3281，疑似是操作次数的上界。 ### H - Poor Penguin 有一个看上去就很笨的做法就是从角上开始把到 P 之间所有厚冰都破坏，取最小的作为答案。但是这个显然是错的。 因为我们有可能从两个角出发把这个矩形分开成为四个小的矩形，而它们分别可以像原来的大矩形一样从角上出发。 所以直接进行一个 dp，表示一块矩形区域外消下去所需的最小代价。直接每次枚举一个分界点，将不含 P 的两个对角矩形全都完全消除，这样对于每一块矩形都算一次从角上过来的答案取最小值即可。 ### I - Full Tournament ？ 记 $a_i$ 为第 $i$ 名的下标，所有排名和下标从 $0$ 开始。那么 $a$ 合法当且仅当 $\forall i,j,a_i<a_{i\text{ or }2^j}$。必要性可以归纳证明。 对于充分性，可以直接构造证明。对于一个已知的 $a$，将其下标在二进制下翻转（FFT/NTT 中的蝶形变换）即可得到一个合法的初始序列。证明仍然可以归纳。 这样的话问题就是给定一些 $a$ 序列中的初始值，构造一个合法的 $a$。 我们可以根据 $a_i<a_{i\text{ or }2^j}$ 的限制给每个点确定一个取值范围 $[l,r]$，之后从小到大贪心确定取值即可。 ### [★]J - Tree MST 对于一张完全图，将其边集划分为若干部分，每部分求出 MST（不连通也可以）对应边集拉回来最终再求一次 MST 与原图 MST 相同。这个结论容易使用反证法证明。 那么对于这个题，可以直接淀粉质，用板子求出来 $dis$ 之后，$(u,v)=(w_u+dis_u)+(w_v+dis_v)$，所以取出 $(w_u+dis_u)$ 最小的与其他所有点连边，这样把所有剩下的边再跑一次 Kruskal 即可。 # 2018 ## code-festival-2018-quala ### A - 配点 直接判断。 ### B - みかん 所有能不放 A 的地方都放 B。 ### C - 半分 发现 $K$ 那么大其实是假的，因为每个数操作 $64$ 次之后就一定是 $0$ 了，所以直接背包再加一维表示是否有一个数卡到了 $64$ 次就做完了。 ### D - 通勤 记 $f_i$ 表示前 $i$ 个加油站中第 $i$ 个必须保留且油满的方案数，那么有 $f_i=\sum\limits_{F-T\le x_i-x_j\le F}f_j\times 2^{cnt_j}$，其中 $cnt_j$ 为 $j$ 后面有多少个不需要加油的。容易发现满足条件的 $j$ 可以双指针，$cnt$ 可以二分求。再加上前缀和优化即可通过。 ### E - オレンジとみかん 第一步显然是二分答案。假设我们二分当前极差不超过 $d$，那么我们枚举 $l$ 检查是否存在一种方案使得每个人的满意度都在 $l\sim l+d$ 之间。 令 $s=\dfrac{X+Y}N$，那么每个人都会取 $s$ 个水果。可以对每个数都计算出满足 $l\le A_ix+B_i(s-x)\le l+d$ 且 $0\le x\le s$ 的 $x$ 的最小值和最大值 $lb_i$ 和 $rb_i$，如果不存在则 $lb_i=rb_i=-1$。那么一个 $l$ 和 $d$ 合法，当且仅当不存在任何一个 $-1$ 而且满足 $\sum lb_i\le X\le\sum rb_i$。 直接做会超时，考虑如何优化这个。在 $d$ 固定且 $l$ 从小到大移动的时候，每个点的状态只会在以下时刻变化： 1. $l=A_ix+B_i(S-x)$，此时 $lb_i$ 应当增加 $1$。 2. $l+d=A_ix+B_i(S-x)$，此时 $rb_i$ 应当增加 $1$。 容易发现这些变化的总次数是 $O(X+Y)$ 的。于是在二分答案之后扫一遍并在过程中判断合法。 ## code-festival-2018-qualb ### A - Probability of Participation 输出 $n-\left\lfloor\dfrac nx\right\rfloor$ 即可。 ### B - Tensai 让 $b$ 最大的加 $x$ 次。 ### C - Special Cake for CODE FESTIVAL 显然是考虑构造那种类似日字格构成的图形，但是发现最终会有少量位置没被覆盖，再额外补上。 ### D - Sushi Restaurant 下面不合适度表示所有人的不满意度之和。 考虑如果 $a$ 和 $b$ 都已经确定了，此时的最小不合适度。容易发现，将 $a,b$ 从小到大排序之后，$\sum |a_i-b_i|$ 就是答案。可以调整法证明。下面第 $i$ 个人（或盘子）就是指空腹度第 $i$ 小的人。 那么，假设已经知道了第 $i$ 个人的空腹度为 $x_j$ 的概率 $t_{i,j}$，那么第 $i$ 个人的期望不满度为 $\sum\limits_j t_{i,j}|x_j-c|$，其中 $c$ 为第 $i$ 小的盘子，容易在 $O(m)$ 的时间内求出期望不满意度的最小值，这样这部分的总复杂度为 $O(nm)$。 考虑怎么求 $t_{i,j}$。可以考虑记 $t$ 的前缀和 $p_{i,j}$ 表示第 $i$ 个人的空腹度至少为 $x_j$ 的概率，于是可以考虑枚举 $x_j$ 和更小的值的分界线位置然后计算方案数，在枚举的同时直接动态计算阶乘，即可做到 $O(nm)$。 注意这个题要求直接输出小数概率，所以在遇到大量乘除法的时候应当先转 ln 然后直接加起来，最后再 exp 回去。 ### E - Game of +- 这不是我们 ucup E 加弱版吗？？？？怎么在这遇到你了，懒的喷。。。 记 $M=\text{lcm}(1,2,\dots,n)$，显然最终的 $G$ 应当为 $\dfrac 1M$。而所有操作都等于加上一个 $\dfrac xM$。所以不妨让所有数都 $\times M$。 那么我们的问题就是让 $G=1$。 考虑将 $M$ 分解为 $\prod\limits_{i=1}^k p_i^{a_i}$。这样所有 $\bmod p_i^{a_i}$ 的结果就能唯一对应 $\bmod M$ 的结果。而且这样每一个修改只会改变一位。 每一位都应当让它的最终结果为 $1$。考虑直接求出最小的 $a$ 满足 $da\equiv 1(\bmod p_i^{e_i})$，其中 $d$ 表示能够修改 $p_i^{e_i}$ 这一位的数 $x=\dfrac 1{p_i^{e_i}}$ 造成的影响。那么如果 $2a<p_i^{e_i}$ 就直接加 $a$ 次 $x$，否则就减 $p_i^{e_i}$ 次 $x$。 能够发现次数不会超过 320。 ## code-thanks-festival-2018 ### A - Two Problems 小清新签到，直接判断就行 ### B - Colored Balls 解出两种操作的操作次数，判断是否都是非负整数。 ### C - Pair Distance 拆成若干段算贡献。 ### D - Concatenation 容易发现在所有前缀最大值处断开即可。 ### E - Union 考虑判定集合合法的过程一定是从小到大合成。因此记 $f_{i,j}$ 表示当前合成到值 $i$，此时有 $j$ 个 $i$ 的方案数，直接暴力转移。经过分析发现 $j$ 的范围也是 $O(V)$ 的，因此总复杂度 $O(nV)$。 ### F - Coins on the tree 注意到每一个硬币的最终位置都一定不会出现在之前的任何一个硬币的最终位置的子树中。于是考虑从前往后贪心选择，每次尝试选当前位置然后判断是否合法。 合法的要求相当于能在把前面确定的位置的子树都扔掉之后存在一个需要 $k$ 次操作的方案，那么其实只要整棵树中深度最小的 $x$ 个点（$x$ 是剩余点数）的深度和不超过 $k$ 且深度最大的 $x$ 个点深度和至少为 $k$ 即可。 ### [★]G - Sum of Cards 考虑把每张牌正反面的两个数之间连一条边，由在上面的数指向在下面的数。那么问题就变成了给一张无向图定向使得至少有 $k$ 个点的出度 $\ge 1$ 且最大化每个点的下标乘上出度。 因为总共有 $n$ 个点和 $n$ 条边，而且每个点度数恰好为 $2$，所以这个图是由若干个环构成的。那么一个点的出度只能是 0，1，2。那么答案又可以表示为 $\dfrac{n(n+1)}2$ 减去出度为 0 的点的下标和加上出度为 2 的点的下标和。 对于一个定向后的环，如果把所有出度为 $1$ 的点都合并成一条边，那么最终的图形其实会成这个样子： ``` a < .... < b > ... > c < ... < d > ... > a ``` 其中被省略的部分就是被合并的点，容易发现这个东西的最大答案是可以 dp 算的。 具体来说记 $f_{i,j}$ 是表示当前环里第 $i$ 个点，然后当前已经经过了 $j$ 个“阶段”时的最大答案。其中一个“阶段”就是指一个同方向的连续段。这样根据阶段的个数也能知道有多少个出度 $\ge 1$ 的点。 最后用一个背包合并各个环的答案即可。总复杂度 $O(n^2)$。 ### H - Median Game 二分答案 $x$，那么 Alice 的目标就是让和 $\ge x$ 的子段数量大于等于和 $<x$ 的子段数量。那么定义一个序列的划分的价值就是这两者之差。 记 $f_i$ 为 $i$ 后缀中 Alice 先手的最大价值，$g_i$ 为 Bob 先手的最小价值。记 $v(l,r)$ 表示这个区间的贡献（为 $1$ 或 $-1$），那么就有 $$f_i=\max\limits_{j\ge i}(v(i,j)+g_{j+1})\\g_i=\min\limits_{j\ge i}(v(i,j)+f_{j+1})$$ 用线段树优化，总复杂度 $O(n\log^2 V)$。 ## code-festival-2018-final ### A - 2540 原来是直接做！ ### B - Theme Color 显然 $p=\dfrac{n!}{(\prod r_i!)m^n}$。 既然他都让你求 $\log$ 了，那你肯定直接转成 $\log$ 啊！求出所有 $\log n!$，然后把所有乘除都改成加减。 ### C - Telephone Charge aminoac 读错题了。。 把所有的价格图像画出来，应该就是由若干条横线和若干条斜率为 $1$ 的线构成。而所有左边横线右边斜率为 $1$ 的那些交点就是 $A_i$ 处。 显然最终取 $\min$ 之后图像就是一段横一段斜一段横一段斜这种的，而我们又知道所有 $A_i$ 都出现在了最终图像上，那么对于一个时长的最优答案一定是它最近的两个方案之一，取个 min 就行。 ### D - Three Letters 因为三元组的总数不多，所以对于每个串的每个字符求出其两侧都有哪些字符出现过以统计都有哪些出现过的三元组，然后直接取 $\max$。 ### E - Tough Journey 直接从后往前贪心，在后面二分出值比当前位置大的第一个和小的最后一个，直接算出过去至少需要买多少即可。 ### F - Dinner Planning 反悔贪心板子？ 把 +1 和 -1 的分成两部分，每次在这一部分加入一个新的值的时候要把这部分里可删除的部分的最低美食度删掉，用一个 multiset 之类的维护。 ### G - Chicks and Cages 对于两个装了 $x$ 和 $y$ 个只因的笼子，$x<y$，假设存在一个只因大小为 $u$ 在第一个笼子里而且存在一个只因大小为 $v$ 在第二个笼子里且 $u>v$，那么交换这两个只因后，它们产生的贡献从 $ux+vy$ 变为了 $uy+vx$，容易发现此时答案会变小。 因此按照 $a$ 排序之后，最优情况下每一个笼子的答案应该都是一个区间。 直接区间 dp 是 $O(n^3)$ 的，但是再使用上面的结论之后改成记忆化写法的 dp 就可以做到 $O(n^2\log n)$ 了。 ### [★]H - Pothunter 首先有一个很显然的 $O(nm)$ dp：记 $f_{i,j}$ 表示 $i$ 时刻在 $j$ 位置的最大收益，因为时刻只需要考虑结束时间，因此是 $O(nm)$ 的，可能带个 $\log$。 考虑 $i$ 从小到大变化时的所有操作。 如果选定一个根，因为转移的过程要经过 LCA，所以所有比赛都可以贡献到所有它的祖先上，然后查询也只查询祖先。 因为这种情况下不合法的答案（指走一些重复路径）一定不优，所以不影响正确性。 然后直接套一个点分治就做完了。 ### I - Homework 首先考虑二分答案 $x$。问题变为求 $x$ 的时间内能得到的最多分数。 因为低位可以合成出高位，所以考虑从低位往高位贪心。注意到如果选择了多个 $2^m$，那么一定是选择了分数最高的那些，而且顺序无所谓。 如果 $x$ 的当前位是 $1$，就拿走一个当前分数最多的。 之后对于剩下的所有数，从大到小两两合并扔上去。注意如果还有一个落单的也要扔上去。 这样一直做到最后，容易证明其正确性。~~但是这并不影响这不容易想到。~~ ### [!]J - Complicated Operations 官方题解就写一页让我怎么读？？？过的人就没几个还都写特别长让我怎么读？？？看我来把官方题解乱翻译一下。。。。 把序列分成前半部分和后半部分。如果前半部分和后半部分需要的值都不需要从另一侧取那就直接分治下去做。 如果一侧需要另一侧的值，考虑依次使用偏移量为 1，-1，2，-2，4，-4，……的操作把它们逐渐移动过去。 在 1 和 -1 中，考虑分别把奇数位往左移和偶数位往右移，这样就能做到交换奇偶了。 同理，就可以完成任何混乱的交换了。