UOJ460 新年的拯救计划
\(n\) 点完全图。选出尽量多生成树。输出方案。 \(n\le1000\)。
考虑上界，总共有 \(\frac{n(n-1)}{2}\) 条边，也就是最多可以分成 \(\frac{n}{2}\) 棵树。
尝试证明这个上界可以达到。我们考虑归纳法，假设 \(n = 2k\) 可行。
考虑 \(2k + 1\)，我们可以将每棵生成树选一个不同的点连向 \(2k + 1\)，考虑到只有 \(k\) 棵，显然是够的。
考虑 \(2k + 2\)，由 \(1 \sim k\) 连向 \(2k + 1\)，\(k + 1 \sim 2k\) 连向 \(2k + 2\)，然后再加一棵生成树，由 \(1 \sim k\) 连向 \(2k + 2\) 和 \(k + 1 \sim 2k\) 连向 \(2k + 1\)，同时连 \(2k + 1\) 和 \(2k + 2\)。
这是一个构造的方法。这题就完了。
CF1558C Bottom-Tier Reversals
首先观察性质：位置的奇偶性不会改变，所以如果一开始奇偶性就错了肯定不行。
接着我们需要确定一个大体思路，如何做排序？由于是对前缀操作，我们考虑倒着往前一步步还原。
所以我们现在先考虑如何把最后两个变成 \(n - 1, n\)，观察最终的长度约束，如果我们能在 5 步内完成，那么这个问题就解决了。
第一步：找到 \(n\)，使其变成第一个。
第二步：找到 \(n-1\)，使 \(n\) 变成 \(n-1\) 前面的元素。
第三步：翻转使得 \(n-1\) 第二个，\(n\) 第三个。
第四步：翻转使得 \(n\) 第一个，\(n-1\) 第二个。
第五步：翻转使得 \(n\) 最后，\(n-1\) 倒数第二。
然后就顺利解决了这道题。
P6892 [ICPC2014 WF] Baggage
神仙构造。
首先看到这种题肯定是要手玩小数据并且猜下界，根据样例不难猜出下界是 \(n\)。
证明下界分两步，首先是证明不存在更小的，其次是构造一个。
我们先考虑证明不存在更小的，观察题目的性质发现，如果我们记相邻两个位置相同的个数为 \(\phi\)，则我们从 \(0 \to 2n-1\)，由于每次最多新增两个且第一次最多新增一个，所以至少 \(n\) 次。
根据这个，我们可以手玩出 \(n = 4\) 的情况：
\[..BABABABA\\ ABBABAB..A\\ ABBA..BBAA\\ A..ABBBBAA\\ AAAABBBB..\\ \]进一步，我们尝试去归纳 \(n\) 更大的情况，我们发现可以这样做：
\[..BABA [(n-4) \times BA] BABA\\ ABBABA [(n-4) \times BA] B..A\\ ABBA.. [(n-4) \times BA] BBAA\\ ABBA[(n-4) \times A + (n-4)\times B]..BBAA\\ A..A[(n-4) \times A + (n-4)\times B]BBBBAA\\ AAAA[(n-4) \times A + (n-4)\times B]BBBB..\\ \]刚好 \(n\) 次，但是这里要求存在使得只往前移两位的方法，所以 \(n-4 \ge 4\)，意味着我们需要自己手玩 \(n = 3,4,5,6,7\) 的情况。
标签：..,连向,构造,times,笔记,我们,sim,2k From： https://www.cnblogs.com/rlc202204/p/18334392