[NOIP2013]华容道 首先是一种比较显然的做法。 整个棋盘，除了起点，终点和空格，其他的方块是等价的。 对于终点，它始终不会变化，如果搜到终点结束搜索即可，所以我们不需要考虑终点。 所以需要考虑的是空格的位置和起点方块的位置。 定义$f(i1,j1,i2,j2)$为 空格所在坐标$(i1，j1)$  起点坐标$(i2，j2)$。 对于每一步，可以移动空格周围的一个可移动棋子，将它与空格位置交换。其实等价于空格移动到和空格相邻的棋子。如果该棋子是起点，则将起点更新到原来空格的坐标。 使用bfs，每次步数加一，队列内的状态步数满足单调，第一次得到（区别于dijkstra，不是...

考场上没有认真审题，没有看到该题目的特殊之处： 保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样 的。 于是无论如何也想不到复杂度小于$O(n^3)$的算法， 只好打一个二维前缀和草草了事。 所以还是要仔细审题。   $O(n^2)$算法： 因为每行上只有一个军队，每列上仅有一个军队， 我们发现一个性质，如果记录上每行军队的列数，设h（x）表示第x行军队所在列， 一个$x->y$方案是合法的当且仅当$y-x=max(h(i))-min(h(i))$   $i \in [x,y]$， 枚举左右端点，记录已有的信息即可$O(1)$判断每个区间是否合法。...

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解， 然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是二分图。 行和列是互相区分的两组节点， 如果存在一个1，则可以在它的行列之间连边， 如果最大匹配数为n，该图就存在可行解。 容易想到同一行列上的1的数量一定不会变化， 因为要求在对角线，如果一个1被使用了，它所在的行列就不能再交换到存在1的位置，这些1就废掉了， 所以使用二分图是可行的。...

一颗赛艇 https://www.lydsy.com/JudgeOnline/problem.php?id=4584 虽然名字听起来很暴力（+1s），却是组合计数好题，在考试时都没有看出来是组合计数。   对于子任务1/2 区间的总长度不超过1e6，可以将区间内的每个数离散化到一个区间里。 于是可以写出一个简单的dp， dp（i，j）表示到第i个学校，最多派出划艇数量为j的方案数， 简单的转移。 使用数状数组或线段树优化一下就可以做到O（NlogN）， 最后将答案-1，删去一个划艇都没有的方案即可。     正解 n很小，可以将n个区间的端点离散化， 得到最多2*...

树上染色 https://www.lydsy.com/JudgeOnline/problem.php?id=4033 可怜与超市 http://hzoj.com/contest/62/problem/5 可以简单的列出状态转移方程。 它的转移过程类似： 1 void dfs(int x) 2 { 3 for(unsigned i=0;i<p[x].size();++i) dfs(p[x][i]); 4 int cur=0; 5 memset(tmp[cur],0x3f,sizeof(tmp[cur])); 6 tmp...

记忆的轮廓 题目描述 通往贤者之塔的路上，有许多的危机。我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶子，如果是正确节点则为正确叶子，否则称为错误叶子。莎缇拉要帮助昴到达贤者之塔，因此现在面临着存档位置设定的问题。为了让昴成长为英雄，因此一共只有p次存档的机会，其中1和n必须存档。被莎缇拉设置为要存档的节点称为存档位置。当然不能让昴陷入死循环，所以存档只能在正确节点上进行，而且同一个节点不能存多次档...

集合计数 题目描述 一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~） 输入格式 一行两个整数N,K 输出格式 一行为答案。 样例 样例输入 3 2 样例输出 ...