AtCoder Grand Contests
大坑。
有意思的题会写题解。
Status
# | A | B | C | D | E | F |
---|---|---|---|---|---|---|
AtCoder Grand Contest 001 | · | · | · | · | · | · |
AtCoder Grand Contest 002 | · | · | · | · | · | · |
AtCoder Grand Contest 003 | · | · | · | · | · | · |
AtCoder Grand Contest 004 | · | · | · | · | · | · |
AtCoder Grand Contest 005 | · | · | · | · | · | · |
AtCoder Grand Contest 006 | · | · | · | · | · | · |
AtCoder Grand Contest 007 | A | A | A | A | · | · |
AtCoder Grand Contest 008 | · | · | · | · | · | · |
AtCoder Grand Contest 009 | · | · | · | · | · | · |
AtCoder Grand Contest 010 | · | · | · | · | · | · |
AtCoder Grand Contest 011 | · | · | · | · | · | · |
AtCoder Grand Contest 012 | · | · | · | · | · | · |
AtCoder Grand Contest 013 | · | · | · | · | · | · |
AtCoder Grand Contest 014 | · | · | · | · | · | · |
AtCoder Grand Contest 015 | · | · | · | · | · | · |
AtCoder Grand Contest 016 | · | · | · | · | · | · |
AtCoder Grand Contest 017 | · | · | · | · | · | · |
AtCoder Grand Contest 018 | · | · | · | · | · | · |
AtCoder Grand Contest 019 | · | · | · | · | · | · |
AtCoder Grand Contest 020 | · | · | · | · | · | · |
AtCoder Grand Contest 021 | · | · | · | · | · | · |
AtCoder Grand Contest 022 | · | · | · | · | · | · |
AtCoder Grand Contest 023 | · | · | · | · | · | · |
AtCoder Grand Contest 024 | · | · | · | · | · | · |
AtCoder Grand Contest 025 | · | · | · | · | · | · |
AtCoder Grand Contest 026 | · | · | · | · | · | · |
AtCoder Grand Contest 027 | A | T | · | · | · | · |
AtCoder Grand Contest 028 | A | A | · | · | · | · |
AtCoder Grand Contest 029 | A | A | A | · | · | · |
AtCoder Grand Contest 030 | · | · | · | · | · | · |
- A: Accepted
- T: Tried
- R: Read
Solutions
7C
猜他拿完一个以后期望仍然是等差数列就赢了。(反正我是看了题解)
第 $i$ 段,分三种情况讨论,贡献分别如下(这一部分题解省略了):
- $\frac{i}{2n} (d + (i + 1)x)$
- $\frac{1}{2n} (3d + 3 i x)$
- $\frac{2n-i-1}{2n} (d + (i-1)x)$
7D
跟多校的某个折线题(我记得有张图的)很像。搞清楚答案的形状之后,转移方程就是:
$f_i = min_{1 \le j \le i} \{ f(j - 1) + \max(2(x_i-x_j), T) + (x_i - x_{j-1})\}$。
max 的那部分可以用单调队列处理,中间的那部分维护一个单调增队列,弹出来以后更新一个全局最小值。最后答案就是两部分的 min。
12C
很容易想到二进制分解,不过太长了。
遂自闭。
题解中的构造方法是 $(p_1,p_2,\ldots,p_n,1,2,\ldots,n)$。这样的话前面和后面的部分的公共子序列会贡献 1。问题就转化成了构造一个排列使得上升子序列个数恰好为 $n$。
然后发明了一种假算法 WA 了,又自闭了。
题解是这样的:假设已经有 $1$ 到 $n$ 的某个排列,上升子序列个数是 $k$。把 $n+1$ 加在后面,可以得到 $2k$,把 $n+1$ 加在前面可以得到 $k+1$。然后递归构造就好了。
当然还有一个有趣的问题是这题的 SPJ 怎么写。(貌似是一个挺经典的 DP)
12D
首先如果 a 能和 b 换,b 能和 c 换,那么 a 就能和 c 换。所以只要把连通关系找到。
很容易想到一个东西越小它就越是 flexible。所以每种颜色最小的跟其他的连边;所有颜色中最小的跟其他颜色的连边。那么最小的里面稍大一点的可能还不能顺利连通;所以还要挑第二少的颜色连一下边。
题解似乎不是这么做的,看起来复杂得很。
12E
做了好几天,有了好几个 observation,但是最后还是看了题解(悲伤)。首先问题转化成:能否将 $x_1$ 到 $x_n$ 划分成若干个区间,使得每个区间内的东西相邻距离都不超过 $v_k$。对于固定的 $v_1$ 输出答案。然后我发明了一套树上乱搞的方法,自闭了。
题解是子集 DP。记录每种子集能覆盖的最大前缀和最大后缀。最后把第一个贴上,判一判就好了。写起来稍微有点痛苦。
17B
式子推错了,两次!捣鼓了好久。
17C
考虑如果最后要变成 $1$ 到 $n$ 怎么做:我们把所有数装在桶里,最后有几个桶是空的,答案就是几。
现在如果有 $k$ 个 $x$,就给 $x, x-1, \ldots, x-k+1$ 这些桶里都加 1。很容易看到,最后有几个桶是空的,答案就是几。
随便维护一下就好了,不需要数据结构。
17D
AGC 也出原题?
17E
很显然把拼图当成边建图,这个图有两部分,我们要将这个图分解成若干起点在左边、终点在右边的路径。
数据规模不大,可以网络流。左边有残余的点连 S,右边有残余的连 T,跑最大流,先检查是否满流。然后要想办法把可能剩下的一些环拼上去。发现只要检查图的连通性就可以(有边的点是否都跟 S 相连)。
题解是 $O(H)$ 的,显然想得更清楚。
22E
坑。