题意:给定一个排列\(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\)指的是序列首位的元素)。
题意:给一个序列\(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)\)。
题意:给定一个序列\(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)\)。
题意:这是一道交互题。
有三堆石子,个数分别为\(a,b,c\)。游戏的规则如下:
你可以自行决定当先手还是后手。
\(a,b,c \leq 10^9,k \leq 10^{12}\)。
题解:考虑什么情况下后手无法操作:
因此,这是一个先手必胜的游戏。我们只需要构造一种方案,使它到达这种状态即可。
还是令\(a<b<c\),那么我们先强制让操作后的那对石子个数最大。显然令\(k=c-a\)即可。
现在,上次操作的一定是\(c\),那么我们稍微计算一下,令\(k=2c-a-b\),就能让得到的\(a,b,c\)成为一个等差数列。并且由于\(a+k>c\),所以操作的那堆石子在操作完成后一定是个数最多的。
题意:给定一棵\(n\)个点的树,一次操作,你可以选定三个点\(a,b,c\),要求\(a\)与\(b\)相邻,\(b\)与\(c\)相邻,然后进行如下操作:
你需要最小化操作次数,使得这棵树仅存在一个节点度数为\(n-1\),其他节点的度数都为\(1\)。不需要输出方案。
\(n \leq 2 \times 10^5\)。
题解:由于树无环,我们可以将其看做一个二分图,并将其黑白染色。那么目标状态显然是只有一个黑或白点。考虑一次操作对黑白点个数的影响。我们设\(c\)是黑色的。
对于所有与\(a\)相邻的节点及其子树内的点,颜色不变;只有节点\(a\)的颜色改变了。
因此,一次操作只会使黑或白点个数变化1。那么答案显然就是\(min(cnt_{white},cnt_{black})-1\)。
直接DFS一遍就好了。
原文:https://www.cnblogs.com/Purple-wzy/p/13272864.html