Codeforces Round Ayachi Nene Solutions (div. 2)
A. Nene's Game
Idea: [user: Otomachi_Una]
Solution
不难发现如果一个人初始位置 \(p\geq a_1\),那么必然会在有限次回合当中被踢出。答案即为 \(\min(n,a_1-1)\)。
B. Nene and the Card Game
Idea: [user: Otomachi_Una]
Hint
两个人手上的对子和单牌数应该是相同的。
Solution
分析每种花色,有三种情况:
- 都在你手上,你必然获得这一分。
- 都在 Nene 手上,你必然得不到这一分。
- 一张在你手上,一张不在你手上,你也得不到这一分。
对于最后一点,Nene 可以这样子操作:
- 当你打出的牌是你对子中的一张时,Nene 也打出对子的一张。
- 当你打出对子中的另一张,Nene 也打出对子的另一张得分。
- 当你打出单牌,Nene 就打出另一张相同花色的牌。
这样子对于单牌你永远不可能得分。
所以答案就是你手上的对子树。
C. Nene's Magical Matrix
Idea: [user: Otomachi_Una]
Hint
当 \(n=3\) 的时候,最优解如下:
1 2 3
2 2 3
3 3 3
Solution
不难发现最大总和的情况如下:
1 2 3 ... n
2 2 3 ... n
3 3 3 ... n
..... ... n
n n n n n n
构造是依次给 \(i\) 行、列赋值 \(1,2,3,\dots,n\)(\(i=n,n-1,\dots,1\))。
Proof
把 \(\geq x\) 的元素是作为 \(1\),\(<x\) 的元素视作为 \(0\),最后得到 \(1\) 的个数记为 \(f_M(x)\)。那么总和即为 \(f_M(1)+f_M(2)+\dots+f_M(n)\)。
下面证明:\(f_M(x)\leq n^2-(x-1)^2\)。
一次操作可以视作为:给一行或一列染 \(x-1\) 个 \(0\),\(n-(x-1)\) 个黑。
尝试加强结论,说明:对于任意的 \(n\times m\) 的矩阵,每次操作可以对一行染 \(x\) 个 \(0\),\(m-x\) 个 \(1\);或者对一列染 \(y\) 个 \(0\),\(n-y\) 个 \(1\)。想要填满这个矩阵至少需要 \(xy\) 个 \(0\)。我们使用归纳法证明。
如果 \(x=m\) 或者 \(n=y\) 那么结论显然成立。
否则,不妨设最后一次操作是对最后一行染色,那么对于列操作,每次至少会对前 \(n-1\) 行染 \(y-1\) 个 \(0\)。
采用归纳法,得知前 \(n-1\times m\) 的格子当中至少有 \((y-1)x\) 个 \(0\)。
加上最后一列 \(x\) 个 \(0\),一共就是 \(xy\) 个 \(0\)。
QED。
D. Nene and the Mex Operator
Idea: [user: Otomachi_Una]
Hint 1
考虑 \(a_i=0\) 能得到的最大值。
Hint 2
钦定一些 \(a_i\) 不进行操作。操作过的 \(a_i\) 最终都不会太大。
Solution
考虑 \(a_i=0\) 时,我们总和可以达到 \(n^2\),即 \(a_i=n\)。具体构造如下:
- 定义 \(solve(k)\) 为把 \(a_1\sim a_k\) 全部变为 \(k\) 的方案。
- \(solve(1)\) 可直接使用操作 \((1,1)\)。
- \(solve(k)\)(\(k\geq 2\))可以先调用 \(solve(k-1)\),再把前 \(k-2\) 个元素归零,然后再调用 \(solve(k-2)\),再把前 \(k-3\) 个元素归零,如此直到调用 \(solve(1)\) 之后。当前的 \(a=[1,2,3,\dots,n-1,0]\)。操作 \((1,n)\) 即可。
可以证明,每时每刻数列 \(a\) 的 mex 不会超过 \(n\)。
本题中,我们考虑钦定一些 \(a_i\) 不进行操作,那么进行操作的 \(a_i\) 最大值不会超过所属进行操作的 \(i\) 的极长段的长度。我们只需要判断哪种方案得到的值最大(这里可以使用 dfs 或者 dp),然后对每一段如果需要操作,先把要操作的元素全部清 \(0\),再如同上面那样 solve 即可。
操作数不会超过 \(\mathcal O(2^n)\)。
E. Nene and the Passing Game
idea: [user: Otomachi_Una]
Hint
两个人 \(i<j\) 能够传球,可以视作为:\([i+l_i,i+r_i]∩[j-r_j,j-l_j]\neq \empty\)。
Solution
根据 Hint,我们可以向数轴上每个整点视作一个额外点。每个人 \(i\),向额外点区间 \([i-r_i,i-l_i],[i+l_i,i+r_i]\) 连边(这里复杂度是 \(\mathcal O(n\alpha(n))\) 的)。最终的答案就是每个人所属本质不同连通块数。
但是有个小问题,按这样子计算如果两个人 \(i<j\),\([i-l_i,i-r_i]∩[j-r_j,j-l_j]\neq \empty\) 也被记入了,不能完成。
为了解绝这个问题,我们可以只保留数轴上同时被某两个 \([i-r_i,i-l_i],[j+l_j,j+r_j]\) 覆盖的点即可,这里使用前缀和找这些点复杂度是 \(\mathcal O(n)\) 的。
F. Nene vs. Monsters
idea: [user: Otomachi_Una]
Hint 1
如果连续三个怪物的能量形如:\(0,x,y\)(\(x,y>0\)),那么血量为 \(y\) 的怪物一定会死亡(因为会不断收到 \(x\) 攻击)。
Hint 2
如果五个连续的怪物能量形如:\(0,x,y,z,0\)(\(x,y,z>0\)),那么 \(x\) 必然存活,\(y\) 必然死亡,如何判断 \(z\) 的最终状态呢?
Hint 3
如果有一个四连段 \(x,y,z,w\)(\(x,y,z,w>0\)),那么经过宁宁几次魔法之后必然会有一个怪物死亡呢?
Solution
注意 Hint 3,假设经过了 \(t\) 次魔法都不会有人死亡,那么分析 \(w\) 的血量下限。
首先 \(x\) 每次打出的伤害至少为 \(1\),那么 \(y\) 至少受到 \(t\) 的伤害。\(z\) 至少收到 \(t-1+t-2+\dots=\mathcal O(t^2)\) 伤害,即初始血量至少为 \(\mathcal O(t^2)\) 的。同样的 \(w\) 初始血量至少为 \(\mathcal O(t^2+(t-1)^2+\dots+1^2)=\mathcal O(t^3)\)。
假设 \(V=10^9\),那么也就说明当 \(t\sim\mathcal O(\sqrt[3]V)\) 的时候必然有一个怪物死亡。
我们可以先跑 \(\mathcal O(\sqrt[3]V)\) 轮,这时候场上就不会有连续的四个活着的怪物了。我们可以对每一个段分析。这个段只有 \(1\sim 3\) 个怪物 \(x,y,z\)(\(x>0,y,z\geq 0\)):第一个怪物必然存活,第二个必然死亡;第二个怪物发出的攻击力为 \((y-x)+(y-2x)+\dots+(y\bmod x)\)。这部分可以用等差数列求和来解绝。
通过算出第二个怪物造成的伤害,第三个怪物的存活情况便知道了。
时间复杂度:\(\mathcal O(n\sqrt[3]V)\)。
标签:Hint,Nene,题解,Codeforces,939,solve,怪物,操作,mathcal From: https://www.cnblogs.com/OtomachiUna/p/18134399