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