题意：给定一个排列\(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