Atcoder/Topcoder 口胡记录

Atcoder/Topcoder 理论 AC

Atcoder的❌游戏示范

  • 兴致勃勃地打开一场 AGC
  • 看 A 题,先 WA 一发,然后花了一年时间 Fix。
  • 看 B 题,啥玩意?这能求?
  • 睡觉觉。

emmmmm 虽然这些副本里的怪一点也不友善,但是却能给直感[1]带来极大的提升。

[1]:「直感」是在战斗中一瞬间判明「对自身最适合行动」的能力


Atcoder Grand Contest 2

B. Box and Ball

口胡 考虑 \(k\) 次操作后可能出现红球的集合,记录每个集合球的个数。

C. Knod Puzzle

口胡 考虑合体,若 \(max\{a_i+a_{i+1}\}<L\) 完蛋。否则先合并 \(a_i,a_{i+1}\)。

D. Stamp Rally

口胡

  • 二分加入多少条边,能解决一组查询,复杂度 \(O(Qmlog(m))\),然后发现每次二分都加边十分智障。
  • 对 Q 组查询整体二分即可。用三元组 l,r,vector<> 表示,vector<> 里的答案在 \([l,r]\) 之间。
  • 对线段树进行 BFS 层序遍历,先解决答案小的询问,也就是先加入右儿子,这样每层都需要要初始化并查集,然后加入每条边。

Atcoder Grand Contest 03

B. Simplified mahjong

题解中的做法

  • 考虑 \(a_i>0\) 的 case,按牌的点数 sort,能取到上界 \([\frac{sum}{2}]\)。
  • 考虑 \(a_i=0\) 的 case,把点数连续的牌,独立考虑。

口胡

  • 观察到 \(i,i+1\) 这样的匹配至多只有 1 个。
  • \(dp[i][0/1]\) 考虑点数 \(1\)~\(i\) 的牌,第 \(i\) 有没有与 \(i-1\) 匹配,最大匹配数。

C. BBuBBBlesort!

口胡

  • 注意到操作 2 能独立地 shuffle \((a_1,a_3,a_5,...),(a_2,a_4,.....)\)
  • 每个元素,都有应该出现的位置,如果应该出现在奇数位置的元素,出现在偶数的位置上,那么我们应该对着它施展操作 1。

D. Anticube

口胡

  • 放逐小的质因子,分类讨论剩下的大质因子。vanishiment this world !

E. Sequential operations on Sequence

口胡

  • \(a_i > a_{i+1}\), 那 \(a_{i}\) 在划水!
  • 倒序考虑,每个数字找到上一个比它小的元素,单调栈线性时间即可求出。
  • 于是剩下一个递增的序列 \(q_1,q_2,...,q_m\),考虑 \(f(i,len)\) 表示 \(q_i\) 的串长度为 \(len\) 的前缀。寻找一个前驱可递归地表示 \(f(i,len)\) 这个串。
  • 口胡这场比赛之前在学欧几里得,取模! 很强!。
  • 复杂度 \(O(NlogNlogMAX)\)
  • F0_0H 先手随手一写就 TLE 了。
  • F0_0H 再随便一改就过了,HYNB!

F. Fraction of Fractal

口胡

  • 观察两个 k=1 的矩阵。分类成 2 * 2 种 Case
    1. 两个矩阵左右放置黑格能否连通。
    2. 两矩阵上下放置黑格能否连通。
  • 1,2 都成立。\(ans=1\)
  • 1,2 都不成立,\(ans=x^{k-1}\)
  • 猜测上下的连通性,左右的连通性在 \(k>1\) 级能一直 keep
  • 啊啊啊啊啊啊啊,好难不会,看题解去。

题解

  • 很接近了。
  • 不妨设 1 成立,2 不成立。
  • 考虑 \(k-1\) 级变成,\(k\) 级的过程。
  • 设 \(k-1\) 中有 \(x\) 个黑格,\(y\) 个左右相邻的黑格。那么 \(k\) 级中,有 \(x-y\) 个连通块
  • 矩阵快速幂求 \(k\) 级中,有多少个左右相连的黑格,左边界右边界有多少个连接点。

Atcoder Grand Contest 4

B. Colorful Slimes

口胡 枚举一共施展了 \(x\) 次 shift,那么 \(i\) 可以由 \(i,i-1,i-2,...i-x\) 获得。

C. AND Grid

口胡 注意到最边上这圈为空,统统连起来吧。

D. Teleporter

做法

  • 让 1 指向 1,否则解体。否则可以按 1 到 1 的极短环的长度 \(len\) 划分成 非空的 \(len\) 个集合,这些集合中,至多只能有一个符合 k 步到 1 的要求。
  • 问题转化为:给一棵树,修改最少的节点的爸爸,使得树的深度小于 \(k\)
  • 自下向上考虑即可。【HYNB】

E. Salvage Robots

口胡

  • 考虑移动的过程,我们记录下 x 方向上位移极小极大,y 方向上位移极小极大,与当前位移。
  • \(f[min_{dx}][max_{dx}][min_{dy}][max_{dy}][dx][dy]\) 表示在这个状态下最大得分。
  • 然后一想,这状态没法转移,因为我从一个状态移动一下不知道能不能吃到东西啊。
  • 再一想,这状态设计很沙雕啊,最后两维没必要,因为确定了横纵坐标位移的极小极大,某个矩形区域内的所有东西都可以吃掉啊,根本不用,care现在位移是多少。
  • \(f[min_{dx}][max_{dx}][min_{dy}][max_{dy}]\) 设计状态。
  • 考虑转移一个状态的转移至多有 4 种,\(f[min_{dx}][max_{dx}][min_{dy}][max_{dy}]\) -> \(f[min_{dx}+1][max_{dx}][min_{dy}][max_{dy}]\)。状态 State 有可以随便吃的泡泡集合\(canEat(State)\),考虑 \(f(cur) = max\{ f(prev) + |canEat(cur) - canEat(prev)| \}\)
  • 注:集合 A - 集合 B 表示对称差

  • 往枚举方向想,很容易解体,虽然枚举是很直观的做法。
  • 试图走直线直接奔赴结果,不失为一种策略,但是容易撞墙上。
  • 这个问题枚举不妥,是因为操作的有序性。
  • 一道计数题:容斥?枚举?解体。
  • 人生如棋,世事难料,笑尽英雄啊。【乱入的「百世经纶·一页书」(`・ω´・ )v】
  • 在难测的棋局中,寻找决定性的因素何在,是为设计状态的动机。
  • 研究决定性的因素的转化,使一切尽在掌控之中,这是状态转移。
  • DPNB!

F. Namori

口胡 啥也没想到,脑壳痛。老想着拿树形 DP 解决问题,但无法把子树合并到父亲。为什么呢?因为操作有序性。

  • 有趣了,上一个题因为操作有序性,枚举做不了,要 DP。
  • 这里操作有序性,DP 直接解体。
  • 这是为什么啊?
  • 这是因为 DP 会把一个问题,分解成好多个子问题,先然后解决子问题,再合并子问题答案。
  • 但是,这里,子问题不认为自己是子问题。u 节点的子树认为自己受到了不公正的对待,它不满地表示:凭什么要我先弄好颜色,你们先施展,我先睡觉觉。
  • 然后就解体了。

题解 for small

  • 树是二分图,先把右集的点全都变成黑色。
  • 于是现在:『选择两个同色的点』修改为『选择两个异色的点』
  • 在左集的每个点放硬币,问题转化为,「可以花 1 的代价,把硬币移动到相邻的没有硬币的节点上」。
  • 考虑一条边会被经过几次,某子树内现在有 \(x\) 个硬币,需要 \(y\) 个硬币,那么有 \(|x-y|\) 个硬币经过了这个点向爸爸的边,由此可以确定答案的一个下界。
  • 证明下界可以取到。【还没看,先试着自己证一下】
  • 利用树是二分图,扭转一个集合的颜色,使得同色->异色。极具创造性的转化!
  • 变成挪硬币问题,天马行空般的想象。
  • 再加上一段证明,精彩的问题!

Atcoder Grand Contest 5

C. Tree Restoring

做法

  • 画直径。
  • 其它点与直径上的点相连。

D. ~K Perm Counting

做法

  • 容斥,考虑 ban 掉 \(i\) 个条件的方案数。
  • \(x\) 向 \(x-k,x+k\) 连边,不存在奇环,二分图!
  • 求 i-match 即可。
  • 连接的边形成 2k 条链,每条链长度为 \([\frac{n}{k}]-1\) 或 \([\frac{n}{k}]\)
  • 对每条链做 dp, \(f[i][j][0/1]\) 表示前 \(i\) 条边,拿 \(j\) 条,最后一条有没有拿的方案数。
  • 把这些链背包合并起来,合并 \(O(k)\) 次,一次代价为 \(O(\frac{n}{k}n)\),复杂度 \(O(n^2)\)

E. Sugigma: The Showdown

题意 两棵树,Alice 追 Bob

做法

  • 如果 Bob 的某条边,在 Alice 的树中距离大于等于 3,那么 Bob 走上这样的边,或者 Bob 比 Alice 走上这样的边的端点时间更短,那么游戏就永远不会结束,而 Bob 非常希望这样的情况发生。
  • 考虑 Bob 剩下的边,剩下的边在 Alice 的树中距离等于 1 或者 2.
  • 考虑 Alice 的策略,每步都逼近 Bob 是最优的。
  • Bob 能到达 \(u\) 点,等价于路径上所有点都能比 Alice 先到。
  • 在可以到达的点集中,选出最优的点。(能 inf 就 inf 否则选出距离最远的点。)

F. Many Easy Problems

做法

  • 考虑一个确定的 \(k\) 如何 \(O(n)\) 计算答案。
  • 考虑每条边对答案的贡献即可。
  • 点 \(u\) 向父亲的边对答案的贡献为 \(\binom{n}{k}-\binom{x}{k}-\binom{n-x}{k}\), \(x\) 表示,\(u\) 子树的大小。
  • 计算长这样的东西 \(f(k)=\sum_{x=k}^{n} c_x\frac{x!}{k!(x-k)!}=\frac{1}{k!}\sum_{x=k}^{n}c_xx!*\frac{1}{(x-k)!}\)
  • NTT 解决之。

code


Atcoder Grand Contest 005

B. Median Pyramid Easy

题意 梯状图,在最底层填入一个排列,能否使得最顶上的数字取到 \(x\)

做法

  • 观察小 Case
  • 构造思想是:把需要构造的数字 \(x\) 放在中间,比它小的放左边,比它大的放右边。这样才能保证 \(x\) 始终是中位数。
  • 左边太多?移动至右边。

C. Rabbit Exercise

题意 好多兔子跳来跳去,每次第 \(x_i\) 只兔子随机选择 \(x_{i-1},x_{i+1}\) 号兔子,跳至对称点。

做法

  • 不变的存在,是什么呢?
  • \(x_{i-1},x_i,x_{i+1} => x_{i-1},x_{i-1}+x_{i+1}-x_i,x_{i+1}\)
  • 交换公差!
  • 求出一次变换的置换,求 \(k\) 次幂即可。

D. Median Pyramid Hard

题意 梯状图,在最底层填入一个排列,求上层填什么。

做法

  • 二分答案 \(x\),于是数字分成 \(<=x\) 的数字(标为 0)和 \(>x\) 的数字(标为 1)。
  • 于是只需考虑一个 01 序列的答案【
上一篇:$CH$ $0x50$ & $0x51$ 做题记录


下一篇:python 获取随机字母