07 2012 档案
hdu 3683 极大极小过程 + 搜索
摘要: 在一个15*15的棋盘上下五子棋。3步之内谁能赢。
阅读全文
posted @
2012-07-30 21:31 西月弦 阅读(309) |
评论 (0) 编辑
hdu 4126 最小生成树 + 树形DP + 优先级队列
摘要: 求N<3,000个点的稠密图的最小生成树的每条边的最佳替换边。
阅读全文
posted @
2012-07-30 13:46 西月弦 阅读(406) |
评论 (0) 编辑
hdu 4305 计算几何 + 高斯消元求行列式 + 逆元
摘要: 平面上有N<300个点。每个两个点如果距离小于R且之间没有共线的另一个点，则这两点之间有一条边。求这个图的生成树的个数mod 10007。
阅读全文
posted @
2012-07-29 22:29 西月弦 阅读(431) |
评论 (0) 编辑
codeforces 212C 递推
摘要: 有一个长度为100的只含A和B的环行串。如果这个串含有AB，那么就变为BA。 给一个串，问有多少种串可以变为这个串。
阅读全文
posted @
2012-07-29 18:41 西月弦 阅读(351) |
评论 (0) 编辑
hdu 3721 树形DP
摘要: 一颗有N个节点(N<2,500)的带权树。现在割去一条边，加到其他节点上，并保证也是一棵树。问最小的直径是多少？
阅读全文
posted @
2012-07-29 14:57 西月弦 阅读(231) |
评论 (3) 编辑
codeforces 204E 后缀数组+线段树
摘要: 给N个串(N<100,000)，总长不超过100,000。对于每个串，求至少在其他k个串中作为子串出现过的子串个数。
阅读全文
posted @
2012-07-26 10:20 西月弦 阅读(753) |
评论 (1) 编辑
codeforces #130 div2
摘要: codeforces #130 div2
阅读全文
posted @
2012-07-24 17:23 西月弦 阅读(300) |
评论 (2) 编辑
hdu 4117 AC自动机 + DP
摘要: 有N(N<20,000)个只含有小写字母的字符串，总长不超过300,000，每个字符串Si有权值Vi。现在让你删除一些字符串，满足对于相邻的串，前一个串是后一个串的子串。求最大权值和。
阅读全文
posted @
2012-07-23 12:52 西月弦 阅读(1338) |
评论 (2) 编辑
codeforces 212B 状态压缩+离散化
摘要: 给一个仅含有小写英文字母的字符串s，(strlen(s)<1,000,000)。询问k次(k<10,000)。每次给出一个字母集合S，问含有且仅含有S集合中的字母的极大子串有多少个？
阅读全文
posted @
2012-07-22 16:18 西月弦 阅读(488) |
评论 (0) 编辑
codeforces 212E 树形DP + 背包
摘要: 题目描述：
一棵N(N<5,000)个节点的树，染两种颜色，不同颜色不能相邻且要给尽可能多的节点染色。求颜色A和颜色B可能的染色节点个数。
阅读全文
posted @
2012-07-21 22:47 西月弦 阅读(285) |
评论 (0) 编辑
codeforces 204D 动态规划
摘要: 有一个长度为n(n<1,000,000)的字符串A。有三种字符，'B','W','X'。现在让你将所有的X要么变成B，要么变成W，构造字符串，使得其存在a<=b
阅读全文
posted @
2012-07-21 19:13 西月弦 阅读(331) |
评论 (0) 编辑
codeforces 200A 并查集
摘要: 给一个大小为n*m(n,m < 2000)的棋盘，有k(K<100,000)次操作。每次在位置（x,y）加入一个点，如果x,y已经有点了，那么加入的点需要满足：
1. 与x,y的曼哈顿距离最近。
2. 如果满足条件1的点有多个，那么要求x最小。
3. 如果满足条件2的点有多个，那么要求y最小。
阅读全文
posted @
2012-07-21 15:02 西月弦 阅读(316) |
评论 (0) 编辑
hdu 4008 树形DP + LCA
摘要: 题目描述：
给一颗结点数为(100,000)的树，最多询问100,000次。每次询问对两个结点X,Y，以X为根，Y的最小标号的孩子，Y的最小标号的后代。
阅读全文
posted @
2012-07-17 10:53 西月弦 阅读(493) |
评论 (0) 编辑
codeforces #129 div1
摘要: codeforces #129 div1
阅读全文
posted @
2012-07-15 22:53 西月弦 阅读(246) |
评论 (0) 编辑
hdu 4125 线段树 + KMP
摘要: 给一个长度为N(N<600,000)的序列，让你按顺序插入静态二叉树。然后DFS出一个序列，问某个模式串在这个序列中出现了几次？
阅读全文
posted @
2012-07-02 15:14 西月弦 阅读(606) |
评论 (0) 编辑