差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:hotpot:atcoderbc176 [2020/08/28 09:03]
lotk
+++ 2020-2021:teams:hotpot:atcoderbc176 [2020/08/28 13:07] (当前版本)
喝西北风
@@ 行 1: / 行 1: @@
 ======AtCoder Beginner Contest 176======
-=====A.Orac and Factors=====
+=====A - Takoyaki =====
 ====题目大意====
-对于一个数 $n ≤ 10^6$ ，找到它最小的不是1的约数，然后加在这个值上，重复 $k ≤ 10^9 $次
+给 $n,x,t$ ,问 $n/x$ 取上整乘 $t$.
 ====解题思路====
-首先对于偶数，这个数一定是 2，而对于奇数，一次操作之后就会变成偶数，答案是显然的。
+模拟
-=====B.Orac and Models=====
+=====B - Multiple of 9=====
 ====题目大意====
-给定一个数列$ a_n  (n \le 1e6) $, 求一个最长子列，满足其前一个的下标是后一个的因数且 $a_j  > a_i $.
+给定一个长为 $n \le 2e5$ 的数，问其是否是9的倍数。
 ====解题思路====
-这题显然就用一个 DP 就能在 $ O( nlogn ) $ 的时间内解决了.
+每位的数相加看能否整除9即可。
-=====C.Orac and LCM=====
+=====C - Step=====
 ====题目大意====
-给定一个数列 $ s_n (n \le 100000) $ ,令 $ t = \{ lcm({a_i,a_j})|i < j \} $ ,求 $ gcd(t) $
+给定长为 $n \le 2e5$ 的数组。允许给每个数任意加值，问最少加多少使数组非减。
 ====解题思路====
-考虑对每个素数因子进行分析，经过$ lcm,gcd $操作之后相当于求每个因子在所有数中出现次数倒数第二小的次数并相乘，模拟即可。
+原本非减就不管，否则加到和前一个数一样大即可。
-注意：可以通过先提取出前两个数所含因子来显著减小复杂度
+=====D - Wizard in Maze=====
-=====D.Orac and Medians=====
+====题目大意====
+给定 $H×W ，H，W \le 1000$ 的一张图，图上有一些不能走的点，支持两种操作，一是走相邻的格子不消耗步数，二是在周围 $5×5$ 的格子内任意移动并消耗一个步数，问最少多少步能够从一点到另一点。
+====解题思路====
+本题图的范围较大，我们不能直接用SPFA解决，而需要通过一次dfs和并查集处理出连通块，再通过bfs得出结果。
+=====E - Bomber =====
 ====题目大意====
-给定一个数列 $ a_n (n \le 100000 ，1 \le a_i \le 1e9) $ , 再给定一个数 $k (1 \le k \le 1e9) $, 问能否通过把一个区间全部变成它的中位数的方式使序列全部变成$ k $.
+在一张 $H×W ，H、W \le 3e5$ 的图上，给定一些点 $(n \le min(H×W,3e5))$，问选定一行一列最多能覆盖多少个点。
 ====解题思路====
-首先，如果不存在 $ k $,那么答案肯定是否， 在存在 $ k $ 的情况下 ，如果 $ k $ 旁边有大于 $ k $ 的数，那么我们显然可以通过将这个数变成 $ k $ 和原本 $ k $ 的区间将别的数都变为 $ k $, 进而我们发现，如果连续三个中存在两个 $\ge k$ ,那么可以通过区间操作将大于 $k$ 的数移到 $k$ 的旁边，若不存在，则不可能实现 (可以证明任意区间都会被变成小于 $k$ 的区间)。
+我们显然可以处理出覆盖点最多的行和列，然后依次枚举检查它们交叉的点处有没有点即可，由于点的个数有限，这个检查是符合复杂度的。
-=====E.Orac and Game of Life=====
+=====F - Brave Chain=====
 ====题目大意====
-给定一个 $ n \times m 的 01 矩阵 (1 \le n,m \le 1000)$, 每个时间一个周围存在不同类型点的点的类型会发生改变 $ (0 \rightarrow 1, 1 \rightarrow 0) $ 给定 $ t \le 100000 $ 个询问，每次问 $ i , j $ 位置上 $ p $ 时间的类型。
+给长度为3n（$n\le 2000$）的序列，每个数都是1到n。每次从前五个里挑三个删除，若这三个数相等，则结果加一。最后剩下的三个若相等，结果也加一。问最终答案的最大值。
 ====解题思路====
-我们发现这个模型具有“传染”的性质，即上一时间变了的点周围没变的点，在下一时间会变且之后一直保持变的状态，因此我们只需要通过 $BFS$ 一次求出每个点开始变的时间并计算最后状态即可。
+首先最朴素的思想，是枚举前一次剩下的结果，复杂度$O(n^3)$。随后，发现每次转移的结果，要么是原先的两个，要么是原先的一个加之后的三个中的一个，要么是三个中的两个。后两种一共O(n)种情况，记录一下所有剩余情况的最大mx和所有剩余的里有i的最大$f_i$即可。第一种除非三个全相等，否则结果不变。可以证明，三个全相等时，最优情况一定是删这三个。因此可以单独再用一个数cnt记录这个即可。最终答案为$cnt+max\{mx,dp[a[3n]][a[3n]]\}$。

CVBB ACM Team

用户工具

站点工具

差别

页面工具