题目分析

首先题目重点是这句话：

如果课表上一共有 n 个科目，每个科目都有且仅有两节课，小 L 想知道是否存在一个课表，满足这 n 科的两节课间隔的课程数从小到大排序后是一个公差为 1 的等差数列。

换句话说，这句话意思是：

如果给你 2n 个数，分别是 1，1，2，2，…，…，n，n 。对于任意小于等于 n 的数字 k ，将其两次出现的位置记做 i 、j 。 $S_k$ $=j-i+1$ 。要求找到一种排列 2n 个数的方法使得将 $S$ 排序后是一个公差为 1 的等差数列。

解决题目

爆搜大家都会跟枚举全排列差不多，但是 n=100000x+1 这种数据爆搜是不行的，DFS期望得分 $50-$ ，错了别怪我，我没交。

用DFS跑 $n=3$ 之后输出所有结果，如果没错的话，应该有如下的两个可行解：

1 2 3 1 3 2
1 2 3 2 1 3

—— 有什么规律吗？
—— 都是以1 2 3开头。
—— 还有吗？
—— 没了……
—— 把开头的1 2 3去掉，看后面的三个数！
—— 呃……1 3总是在一起，顺序也不变。

$n=5$
以1 2 3 4 5开头的可行结果：

1 2 3 4 5 1 3 5 2 4 
1 2 3 4 5 1 4 2 5 3 
1 2 3 4 5 2 1 5 4 3 
1 2 3 4 5 2 4 1 3 5 
1 2 3 4 5 3 1 4 2 5 
1 2 3 4 5 3 2 1 5 4

其中有

1 2 3 4 5 1 3 5 2 4 
1 2 3 4 5 2 4 1 3 5

满足之前推出来的规律。

等等，为什么是 $n=5$ 而非 $n=4$ 呢？

看题，题目中有

输入仅一行，一个奇数 n，表示课表上的课程数。

所以看题很重要！

用DFS可以跑出 $n=7$ 与 $n=9$ 以及 $n=11$ 可以发现如下规律：

前 n 个数是1，2，…，n。后 n 个数可以是（小于 n 的所有偶数+小于 n 的所有奇数）或（小于 n 的所有奇数+小于 n 的所有偶数）。所有奇偶数均按从小到大排列。

分块就是再DFS可以接受的范围搜索，出了这个范围就用别的方法，例如上面的规律。

这是考场上常用的技巧，可以保证自己再拿到暴力分的基础上可能有更高的分。

数学不好不要慌，暴力规律出奇迹！