首页 > 其他分享 >【官方题解】Codeforces Round 939 (Div. 2)

【官方题解】Codeforces Round 939 (Div. 2)

时间:2024-04-14 17:36:32浏览次数:36  
标签:Hint Nene 题解 Codeforces 939 solve 怪物 操作 mathcal

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

相关文章

  • [暴力题解系列+正经题解]好数
    好数虽然不是13号考的那批人,但是还是扔一个暴力题解在这里。首先数据范围\(n\le10^7\),就算纯粹暴力去做也只是\(O(nlogn)\),也就是直接从1到n去枚举。秉持着暴力就是要优化细节的精神,对题目进行一个分析,发现无论如何,个位数必须是奇数,否则必然不满足条件,那么优化手段就显而易见了......
  • P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    题目传送门试题A:空间【解析】本题考察计算机存储的基础知识,只要掌握空间存储的换算方法,就能够算出答案。【程序】#include<bits/stdc++.h>usingnamespacestd;intmain(){printf("%d\n",256*8/32*1024*1024);return0;}【答案】67108864......
  • P8679 [蓝桥杯 2019 省 B] 填空问题 题解
    题目传送门试题A:组队【解析】本题是一道经典的DFS搜索题,每次对各号位的选手进行DFS,找到各号位上有成绩的选手时再进行进一步搜索即可。【程序】#include<bits/stdc++.h>usingnamespacestd;intteam[20][6];intmax_sum;boolvis[20];voiddfs(intu,intsu......
  • P9686 Judg. 题解
    题目传送门一道简单模拟。这道题最简单的方法就是直接在for循环中判断题目给出状态是否为AC,如果不是则输出当前\(i\)的值,否则就不输出。#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+10;intn;stringa[MAXN];intmain(){ scanf("%......
  • P9517 drink 题解
    题目传送门这道题考场上用的查找做的。先用一个结构体分别表示firstlast,然后进行查找即可,两个for循环分别计算出first和last,最后计算它们的差值。(注意,计算差值时要加1)然后你就会发现一个问题:只有\(90\)分。所以我们来思考一下哪里出现了问题。你会发现:如果全都是......
  • P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    题目传送门试题A:空间【解析】本题考察计算机存储的基础知识,只要掌握空间存储的换算方法,就能够算出答案。【程序】#include<bits/stdc++.h>usingnamespacestd;intmain(){printf("%d\n",256*8/32*1024*1024);return0;}【答案】67108864......
  • [题解]P3413 萌数
    P3413萌数先打出暴搜代码,参数有\(pos,limit,hui\),其中bool类型的\(hui\)表示到当前是否有回文。暴搜代码中加入了一个剪枝:if(!limit&&hui)returnpow10[pos];,这个!limit很重要,我就是因为这个没加,暴搜代码都调了半天。然后就是if(pos==0)returnhui;。我们还需要记录下填过的......
  • [题解]CF55D Beautiful Numbers
    CF55DBeautifulNumbers打出暴搜后有些茫然,不知道该怎么优化才好,看了题解才豁然开朗。简单说下暴搜的思路:参数有\(pos,limit,lcm,num\)。其中\(lcm\)表示到\(pos+1\)位,所有非\(0\)位的\(lcm\)是多少;\(num\)表示填到\(pos+1\)位的整个数是多少。然后在\(pos=0\)时判断\(lcm\)是......
  • [题解]CF1073E Zegment Sum
    CF1073ESegmentSum这道数位dp与其他不同的是,这个求的是满足要求的数的和,这种题型的题我们还没有做过。以前虽然做过一些求和或者求积的题,但都是求每个满足条件的数的数位和、二进制1的个数等等的和。而这道题是对\([L,R]\)中满足条件的数直接求和,这意味着基本不会有两个状态得......
  • [NOIP2018] 旅行 题解
    明显要以\(1\)为起点。原图是树这种情况下,走路不能回头,只能用\(dfs\)的思路走。当然肯定每次都走较小的那棵子树,\(vector\)存图后排序即可达到这种效果。时间复杂度\(O(n\logm)\)。原图是基环树明显可以分别考虑将所有边断掉后的情况,取字典序最小的。时间复杂度\(O(......