Also available: UVALive 6588, UVA 1611, Gym 100299C

题意

给出 n 个数，每次可以选一个偶数长度的区间，将区间前半部分和后半部分的元素交换。要求最终交换成 1, 2, 3, ..., n 的排列，输出交换步骤，且总次数要小于 531441。

Also available: UVALive 6582, UVA 1642, Gym 100299C

题意

给定一个序列，定义一个连续子序列的 Magical GCD 为子序列内所有元素的 GCD 乘上区间长度，求最大的 Magical GCD。

比赛 ID: 2015

注：本题解参考代码均为 C++ 代码，如果你是 C 使用者，出现不认识的头文件时，若是 c 开头的，一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件，如 cstdio 在 C 中为 stdio.h ，其他的请自行搜索。另外，如果出现不认识的写法，如 sort（排序） 、 stack（栈） 等，请自行实现。

比赛 ID: 2016

注：本题解参考代码均为 C++ 代码，如果你是 C 使用者，出现不认识的头文件时，若是 c 开头的，一般可以通过去掉开头的 c 然后在末尾添加 .h 来转换成 C 的头文件，如 cstdio 在 C 中为 stdio.h ，其他的请自行搜索。另外，如果出现不认识的写法，如 sort（排序） 、 stack（栈） 等，请自行实现。

解题思路

不难想到用 $dp[i][j]$ 表示放第 $i$ 个题时趣味值为 $j$ 的方案数，然而有一个问题是不好表示前面 $i-1$ 个都选了哪些。因此这里需要用状态压缩 DP（一看题目数量那么小就应该试图往状压那边想了），把我们的 dp 数组中的第一维表示为一种题目选择方案（按二进制压缩成一个数存储），然后就很容易写出转移方程（其中 $i$ 表示当前遍历到的状态，$j$ 和 $k$ 分别为 $[1, n]$ 及 $[0, m]$ 的循环，$cnt$ 为当前状态下的已选题目数量）：

$$dp[i+2^{j-1}][min(k+a[cnt+1][j], m)] += dp[i][k]$$