路终会有尽头，但视野总能看到更远的地方。

题目大意

P同学总共有k根火柴，分别放在摆成一列的n个火柴盒内，保证k是n的倍数。P同学想要每个火柴盒都有相同数目的火柴，每次他可以从一个火柴盒中拿一根火柴放到相邻的火柴盒中。他想知道他最少要移动多少次。

题目分析

与【NOIP 2002提高】均分纸牌 几乎相同。
将平均数减掉后从左往右传递差值即可。

题目大意

给出元素$i$在排列$b$中的相对距离（如，与$2$相对距离为$1$的是$1,3$，与$1$相对距离为$2$的是$n-1,3$），求出字典序最小的$b$。

题目分析

显然我们可以建立起二分图模型。
左边的点代表$i$，右边的代表$b$中的元素，$x\rightarrow y$连边代表$b_x$可以为$y$。
然后我们便可以使用匈牙利算法构造出一组可行解。

题目大意

有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为$K$。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。

题目分析

可以修改权值意味着树的形态发生改变，但是无论如何改变，数据值是没有变的，这就意味着中序遍历仍然有序。
我们可以先对数据值进行排序，然后枚举根求解。
发现枚举根后可以转为子问题且具有最优子结构，因此可以考虑使用动态规划解决。

题目大意

葫芦世界有n个葫芦，标号为1~ n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。
小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。

题目大意

小澳最近迷上了考古，他发现秦始皇的兵马俑布局十分有特点，热爱钻研的小澳打算在电脑上还原这个伟大的布局。
他努力钻研，发现秦始皇布置兵马俑是有一定规律的。兵马俑阵总共有n行m列，秦始皇在布置的时候每次会指定一行或一列，然后指定一个兵种，使得这一行或者这一列上全部放上这一个兵种。如果这一行上以前放过其它的兵种，那么他会拔掉以前的兵种改成现在他命令的兵种。
小澳从秦朝的文献中找到了布置这个方阵的操作顺序，他希望你能告诉他布局完成后整个兵马俑阵是什么样子的。

震惊！最小割转对偶图竟然是NOIP初赛考点！
震惊！CCF淘汰Pascal竟然是为了给NOIP初赛埋下伏笔！
震惊！NOIP初赛竟然出现出现复赛原题AC代码！
震惊！NOIP初赛完善程序第一题竟然RE！
震惊！试卷底部竟然是“CCF NOIP2016初赛”！
震惊！CCF竟然提问中华人民共和国于周几成立？

题目大意

给一个$n\times n$的矩阵，有$01$两种颜色，通过交换两行/列的颜色进行变换，询问是否存在一种方案使得矩阵主对角线均为$1$。

题目大意

题目大意

小w心里的火焰就要被熄灭了。
简便起见，假设小 w 的内心是一棵 n - 1 条边，n 个节点的树。
现在你要在每个节点里放一些个灭火器，每个节点可以放任意多个。
接下来每个节点都要被分配给一个至多 k 条边远的灭火器，每个灭火器最多能分配给 s 个节点。
至少要多少个灭火器才能让小 w 彻底死心呢？

题目大意