Skip to main content

__debug's Home Keep it simple, stupid

AtCoder 选做

实际上是乱做…

不过 AtCoder 题目质量都挺高的, 所以也没什么问题.

约定: 未特别说明时, 默认数据范围为 \(10^9\) 以内的整数.


AtCoder Regular Contest 072

E - Alice in linear land

Description

Alice 在一个数轴上旅行, 她打算去一个离自己距离为 \(D\) 的点. 现在有一个操作序列 \(\{x_i\}\), Alice 会按顺序尝试每个 \(x_i\). 对于一个 \(x_i\), 如果她向目的地所在的方向前进 \(x_i\) 的距离 (在这期间 Alice 不会改变方向) 之后与目的地的距离会变短, 她便会应用这个操作.

现在, 有 \(Q\) 个询问, 对于一个询问 \(q_i\), 你需要回答能否仅仅通过改变 \(x_{q_i}\) 这个数, 让 Alice 无法到达终点.

\(N, Q \le 5 \times 10^5\)

Solution

首先显然要预处理出 \(f(i)\) 表示考虑 \([1, i)\) 这段前缀 Alice 可以到哪里. 那么对位置 \(i\) 询问时, 我们能做的就是将当前的距离改为 \([0, f(i)]\) 中的任意一个数.

考虑如果可以将当前距离改为任意一个数, 那么一定可以让 Alice 无法到达终点. 现在有了一个上界限制, 可不可以求出 \(g(i)\) 表示一个最小的初始距离, 使得仅考虑后缀 \((i, N]\) 时 Alice 无法到达终点呢?

这个显然是容易递推的.

这类题的难点在于可以尝试的方法很多, 有时性质更强的东西还会好求一些.

F - Dam

Description

现在你有一个水箱, 容量为 \(L\). 一共有 \(N\) 天需要操作, 一开始水箱是空的, 已知每天早上进入水箱的水量 \(v_i\) 和水温 \(t_i\). 每天晚上, 你可以将一些水倒出水箱, 在任一时刻都必须满足水箱内的水量不大于 \(L\).

由 \((v_1, t_1)\) 和 \((v_2, t_2)\) 合并出来的水的参数为 \((v_1 + v_2, \frac{v_1 t_1 + v_2 t_2}{v_1 + v_2})\).

现在对于每一天 \(i\), 询问在第 \(i\) 天中午的水箱是满的情况下, 此时水的最大温度是多少. 询问之间相互独立.

\(N \le 5 \times 10^5, v_1 = L\)

Solution

首先将水的状态 \((v, t)\) 重新表示为一个向量 \((v, vt)\), 这样合并两个水就是直接向量相加了. 然后每次询问的也就是在所有能凑出的状态 \((i, x)\) 中最大的 \(x\) 是多少.

不如考虑一个看上去更难的问题: 求出能到达的状态集合.

将每个状态看作是一个平面上的点, 手玩一下, 发现这个东西是凸的, 并且上凸壳很好用维护, 用单调队列搞一下就行了. 求出上凸壳之后, 原问题就可以轻松回答了.


AtCoder Grand Contest 013

C - Ants on a Circle

Description

有一个长度为 \(L\) 的圆环, 上面有 \(N\) 个蚂蚁, 位置分别为 \(x_i\), 运动方向为 \(d_i\), \(1\) 表示顺时针, \(2\) 表示逆时针. 每只蚂蚁将会同时开始以单位速度运动, 如果两只蚂蚁相遇, 那么它们会改变自己的方向继续运动. 求 \(T\) 秒之后每只蚂蚁的位置.

\(N \le 10^5, 0 \le x_1 < x_2 < \cdots < x_N < L\)

Solution

看上去是一个十分经典的问题, 实际上做法也非常简洁.

首先注意到每只蚂蚁的相对顺序不会改变, 并且 \(T\) 秒之后哪些位置有蚂蚁可以轻松求出. 那么现在有两种思路:

  1. 求出特定编号的蚂蚁最终在哪个位置
  2. 求出最终特定位置的蚂蚁编号是什么

尝试一下, 发现第二种思路比较可行. 不妨将逆时针移动的蚂蚁当作参照物, 那么顺时针移动的蚂蚁将会以两倍速度移动, 并且每次遇到其他的蚂蚁, 这个蚂蚁的编号会增加 \(1\). (因为输入是排好序的)

然后就可以在 \(O(N)\) 的时间内算出最终某个位置的蚂蚁的编号了, 然后再给每个位置按顺序编号即可. 小心处理两个蚂蚁重叠的情况.

D - Piling Up

Description

Joisino 一开始有一些红球和蓝球放在箱子里, 共 \(N\) 个.

她会重复以下操作 \(M\) 次:

  1. 从箱子里任意拿出一个球
  2. 将一个红球和一个蓝球放入箱子里
  3. 再从箱子里任意拿出一个球

在 \(M\) 次操作之后, Joisino 将会得到一个长度为 \(2M\) 的颜色序列. 你需要回答, 对于任意的初始的红蓝球个数, 一共能凑出多少种不同的颜色序列. 对 \(10^9 + 7\) 取模.

\(N, M \le 3000\)

Solution

容易发现每一轮结束之后球都还是 \(N\) 个. 一个 naive 的想法是设状态为 \(dp(i, j)\) 表示进行了前 \(i\) 轮, 箱子里的红球有 \(j\) 个, 此时的方案数. 4 种转移十分显然.

但是这样做肯定是有问题的, 因为两种不同的初始状态可能会得到一个相同的颜色序列. 利用"唯一表示"的思想, 我们只需在 DP 时多记录一个 \(k\) 表示是否存在某一时刻红球用完了, 最后直接统计就行了.

感觉这题比 C 题要简单一些.

E - Placing Squares

Description

Joisino 有一个长度为 \(N\) 的木条, 上面有 \(M\) 位置有标记.

她会在这个木条上放一些正方形, 满足:

  1. 边长为整数
  2. 木条必须被正方形恰好覆盖
  3. 两个正方形的边界不能在一个标记正上方
  4. 不能斜着放

一个放置方案的美观值定义为每个正方形面积的乘积. Joisino 想知道所有方案的美观值之和. 对 \(10^9 + 7\) 取模.

\(M \le 10^5\)

Solution

首先考虑 \(M = 0\) 时的情况. 其实就是下面这个递推式:

\begin{align*} f(0) &= 1 \\ f(n) &= \sum_{k=1}^{n} f(n - k) k^2 \end{align*}

经验告诉我们这个序列应该可以被表示为一个线性常数阶递推式. Wolfram 一发果然有

\begin{align*} &f(0)=0, f(1)=1, f(2)=5 \\ &f(n) = 4f(n - 1) - 2f(n - 2) + f(n - 3) \end{align*}

(把 \(f(0)\) 改为 \(0\) 是为了方便处理)

然后 \(M = 0\) 的时候我们就可以 \(O(\log N)\) 做了. 现在有了限制, 经典思路是记 \(dp(i)\) 为从起点到 \(x_i\) 且不经过 \(x_1, x_2, ..., x_{i - 1}\) 这些点的方案数, 容易做到 \(O(M^2 + M \log N)\).

但是这道题是非常特殊的, 因为是矩阵乘法, 所以可以用一用分配率, 记录一个\(3 \times 1\) 的列向量的前缀和, 每次加入 \(trans^{x_i - x_{i - 1}}\) 的贡献就行了.

这道题的标算好像是一个比较巧妙的组合构造, 不过殊途同归啦.

F - Two Faced Cards

这题比较繁琐…

AtCoder Grand Contest 014

A - Cookie Exchanges

Description

一个游戏, 初始有三堆石子, 分别有 \(a, b, c\) 个石头. 每轮操作会将 A 堆的 \(a\) 个石头分成两份放分别到 B, C 堆去, \(b, c\) 同理. 也就是说, \((a, b, c)\) 会变为 \((\frac{b + c}{2}, \frac{a + c}{2}, \frac{a + b}{2})\).

当 \(a, b, c\) 中存在至少一个奇数的时候, 游戏结束. 问游戏最多持续多少轮, 注意可能出现无法结束的情况.

\(a, b, c \le 10^9\)

Solution

猜想: 除非 \(a = b = c\) 会出现无法结束的情况, 否则游戏的轮数是 \(O(\log n)\) 级别的.

题解的证明十分巧妙, 考虑最大值和最小值之差, 每次正好会除以 \(2\).

B - Unplanned Queries

Description

下面是一个经典问题:

给你一棵 \(n\) 个点的树, 每条边上初始权值为 \(0\), \(q\) 次操作, 每次操作将 \(u\) 到 \(v\) 路径上的所有边权 \(+1\), 最后输出每条边的权值.

现在告诉你树的点数以及 \(q\) 个操作, 已知最后每条边权均为偶数, 问是否存在这样的一棵树.

\(n, q \le 10^5\)

Solution

考虑如果是一条链, 每个点被覆盖的次数为偶数次就行了, 因为可以将一个区间操作拆成两个前缀操作.

然后发现树上其实也是一样的, 一条 \(u\) 到 \(v\) 的路径操作可以转化为 \(u\) 和 \(v\) 到根的路径的操作.

C - Closed Rooms

Description

给你一个 \(n \times m\) 的四连通网格图, 其中有一些格子是障碍, 其他的格子是空地. 初始你在某个格子上, 每轮你可以:

  1. 首先, 移动至多 \(k\) 步, 不能经过障碍
  2. 然后, 将至多 \(k\) 个障碍格子变为空地

问走到边界最少需要几轮.

\(n, m \le 800, k \le nm\)

Solution

注意到两步的 \(k\) 值是相同的, 所以第一轮的第一步走到某个节点之后, 余下的最优方案一定可以直接向某个边界走去.

于是 BFS 一下就好了.

D - Black and White Tree

Description

有一棵 \(n\) 个点的树, 初始每个结点都没有颜色. 现在 Alice 和 Bob 轮流给每个为染色的节点染色, Alice 用白色, Bob 用黑色.

当所有节点都被染色之后, Bob 会将所有与白色节点直接相邻的白色节点变为黑色. 假设 Alice 和 Bob 都足够聪明, 问哪一方存在必胜策略.

\(n \le 10^5\)

Solution

首先考虑一条链的情况. 经过一些观察之后发现链长为奇数的时候 Alice 必胜, 否则 Bob 必胜.

Alice 的必胜策略为: 每次染左数第二个未被染色的点, 这样 Bob 只能染左数第一个未被染色的点, 最后会生下一个点; Bob 的必胜策略为: 如果 Alice 染的点编号为奇数, 则跟着然后一个点, 否则跟着染前一个点.

如何推广到树上?

考虑 Alice 每次染一个叶子的父亲, 那么 Bob 只能染那个对应的叶子. 如果某个时刻出现了某个点有两个叶子的情况, 或是只剩下一个点, Alice 就赢了. 一棵树是否满足这个条件是很好判断的.

猜想: 所有不满足这一条件的树都是 Bob 必胜.

证明是很巧妙的. 考虑所有不满足上述条件的树, 一定存在完美匹配. 于是 Bob 存在非常显然的必胜策略. (可以发现这个策略和之前提到的 Bob 在偶链上的必胜策略是等价的)

E - Blue and Red Tree

Description

给你一棵 \(n\) 个点的树, 一开始, 每条边都是蓝色的. 现在你可以做 \(n - 1\) 次操作:

  1. 选择一条仅由蓝边组成的路径, 然后删去路径上的某条边
  2. 在路径的两个端点之间连一条红边

给你一棵目标树, 每条边都是红色, 问是这个树否可以通过上述操作构造出来.

\(n \le 10^5\)

Solution

观察: 最后一次操作一定是删去一条蓝边, 然后加上连接同两个点的红边.

于是我们有了一个 \(O(n^2)\) 的判断方法: 每次找到两条相同的边, 缩点之后继续判断即可. 如果最后剩下一个点则有解, 否则无解.

这个问题十分简单. 启发式合并一下 \(O(n \log^2 n)\) 解决. 大力 set 即可.

AtCoder Regular Contest 066

F - Contest with Drinks Hard

Description

有 \(N\) 道题, 每道题有一个耗时 \(T_i\).

你可以选择解决某一些题目, 那么你的分数将会是: 所有满足 \(l \le r\) 并且 \(l...r\) 中的题目都被解决了的有序数对 \((l, r)\) 的数量减去耗时总和.

现在有 \(M\) 个询问, 每次询问将第 \(P_i\) 题的耗时变为 \(X_i\) 时的最大分数. 询问之间相互独立.

\(N, M \le 3 \times 10^5\)

Solution

首先发现如果没有修改, 原问题是可以 \(O(N)\) 斜率优化的. 于是可以处理出 \(dpL\), \(dpR\) 分别表示前缀和后缀的 DP 值.

如果有了修改 \((p, x)\), 考虑两种情况:

  1. \(p\) 不包括在最优解中: 此时答案为 \(\max(dpL(p - 1), dpR(p + 1))\)
  2. \(p\) 包括在最优解中

在情况 2 中, 我们发现每次修改具体修改成什么值并不重要, 所以我们要预处理出 \(dpM(i)\) 表示包含 \(i\) 的方案的最大分数.

这里考虑一种分治的思路. 每次考虑所有完全在 \([l, r]\) 内并且经过 \(mid\) 的区间对 \(dpM(l...r)\) 的贡献. 斜率优化有个很好的性质: 我们把 \([l, mid]\) 的 DP 值丢进栈里, 然后依次考虑 \([mid, r]\) 每个位置的最大分数. 这个最大分数就是强制经过了 \(mid\) 的最大分数. 于是上面这一步做完之后去个后缀 \(\max\), 然后就可以用来更新 \(dpM(mid...r)\) 了. 对于 \([l, mid]\) 也是同理的.

算出 \(dpM\) 之后问题迎刃而解, 时间复杂度 \(O(N \log N)\).

AtCoder Regular Contest 073

F - Many Moves

Description

一条长度为 \(N\) 的数轴, 标号从 \(1\) 到 \(N\). 你有两个棋子, 一开始分别在 \(A\), \(B\) 上.

现在有 \(Q\) 次操作, 每次操作要求你将某一个棋子移动到 \(x_i\) 上. 定义一次移动的代价为数轴上的距离. 两个棋子允许重叠. 问最小移动代价.

\(N, Q \le 10^5\)

Solution

为了方便, 在 \(x\) 数组的最前面加入 \(A, B\).

观察: 做完了前 \(i\) 个操作, 一定有一个棋子在 \(x_i\) 上.

设 \(dp(i)\) 表示当前做完了前 \(i\) 个操作, 并且两个棋子分别为 \(x_{i-1}\), \(x_i\), 此时的最小移动代价. \(O(Q^2)\) 的转移比较显然.

发现转移里有一个绝对值, 开两个线段树维护一下最小值即可. 时间复杂度 \(O(Q \log N)\).

AtCoder Grand Contest 012

这一场好多题之前都听别人讲过了, 于是就没写题解了.

F - Prefix Median

Description

对于一个 \(2n - 1\) 的数列 \(a\), 可以唯一定义一个长度为 \(n\) 的数列 \(b\), 满足:

  • \(b_1\) 为 \((a_1)\) 的中位数
  • \(b_2\) 为 \((a_1, a_2, a_3)\) 的中位数
  • \(\vdots\)
  • \(b_n\) 为 \((a_1, a_2, ..., a_{2n-1})\) 的中位数

现在给定一个长度为 \(2n - 1\) 的数列 \(a\) (不一定为排列), 计算将 \(a\) 任意排列之后, 能产生多少种不同的 \(b\).

\(n \le 50, 1 \le a_i \le 2n - 1\)

Solution

首先将 \(a\) 升序排序.

从 \(a\) 出发对 \(b\) 进行计数不太可行, 考虑找出 \(b\) 能被至少一种 \(a\) 的排列表示的充要条件. 首先注意到必有 \(a_i \le b_i \le a_{2n-i}\).

容易注意到, 中位数一定是在已有的数中"连续"变化的. 也就是说, 对于任意的 \(i < j\), 一定不能出现 \(b_i\) 在 \(b_j\) 和 \(b_{j+1}\) 之间(不含端点)的情况.

上面列出了两个必要条件. 然而事实上这就是充要条件! 非常神奇的结论, 知道了结论要证明也不是很容易, 可以将整个过程倒过来考虑, 从后往前用归纳法证明. 具体细节看题解吧… 不过其实题解也略过了一些细节.

然后计数就很容易了. 还是从后往前考虑. 设状态 \(dp(i, j, k)\) 为考虑到 \(b_i\), 此时有 \(j\) 个可以选择的值, 其中 \(b_{i+1}\) 是这些数的第 \(k\) 小, 此时的方案数.

时间复杂度 \(O(n^4)\).

AtCoder Grand Contest 015

D - A or…or B Problem

Description

求使用多个(\(\ge 1\)) \([a, b]\) 之间的整数或起来可以得到多少种结果.

\(1 \le a \le b < 2^60\)

Solution

显然按位考虑. 从高到低找到第一位满足 \(a\) 为 \(0\) 且 \(b\) 为 \(1\), 记为 \(2^t\). 将数分为两类: A 类为 \([a, 2^t)\), B 类为 \([2^t, b]\).

A 类中的数无论怎么或都只能凑出 \([a, 2^t)\). 如果 A 类和 B 类一起, 也只能凑出 \([a + 2^t, 2^{t-1})\).

不过 B 类自己或自己可以搞出更多来. 具体地, 记 \(2^d\) 为 \(b\) 中最高的低于 \(2^t\) 的 \(1\) 位, 显然 B 可以凑出 \([2^t, 2^t + 2^d)\).

所以答案就是 \(|[a, 2^t + 2^d) \cup [a + 2^t, 2^{t-1})|\).

E - Mr.Aoki Incubator

Description

一开始数轴上有 \(n\) 个点, 每个点有一个正方向的速度. 每个点在 \(0\) 时刻同时开始运动.

现在你可以在 \(0\) 时刻之前将某些点感染. 如果某时刻两个点的坐标重合并且有一个点被感染了, 那么另一个点也会被感染. 一个合法的初始感染方案定义为, 经过足够长的时间后, 所有的点都能被感染.

求所有 \(2^n\) 种方案中有多少种合法的. 对 \(10^9 + 7\) 取模.

\(n \le 2 \times 10^5\), \(x_i, v_i\) 互不相同

Solution

首先将所有人按 \(x_i\) 排序, 记 \(l_i\) 为位置 \(\ge x_i\) 的 \(v_i\) 的最小值, \(r_i\) 为位置 \(\le x_i\) 的 \(v_i\) 最大值. 那么可以发现, 无论在哪个位置, 只要速度在 \([l_i, r_i]\) 之间, 那么都能被 \(i\) 传染. 并且, 容易看出, 如果速度不在这个区间, 那么一定不能被 \(i\) 传染.

接下来就变为一个经典问题:

\(n\) 个点的数轴上有 \(m\) 个区间, 问有多少种选取区间的方案, 可以覆盖所有的点.

这个问题可以在 \(O(n \log n)\) 的时间内解决. 具体地, 设状态 \(dp(i)\) 表示覆盖了 \([1, i]\) 这段区间的方案数. 然后把区间按左端点排序之后用线段树优化转移即可.

不过本题不需要这么复杂. 注意到 \(l_i \le l_{i+1}\) 同时 \(r_i \le r_{i + 1}\), 所以可以直接 Two Pointers 做过去. 时间复杂度 \(O(n)\).

F - Kenus the Ancient Greek

Description

定义一个有序数对 \((a, b)\) 的欧几里德步数 \(step(a, b)\) 为

  • \(step(a,b) = step(b,a)\)
  • \(step(0,a) = 0\)
  • 若 \(0 < a \le b\), \(step(a,b) = step(b, b \bmod a)\)

现在有 \(Q\) 个询问, 每次询问所有满足 \(x \le X, y \le Y\) 的 \(step(x, y)\) 的最大值, 并求出最大值的数量. 对 \(10^9 + 7\) 取模.

\(Q \le 10^5, 1 \le X_i, Y_i \le 10^{18}\)

Solution

首先最大值很好求, 直接在 Fibonacci 序列中找最后一个合法的即可. 但是计数不能直接求, 因为最大值可能会有很多个.

定义 \((x, y)\) 为好的, 当且仅当不存在 \(f(x', y') > f(x, y)\) 且 \(x' < x, y' < y\). 显然我们只用关心好的数对.

观察到对于每个好的 \((x, y)\), 似乎 \((y, y \bmod x)\) 的数量不是很多. 写一个程序试试看, 最后一步直接用除法实现, 然后就 A 了.

证明这个结论有些复杂… 我们可以证明, 所有"倒数第二步"的 \((x, y)\), 都一定满足 \(x, y < F_{k+2} + F_{k-1}\). (这个界和题解的不同, 我觉得题解证错了) 具体证明用到了反证法, 设 \(step(y, px + y) = k + 1\), 那么上一步是 \((x, y)\); 假设 \(y \ge F_{k+2} + F_{k-1}\), 那么就有 \(px + y \ge F_{k+3}\), 于是 \((y, px + y)\) 就不是好的数对了. 矛盾.

证明了这个界, 我们发现对于 \(step\) 为 \(k + 1\) 的层, 从第 \(k\) 层变过来个数只会增加 \(2\). (通过 \((F_k, F_{k+1}) \rightarrow (F_{k+1}, 2F_{k+1}+F_k)\)) 于是第 \(k\) 层的 "倒数第二步" 的个数都是 \(2k\) 个, 也就是 \(O(\log MAX)\) 级别的.

所以总复杂度是 \(O(\log^2 MAX + Q \log MAX)\).

Comments

Comments powered by Disqus