解题报告
【奋战2013regional】 hdu 1662 计算几何
摘要: 给出一个“一笔画”轨迹，没有线段重叠。求这个轨迹将平面分成了几部分。
阅读全文
posted @
2013-05-06 14:07 西月弦 阅读(295) |
评论 (0) 编辑
uva 12583 可持久化treap
摘要: 对一个字符串S(初始为空)，有Q次操作(Q<=50,000)，操作分三种：
1. 在某个位置p后面插入一个长度不大于100的字符串。
2. 删除一段字符[l,r]
3. 输出在第k次操作时，字符串(S_l ... S_r) 插入的字符不超过1,000,000个。
阅读全文
posted @
2013-03-19 22:15 西月弦 阅读(1565) |
评论 (1) 编辑
动态规划求解背包类问题(更新中...)
摘要: 我理解的背包类问题，大概有两类：
(1) 在N组物品中，挑选出M个，使得某些性质最优。
(2) 在N组物品中，挑选出M个，求并符合某条件的方案数。
阅读全文
posted @
2012-12-03 13:40 西月弦 阅读(430) |
评论 (0) 编辑
codeforces 145C DP+数论
摘要: 给长度为n的数列，(n<1e5)。让你求选择没有相同的lucky number的子序列的方法数 mod 1e9+7。
阅读全文
posted @
2012-11-30 18:39 西月弦 阅读(448) |
评论 (0) 编辑
topcoder srm 561 div1
摘要: topcoder srm 561 div1
阅读全文
posted @
2012-11-21 16:02 西月弦 阅读(501) |
评论 (3) 编辑
2012亚洲区成都现场赛原创题解
摘要: 2012亚洲区成都现场赛原创题解
阅读全文
posted @
2012-11-17 23:04 西月弦 阅读(1120) |
评论 (6) 编辑
codeforces #148 (坑。。)
摘要: codeforces #148 (坑。。)
阅读全文
posted @
2012-11-05 20:25 西月弦 阅读(423) |
评论 (0) 编辑
2012天津赛区原创题解
摘要: 题目连接
http://acm.hdu.edu.cn/search.php?field=problem&key=2012%20Asia%20Tianjin%20Regional%20Contest&source=1&searchmode=source
阅读全文
posted @
2012-10-30 00:07 西月弦 阅读(998) |
评论 (8) 编辑
codeforces #147 div2
摘要: codeforces #147 div2
阅读全文
posted @
2012-10-28 16:01 西月弦 阅读(404) |
评论 (3) 编辑
poj 3415 SAM
摘要: 询问两个长度为100,000的字符串，不小于k的公共子串有多少个。
阅读全文
posted @
2012-10-25 19:23 西月弦 阅读(554) |
评论 (0) 编辑
topcoder srm 558 div1
摘要: topcoder srm 558 div1
阅读全文
posted @
2012-10-24 16:22 西月弦 阅读(232) |
评论 (0) 编辑
codeforces #146 div1
摘要: codeforces #146 div1
阅读全文
posted @
2012-10-24 14:13 西月弦 阅读(540) |
评论 (2) 编辑
topcoder srm 557 div1
摘要: topcoder srm 557 div1
阅读全文
posted @
2012-10-18 14:00 西月弦 阅读(439) |
评论 (0) 编辑
codeforces #145
摘要: codeforces #145
阅读全文
posted @
2012-10-17 13:47 西月弦 阅读(606) |
评论 (1) 编辑
poj 2949 spfa求正环
摘要: 题目描述：
有N个串，两个尾首两个字母相同的串可以连接。求最大均值圈。
阅读全文
posted @
2012-10-10 19:32 西月弦 阅读(294) |
评论 (0) 编辑
fzu 2042 数位DP
摘要: 题目描述：
给出五个数（不超过2^63-1），让你求下面代码的sum值
for(ll i = a; i <= b; i++)
for(ll j = c; j<= d; j++)
if((i ^ j) > e)
sum += i^j;
阅读全文
posted @
2012-10-10 14:56 西月弦 阅读(419) |
评论 (0) 编辑
codeforces #139
摘要: codeforces #139
阅读全文
posted @
2012-10-08 15:00 西月弦 阅读(216) |
评论 (0) 编辑
codeforces #140
摘要: codeforces #140
阅读全文
posted @
2012-10-07 16:10 西月弦 阅读(535) |
评论 (10) 编辑
codeforces #141
摘要: codeforces #141
阅读全文
posted @
2012-10-04 00:51 西月弦 阅读(259) |
评论 (0) 编辑
codeforces #142
摘要: codeforces #142
阅读全文
posted @
2012-10-03 14:47 西月弦 阅读(377) |
评论 (0) 编辑
topcoder srm 555 div1 [pratice]
摘要: topcoder srm 555 div1 [pratice]
阅读全文
posted @
2012-10-02 23:42 西月弦 阅读(247) |
评论 (0) 编辑
codeforces #137 div2
摘要: codeforces #137 div2
阅读全文
posted @
2012-09-11 21:39 西月弦 阅读(369) |
评论 (3) 编辑
hdu 4285 插头DP
摘要: 求12×12矩阵上的互不嵌套的k个哈密顿回路的方案数。
阅读全文
posted @
2012-09-10 21:09 西月弦 阅读(1121) |
评论 (5) 编辑
zoj 1063 广搜
摘要: 狗狗四十题第六题
阅读全文
posted @
2012-09-10 11:33 西月弦 阅读(221) |
评论 (0) 编辑
zoj 1021 递归
摘要: 狗狗四十题第一题
阅读全文
posted @
2012-09-03 19:58 西月弦 阅读(291) |
评论 (0) 编辑
codeforces #136 div1
摘要: codeforces #136 div1
阅读全文
posted @
2012-09-01 12:57 西月弦 阅读(593) |
评论 (7) 编辑
topcoder srm 552 div1 比赛小记
摘要: topcoder srm 552 div1 比赛小记
阅读全文
posted @
2012-08-17 13:17 西月弦 阅读(387) |
评论 (1) 编辑
hdu 4127 迭代加深搜索
摘要: 玩flood-it游戏, 一个8*8的带6种颜色的格子. 每次占领与已占领的联通块相邻的联通块, 问最少几次可以全部占领完. 第一次占领左上角.
阅读全文
posted @
2012-08-15 20:56 西月弦 阅读(410) |
评论 (0) 编辑
codeforces #133 div2
摘要: codeforces #133 div2
阅读全文
posted @
2012-08-15 16:25 西月弦 阅读(262) |
评论 (0) 编辑
codeforces 213E 多项式哈希+线段树
摘要: 给两个长度为200,000的全排列a,b. 寻找整数k的个数,使a的每个数加上k以后,是b的子序列.
阅读全文
posted @
2012-08-10 22:54 西月弦 阅读(463) |
评论 (0) 编辑
codeforces #132 div2
摘要: codeforces #132 div2
阅读全文
posted @
2012-08-10 10:42 西月弦 阅读(330) |
评论 (0) 编辑
codeforces 213D 计算几何
摘要: 要求一笔划画出N(N<100)个五角形，输出方案(画的轨迹)。
阅读全文
posted @
2012-08-06 22:25 西月弦 阅读(279) |
评论 (0) 编辑
hdu 4116 计算几何 + 扫描线
摘要: 在无限平面上有N(N<1,000)个圆。问一条直线最多可以“穿过”几个圆，相切也算。
阅读全文
posted @
2012-08-06 14:58 西月弦 阅读(1238) |
评论 (0) 编辑
codeforces 212D 线段树 + 栈的应用
摘要: 给1,000,000个数，大小不超过10^9。询问1,000,000次，长度为k的区间最小值的期望。
阅读全文
posted @
2012-08-05 19:57 西月弦 阅读(326) |
评论 (0) 编辑
hdu 3712 计算几何
摘要: 给一个点光源(x0,y0)，向(x1,y1)处发射射线。p0,p1,p2三个点是三棱镜，折射率为n。求最后光线与x轴的交点。
阅读全文
posted @
2012-08-05 14:35 西月弦 阅读(460) |
评论 (0) 编辑
hdu 4060 二分图最小点覆盖
摘要: 由于题目描述过于imba，这里直接给出链接吧
http://acm.hdu.edu.cn/showproblem.php?pid=4060
阅读全文
posted @
2012-08-04 06:14 西月弦 阅读(367) |
评论 (0) 编辑
hdu 3694 计算几何
摘要: 求四个点的费马点与这四个点的距离和。
阅读全文
posted @
2012-08-03 16:26 西月弦 阅读(180) |
评论 (0) 编辑
codeforces #131 div1
摘要: codeforces #131 div1
阅读全文
posted @
2012-08-03 15:36 西月弦 阅读(269) |
评论 (0) 编辑
hdu 3683 极大极小过程 + 搜索
摘要: 在一个15*15的棋盘上下五子棋。3步之内谁能赢。
阅读全文
posted @
2012-07-30 21:31 西月弦 阅读(303) |
评论 (0) 编辑
hdu 4126 最小生成树 + 树形DP + 优先级队列
摘要: 求N<3,000个点的稠密图的最小生成树的每条边的最佳替换边。
阅读全文
posted @
2012-07-30 13:46 西月弦 阅读(403) |
评论 (0) 编辑
hdu 4305 计算几何 + 高斯消元求行列式 + 逆元
摘要: 平面上有N<300个点。每个两个点如果距离小于R且之间没有共线的另一个点，则这两点之间有一条边。求这个图的生成树的个数mod 10007。
阅读全文
posted @
2012-07-29 22:29 西月弦 阅读(421) |
评论 (0) 编辑
codeforces 212C 递推
摘要: 有一个长度为100的只含A和B的环行串。如果这个串含有AB，那么就变为BA。 给一个串，问有多少种串可以变为这个串。
阅读全文
posted @
2012-07-29 18:41 西月弦 阅读(328) |
评论 (0) 编辑
codeforces 204E 后缀数组+线段树
摘要: 给N个串(N<100,000)，总长不超过100,000。对于每个串，求至少在其他k个串中作为子串出现过的子串个数。
阅读全文
posted @
2012-07-26 10:20 西月弦 阅读(737) |
评论 (1) 编辑
codeforces #130 div2
摘要: codeforces #130 div2
阅读全文
posted @
2012-07-24 17:23 西月弦 阅读(294) |
评论 (2) 编辑
hdu 4117 AC自动机 + DP
摘要: 有N(N<20,000)个只含有小写字母的字符串，总长不超过300,000，每个字符串Si有权值Vi。现在让你删除一些字符串，满足对于相邻的串，前一个串是后一个串的子串。求最大权值和。
阅读全文
posted @
2012-07-23 12:52 西月弦 阅读(1334) |
评论 (2) 编辑
codeforces 212E 树形DP + 背包
摘要: 题目描述：
一棵N(N<5,000)个节点的树，染两种颜色，不同颜色不能相邻且要给尽可能多的节点染色。求颜色A和颜色B可能的染色节点个数。
阅读全文
posted @
2012-07-21 22:47 西月弦 阅读(279) |
评论 (0) 编辑
codeforces 204D 动态规划
摘要: 有一个长度为n(n<1,000,000)的字符串A。有三种字符，'B','W','X'。现在让你将所有的X要么变成B，要么变成W，构造字符串，使得其存在a<=b
阅读全文
posted @
2012-07-21 19:13 西月弦 阅读(328) |
评论 (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 西月弦 阅读(313) |
评论 (0) 编辑
hdu 4008 树形DP + LCA
摘要: 题目描述：
给一颗结点数为(100,000)的树，最多询问100,000次。每次询问对两个结点X,Y，以X为根，Y的最小标号的孩子，Y的最小标号的后代。
阅读全文
posted @
2012-07-17 10:53 西月弦 阅读(487) |
评论 (0) 编辑
codeforces #127 div1
摘要: codeforces #127 div1
阅读全文
posted @
2012-06-30 02:49 西月弦 阅读(532) |
评论 (0) 编辑
hdu 4087 仿射几何 + 矩阵乘法
摘要: 定义一种变换向量的语言，其语法有这么几种：
1. translate tx ty tz 功能：(x,y,z) = (x+tx,y+ty,z+tz)
2. scale a b c 功能：(x,y,z) = (ax,by,cz)
3. rotate tx ty tz angle 功能：让x,y,z以tx,ty,tz为轴逆时针旋转angle。
4. rotate k .... end 功能： 重复执行...k次
给若干个向量，输出对应的变换后的向量。
阅读全文
posted @
2012-06-24 16:01 西月弦 阅读(403) |
评论 (1) 编辑
codeforces 198C 二分答案 + 计算几何
摘要: 有个星球起始位置是（xp,yp），绕原点以速度Vp做匀速圆周运动。不明物体起始位置（x,y），速度为V(V>Vp)。这个物体可以随意移动，但是任何时刻与原点的距离不能小于r。请问这个物体想要与星球位置重合的最少时间是多少？
阅读全文
posted @
2012-06-23 19:26 西月弦 阅读(483) |
评论 (0) 编辑
hdu 3727 主席树+ 线段树
摘要: 对一个序列进行维护，要求支持四种操作：
1. 在结尾加入一个数。
2. 询问区间第K大的数
3. 询问大小为X的数在序列中的排名
4. 询问第K大的数
阅读全文
posted @
2012-06-21 15:47 西月弦 阅读(1119) |
评论 (4) 编辑
bzoj 2653 二分枚举 + 可持久化线段树
摘要: 给长度为20000的序列。求左端点在[a,b]和右端点在[c,d]中所有的子序列，最大的中位数。
阅读全文
posted @
2012-06-20 16:44 西月弦 阅读(1231) |
评论 (5) 编辑
hdu 1828 线段树求矩形周长并
摘要: 给N(N<5000)个矩形，求周长并。
阅读全文
posted @
2012-06-04 20:54 西月弦 阅读(444) |
评论 (0) 编辑
2012 黑龙江省赛简要题解
摘要: 2012黑龙江省赛简要题解(不断更新)
阅读全文
posted @
2012-05-30 10:33 西月弦 阅读(321) |
评论 (0) 编辑
poj 2831 次小生成树 or 树链剖分
摘要: 给一个点数为N(N<1,000)的图,Q次询问. 每次询问如果第i条边的值变为v, 这条边是否可能会在最小生成树中.
阅读全文
posted @
2012-05-20 15:22 西月弦 阅读(494) |
评论 (0) 编辑
bzoj 2243 树链剖分+线段树
摘要: 在一颗点数为N<100,000的树上，每个点有一个颜色。请你实现两种操作 1. 给一段路径u->v染色 2. 询问路径u->v上有多少种颜色
阅读全文
posted @
2012-05-16 17:10 西月弦 阅读(855) |
评论 (1) 编辑
spoj 375 树链剖分+LCA+RMQ(zkw线段树)
摘要: 在一个点数为N(N<10,000)的带权树上，支持两个操作：1. 改变一个边权 2. 询问u和v之间的路径上的最大边权
阅读全文
posted @
2012-05-14 22:17 西月弦 阅读(803) |
评论 (2) 编辑
poj 3580 splay(重口味)
摘要: 给一个长度为N(N<10,000)的数列，要求支持6种操作： 1. 将区间[l,r]同时加一个数 2. 将区间[l,r]翻转 3.将区间[l,r]旋转若干次 4. 插入一个数 5. 删除一个数 6.求[l,r]的最小值
阅读全文
posted @
2012-05-12 23:48 西月弦 阅读(600) |
评论 (0) 编辑
hdu 1890 splay + 懒惰标记
摘要: 给一个长度为N(N<10,000)的数列，每次选取值最小的元素并翻转前面的数列，然后删除这个元素。请在每次操作之前输出这个最小元素的位置。
阅读全文
posted @
2012-05-10 20:54 西月弦 阅读(1151) |
评论 (0) 编辑
hdu 4052 线段树+扫描线
摘要: 10^7 * 10^7 的平面上有N(N<50,000)个不相交的矩形。要在这个平面上放置一个长度为M(M<1,000)的线段，有多少种方法
阅读全文
posted @
2012-05-09 22:20 西月弦 阅读(518) |
评论 (0) 编辑
poj 3225 线段树(zkw版)+ 懒惰标记
摘要: 定义区间的交，并，差操作。假设当前坐标轴区间集合为S(开始为空)，给大量的询问，格式为 命令+区间T，命令'I'代表S = S交T，'U'代表并，D和C代表S=S-T和S=T-S，S代表S=S-T并T-S。输出最后的区间集合S。
阅读全文
posted @
2012-05-07 20:21 西月弦 阅读(1617) |
评论 (0) 编辑
hdu 3605 二分图的多重匹配(匈牙利算法)
摘要: 有N(N<100,000)个人要去M(M<10)个星球，每个人只可以去一些星球，一个星球最多容纳Ki个人。请问是否所有人都可以选择自己的星球...
阅读全文
posted @
2012-05-06 14:20 西月弦 阅读(1509) |
评论 (0) 编辑
poj 1182 并查集
摘要: 有三个物种 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 给出N(N<50000)个生物，给出X(X<100000)个定论，请问X个定论中有多少是谎话？
阅读全文
posted @
2012-05-06 02:28 西月弦 阅读(373) |
评论 (7) 编辑
hdu 3603 二分+RMQ
摘要: 给一个长度不超过1,000,000的数列S。询问Q(Q<100,000)次，在区间[l,r]里，查询最长的元素互不相同的字串的长度。
阅读全文
posted @
2012-05-04 22:59 西月弦 阅读(226) |
评论 (0) 编辑
poj 1061 求模线性方程的最小整数解
摘要: 在一个长度为L的环上的有两点x,y。点A的速度是m，点B的速度是n。请问二者相遇的最小整数时间。保证m,n,x,y,l都是int型正整数。
阅读全文
posted @
2012-05-04 11:20 西月弦 阅读(441) |
评论 (0) 编辑
poj 2528 线段树+离散化
摘要: N(N<10000)多线段[l,r](1<=l<=r<=1,000,000,000)相互覆盖，每个线段颜色不同，请问最后有多少种颜色?
阅读全文
posted @
2012-05-03 19:21 西月弦 阅读(530) |
评论 (0) 编辑
hdu 3068 Manacher算法
摘要: 求一个字符串的最长回文串。串长度小于110,000。
阅读全文
posted @
2012-05-02 21:26 西月弦 阅读(511) |
评论 (0) 编辑
poj 1741 树形DP+分治+排序+容斥原理
摘要: 给你一个N(N<10000)个点的有权树，请问距离不超过K(K<1,000,000,000)的点对有多少个?
阅读全文
posted @
2012-05-02 16:58 西月弦 阅读(454) |
评论 (0) 编辑
bzoj 1503 平衡树(splay)
摘要: 用一个数据结构来统计员工，有四种操作 1. 加入一个初始工资为A的员工 2. 将所有人工资提高一个数 3. 将所有人工资降低一个数 4. 询问第K多工资的员工是谁。 其间一点某人的工资低于工资下限，就会立刻离开公司...
阅读全文
posted @
2012-05-01 19:52 西月弦 阅读(1621) |
评论 (1) 编辑
hdu 4056 线段覆盖+并查集优化
摘要: 在一个N*M(N<=200,M<=50000)像素的画板上画Q(Q<=50000)个图形，有矩形，圆形，倒等腰三角形，菱形四种，每个图形有九种颜色可选择。对于一个像素，后画的颜色会覆盖前面的颜色，请求出最后每种颜色的像素有多少个？
阅读全文
posted @
2012-04-30 17:38 西月弦 阅读(483) |
评论 (0) 编辑
codeforces 11D 基于路径的动态规划+bitmask
摘要: 请问在点数为V(V<20)的无向图中，长度不小于3的简单回路有多少个？(保证结果可以用long long表示， 且图中无自环或者重边)
阅读全文
posted @
2012-04-29 22:14 西月弦 阅读(875) |
评论 (0) 编辑
hdu 3980 组合博弈+动态规划+SG函数
摘要: 给一个长度为 N<1000 的环。A和B两个人每次在这个链上选一段长度为 M<1000 的未染色区间进行染色。直到某人不能进行此操作时判此人负。假设两人都足够聪明，请你判断谁会取得胜利？
阅读全文
posted @
2012-04-28 23:14 西月弦 阅读(419) |
评论 (0) 编辑
hdu 4200 高斯消元法 + 枚举
摘要: N(N<100)个带开关的灯泡排成一行，每个灯泡的开关可以转换自己，左边连续D个和右边连续D个灯泡的开关状态。现在给你每个灯泡的初始状态{Ai}，请问最少开关多少次能把所有的灯熄灭？
阅读全文
posted @
2012-04-27 18:26 西月弦 阅读(600) |
评论 (0) 编辑
hdu 4123 树形动态规划+二分+单调队列
摘要: 给出一个N个点的带权树(N <= 50000)。每个点到任意叶子节点的最长距离记为Di。询问M < 300次，对每次询问，找到长度最大的区间[l,r]，使得Di(l<=i<=r)的最大值和最小值的差不超过Q。
阅读全文
posted @
2012-04-26 16:42 西月弦 阅读(443) |
评论 (0) 编辑
zoj 3541 基于区间的动态规划
摘要: N个按钮在一条直线上排列，给出每个按钮的坐标(Xi,0)。每个按钮按下之后在Ti秒之后马上弹起，你一开始在最左端的按钮上，每移动1个单位长度需要1秒钟。
请问你能否在某一时刻使所有按钮都是按下的。如果可以输出任一方案。
阅读全文
posted @
2012-04-25 12:01 西月弦 阅读(918) |
评论 (0) 编辑
hdu 4114 动态规划+bitmask+最短路
摘要: 给一个点数为N(N<50)的带权无向图。其中有K个景点，参观每个景点有一个代价 Ti。有一些地方可以获得一些景点的票，如果持票参观景点i则代价为 FTi。 保证K<=8，FTi <= Ti。 请问从景点1出发,参观全部的景点，再回到景点1的最小代价是多少。路的权也计算在代价中。
阅读全文
posted @
2012-04-24 20:11 西月弦 阅读(1804) |
评论 (0) 编辑
hdu 2829 动态规划+斜率优化
摘要: 给你一个序列A，请你把序列A分成连续K个子段，每个子段的代价是 sum(A[i]*A[j]) 其中 i < j。请问如何分组使代价最小。
数据范围|A|,K <100
阅读全文
posted @
2012-04-24 14:51 西月弦 阅读(913) |
评论 (3) 编辑