首页 > 其他 > 详细

Codeforces Global Round 9题解

时间:2020-07-09 12:26:51      阅读:78      评论:0      收藏:0      [点我收藏+]

Contest链接

CF1375C Element Extermination

题意:给定一个排列\(a\),每次操作你可以选定一个\(i\),满足\(a_i < a_{i+1}\),然后删除\(a_i\)或者\(a_{i+1}\)。问最后能否使排列仅剩下数字1。\(\sum n \leq 3 \times 10^5\)

题解:大胆猜一波结论:存在方案当且仅当:\(a_1 < a_n\)。事实也确实是这样。为什么呢?

考虑\(a_1 >a_n\)时,我们肯定不希望排列最后只剩下它们两个数,因此需要将\(a_1\)变小或将\(a_n\)变大。但无论我们怎么操作,\(a_1\)是不会降的,\(a_n\)也是不会升的(这里的\(a_1\)\(a_n\)指的是序列首位的元素)。

CF1375D Replace by MEX

题意:给一个序列\(A\),每次操作可以选定一个位置\(p\),令\(a_p=\)这个序列的\(mex\)。你需要进行若干次操作,使得这个序列单调不降。操作次数不能超过\(2n\)

\(n \leq 1000,a_i \in [0,n]\)

题解:为方便起见,我们将序列按\(0\)\(n-1\)编号。考虑能否将序列还原为\(0\)\(n-1\)的序列。

当序列的\(mex\)小于\(n\)时,我们令\(p=mex\);否则,令\(p\)为任意一个\(a_i \neq i\)的位置\(i\)。这样做,操作次数的上界为\(1.5n\)。下面是一个简单的证明:

考虑当\(mex=n\)时,整个序列是\([0,n-1]\)的一个排列。我们做完一次操作后,序列的\(mex\)就变为了\(a_p\),令\(a_{a_p}=a_p\)后,序列的\(mex\)又变成了原来的\(a_{a_p}\)。那么要使\(mex=n\)的出现次数最多,显然形如\(0,2,1,4,3,\cdots\)这样有很多"2-cycle"的排列是最毒瘤的,每做2次,序列的\(mex\)就会变成\(n\)

直接模拟即可。

时间复杂度:\(O(n^2)\)

CF1375E Inversion SwapSort

题意:给定一个序列\(A\),长度为\(n\)。我们记录下序列所有逆序对的下标\(u_i,v_i\)。你需要给所有的\({u_i,v_i}\)指定一个顺序,每次交换\(a_{u_i},a_{v_i}\),使得所有操作完成后的序列单调不降。

\(n \leq 1000,a_i \leq 10^9\)

题解:先考虑对于一个排列如何求解。设\(p_{a_i}=i\)

我们尝试从后往前逐位确定答案。考虑当前序列的最后一位\(n\),它想成为\(n\),那么\(a_n\)必须在与\(n\)有关的最后一次操作中被换到位置\(n\)。所以,我们只需要依次进行如下的操作:(\(p_{a_{i+1}},n\)),(\(p_{a_{i+2}},n\)),\(\cdots\),(\(p_{n},n\))即可。剩下的问题就是一个\(n-1\)的子问题了。

那么对于序列的情况也就很简单了:将所有元素按\(a_i\)为第一关键字,\(i\)为第二关键字排序,化成排列的问题即可。

时间复杂度:\(O(n^2)\)

CF1375F Integer Game

题意:这是一道交互题

有三堆石子,个数分别为\(a,b,c\)。游戏的规则如下:

  • 先手每次给定一个数\(k\),后手需要给这三堆石子的某一堆的个数加上\(k\)
  • 后手不能连续对同一堆石子进行操作。
  • 当存在两堆石子个数相等时,先手胜;当回合数超过1000时,后手胜。

你可以自行决定当先手还是后手。

\(a,b,c \leq 10^9,k \leq 10^{12}\)

题解:考虑什么情况下后手无法操作:

  • 设当前石子个数为\(a,b,c\),且\(a<b<c\),上一次操作的是\(c\)这堆石子。
  • 那么当\(a,b,c\)形成等差数列时,后手就无法操作了。

因此,这是一个先手必胜的游戏。我们只需要构造一种方案,使它到达这种状态即可。

还是令\(a<b<c\),那么我们先强制让操作后的那对石子个数最大。显然令\(k=c-a\)即可。

现在,上次操作的一定是\(c\),那么我们稍微计算一下,令\(k=2c-a-b\),就能让得到的\(a,b,c\)成为一个等差数列。并且由于\(a+k>c\),所以操作的那堆石子在操作完成后一定是个数最多的。

CF1375G Tree Modification

题意:给定一棵\(n\)个点的树,一次操作,你可以选定三个点\(a,b,c\),要求\(a\)\(b\)相邻,\(b\)\(c\)相邻,然后进行如下操作:

  • 所有与\(a\)相邻的节点和\(c\)连边;
  • 断掉连接\(a\)与其所有相邻节点的边;
  • \(a\)\(c\)连边。

你需要最小化操作次数,使得这棵树仅存在一个节点度数为\(n-1\),其他节点的度数都为\(1\)。不需要输出方案。

\(n \leq 2 \times 10^5\)

题解:由于树无环,我们可以将其看做一个二分图,并将其黑白染色。那么目标状态显然是只有一个黑或白点。考虑一次操作对黑白点个数的影响。我们设\(c\)是黑色的。

对于所有与\(a\)相邻的节点及其子树内的点,颜色不变;只有节点\(a\)的颜色改变了。

因此,一次操作只会使黑或白点个数变化1。那么答案显然就是\(min(cnt_{white},cnt_{black})-1\)

直接DFS一遍就好了。

Codeforces Global Round 9题解

原文:https://www.cnblogs.com/Purple-wzy/p/13272864.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!