岁月流风.

摘要： 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4717 每两个点之间的距离变化是一个单峰函数，因为每次求的值最大值，多个单峰函数的最值函数还是单峰的。。 1 //STATUS:C++_AC_515MS_256KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #inc... 阅读全文

摘要： 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4716 直接搞。。 1 //STATUS:C++_AC_0MS_288KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #in... 阅读全文

摘要： 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2686 经典的多进程DP，比较简单。f[x1][y1][x2][y2]表示起点到点(x1,y1)和(x2,y2)的最优值，然后分层转移就可以了，每一层为斜向右的线。。 1 //STATUS:C++_AC_46MS_6172KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12... 阅读全文

摘要： 原来还有如此简单粗暴的办法，当数字比较小(比如10^9)时，我们可以用sqrt函数直接求平方根。但是当数字达到10^20时，sqrt就没用了。此时我们可以用二分来找平方根。但是如果又要精确到小数点后若干位，那么二分也不知道要跑多久。于是我们使用手动开方的算法。首先将数字每两位分成一段。如：745836942。就分成：7|45|83|69|42，即从个位开始分。共分成五段，第一段是7。对第一段的数字7开方取整，可得到2。此时，要在2后面接一个数字b，并在7后面加上下一段的数45，使产生的两位数2b的平方不大于745。我们知道，数是10a+b，其平方是100a^2+20ab+b^2。我们可以暂.. 阅读全文

摘要： 摘自：http://blog.sina.com.cn/s/blog_7a1746820100wp67.html“在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决，实际上，仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。记siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位.. 阅读全文

摘要： 题目链接：http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10857&courseid=55 比赛的时候把题目看成取恰好K个点了，，，悲剧。。然后按照正确的题意的话，是比较好做的，求个凸包，然后DP就可以了，f[i][j][k]表示第 i 个点到第 j 点选择k个点的多边形的最大面积，那么f[i][j][k]=Max{ f[i][j][k], f[i][y][k-1]+area(p[i],p[y],p[j]) }就可以了。。 这题相当悲剧，题目的数据范围描述错了，k应该是小于等于30，因为题目sb， 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29359 题意：一个数列，有三种操作： 1.区间[a,b]之间大于零的数整出c。 2.区间[a,b]之间所有的数减去c。 3.求区间[a,b]的和。 只要注意到每个数最多除lgn次，总共除n*lgn次，那么直接对除法进行单点更新就可了，关键要分析好复杂度。。 1 //STATUS:C++_AC_3020MS_33996KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7... 阅读全文

摘要： 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4283 题意：n个人排队，每个人有一个权值val[i]。从第一个人开始出队，进入一个栈中，每次可以留在栈中或者从栈中移出一个，如果第 i 个人是第k个出栈的，那么有sum+=(k-1)*val[i]，求是的sum最小。 f[i][j]表示区间第 i 个人到第 j 个人sum的最小值，那么每次转移的时候我们只要枚举第 i 个人是什么时候出的栈就可以了，假设第 i 个人是第k个出的栈，那么f[i][j]=Min{f[i+1][i+k-1]+(k-1)*num[i]+f[i+k][j]+k*(su... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=26586 题意：给一个图，每条边有一个权值。要你求选择一棵树，权值和为sum，然后在树上选择一条边权值为w，然后使得sum-2*w最小。 首先求一遍最小生成树，然后求出每两个点之间的最小瓶颈路，然后枚举边就行了。。 1 //STATUS:C++_AC_916MS_30048KB 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=15505 每个h[i]维护两个值l[i]和r[i]，分别表示大于h[i]的左边最远距离和小于h[i]的右边最远距离，DP转一下，然后直接求。。 1 //STATUS:C++_AC_80MS_1360KB 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 typedef long lo... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=26580 题意：给一个模式串，然后m个匹配串，要求删掉匹配串中的所有存在的模式串，使得余下的串中没有模式串。 数据很大，需要O(N)的算法。。。 首先kmp求出模式串的next数组，然后就是kmp匹配了。 但是我们要注意到是要删尽，如BBUGUG，这个样例是删没了的，因此在kmp匹配的时候，对于每个字符 i，我们需要维护两个值 l 和 r，分别表示 i 的左边的有效字符串的下标和右边有效字符串的下标。同时还要维护一个cur[i]数组，表示位置为 i 的字符的next值。然后如... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=26579 考虑两个性质：蚂蚁的相对位置不变，蚂蚁碰撞时相当于对穿而过，然后排两次序就可以了。。 1 //STATUS:C++_AC_204MS_3048KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #inc... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29365 首先排序，然后维护一个后缀，等差求下和就可以了。。 1 //STATUS:C++_AC_2090MS_1716KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29364 题意：给一个序列，输出序列中，二进制1的个数最少的数。。 随便搞搞就行了，关于更多算法，可以看. 1 //STATUS:C++_AC_290MS_1324KB 2 #include 3 #include 4 #include 5 //#include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include... 阅读全文

摘要： 题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29358 状态虽然很多，但是非常稀疏，dfs搜索然后剪下枝。。 或者DP，f[i][j][k]表示前 i 个物品能否到达第一个背包和第二个背包容量分别为 j 和 k 的状态，然后判断第3个背包是否能装下剩下的。f[i][j][k]=f[i-1][j][k] | f[i-1][j-v[i]][k] | f[i-1][j][k-v[i]].. 搜索： 1 //STATUS:C++_AC_10MS_1308KB 2 #include 3 #include 4 #include ... 阅读全文