给出一个无向图，求最少点覆盖

(太难了，以后补

继续阅读 →

给出一棵树，每个结点有一个权值，求k条路径使权值和最大，一个结点经过多次只能算一次

贪心 + 两次dfs。开始感觉费用流能过，一直坚信费用流的玄学复杂度是O(m)的!，结果一直TLE…

继续阅读 →

dir[i][j]表示’0’的位置在i的时候，可以和谁换，先把每个状态之间的转换预处理出来，然后就可以BFS了 [学会这题就可以做15北京网赛的那个Boxes了

Accepted    1320K    94MS    G++    1363B

继续阅读 →

有n个盘子，大小分别是1-n，现在给出他们的一个排列，求移动成顺序(1,2,3,4…n)最少需要多少步。移动的规则是每次只能移动一个盘子，小的盘子可以放在大的盘子上

没做过这种bfs，不知道怎么从一种状态往其他状态扩展 = =!

用一个数组state记录每个第i个的盘子放置的位置，那么可以先从state[1][2][3][4][5][6][7]搜出所有结果，然后O(1)查询，因为不知道会有几个盘子，所以要BFS7次（n = 1 和 n = 2的时候可以特判）

继续阅读 →

给出一棵N个结点，M条边的以1为根的树，树的每个结点保存一个字母。接下来给出M个询问，每次询问有两个值v，h，即结点v的所有深度为h的儿子能否组成一个回文串

在线：dfs一次，把深度相同的字符相同的点放到一个vector中，查询的时候查从’a’到’z’每个字符的数目，最多只能有一种字符是奇数个。若某个字符B是A的子结点满足：pre[B] > pre[A] && post[B] < post[A]      时间复杂度：O(26nlogn)

代码：

继续阅读 →

给出一个二维平面和起点S，终点T的坐标(sx, sy),  (tx, ty)，并给出m个移动的方向，求从S到T的最小移动次数或IMPOSSIBLE

 剪枝很神！每次算S到当前点的向量与S到T的向量构成的平行四边形的面积，与点的最大活动范围比较，如果大于，那么当前点就是不合法的。最大活动范围是ST的距离乘上一次点能移动的最大距离。

代码

继续阅读 →

给出n个结点的一棵树，每个结点一个编号，要求同一个结点的字节点标号连续，这棵树的每棵子树的标号连续，求有多少种方案。

每个节点的非叶子儿子结点不会超过两个，而叶子儿子节点的排列可能有K！种，如果有小于两个非叶子儿子节点，则总贡献为2*K！种

代码：

继续阅读 →

给出一个有向图，求最少去掉多少个点使的从S到T的最短距离大于K

如果问从S到T最少去掉多少条边使ST不连通，那么这就是个最小割的问题

把每个点拆成两个，连一条费用为0，流量为1的边，其余相连的两点连一条费用为1，流量为1的边。则每条增广路的费用为S-T的路长，S-T的费用大于K时停止增广，此时的最大流即为此图的最小割边数，原图的最小割点数

然而上面的想法是错的…

正解：枚举删除的点

继续阅读 →