- 博客(36)
- 收藏
- 关注
RSS订阅原创 coderforces 335B--Palindrome [字符串好题]
给出一个字符串s（长度小于50000），从中找出一个长度不超过100但尽可能长的回文子串（这里的子串不一定要连续的），任意输出一个即可。codeforces的题目都有标签，这题不例外有个DP，便一开始就往这方面想。首先回文一定要左右“对称”，那么如果做动态规划，那么必须左右同时进行。一开始想记f（i，j）为i到j这个区间的最长回文串，但就是空间就已经超了。看到题目中找的最长只是100，能不能记其他
2014-04-06 13:05:08
718
原创 1D/1D动态规划优化初步 模型一
今天看了一篇很不错的文章——《1D/1D动态规划优化初步》，其中的模型一我觉得十分常见和实用，就拿“玩具装箱”这题做了一下。这题的确很经典，做过不少动态规划的题目都见过这个模型。根据文章的介绍，能够用这种优化的，需要满足决策单调性。设w（x）为f（x）所枚举的最优决策是多少，所谓的决策单调性需要满足：当i 有了这个，如果只是单纯地在枚举时的i从w（x-1）到x-1，这必然作用不大，不能起到实际效果
2014-04-06 13:05:06
1991
原创 poj 1738--石子合并 [GarsiaWachs算法]
石子合并算是一道比较经典的题目了，这里讨论一下朴素的动态规划和GarsiaWachs算法。最简单的就区间动态规划了。设f(i, j)（i （需要枚举一个p）以区间长度为阶段，时间复杂度为三次方的。一个对决策的优化，可以把转移优化为O（1）的。设g(i, j)为f(i, j)枚举的决策最优的p，那么显然有：这样子枚举的p的范围就大大缩小了，p的取值范围是比较小的，只有一两个左右。然而，该算法的时间和
2014-04-06 13:05:01
1270
原创 AC自动机的失败指针树
AC自动机在询问时都要沿着失败指针走一遍，这是非常耗时的，从而可以把每个结点沿失败指针走一次的结果保存下来，那么就能省不少时间。 如图，是已经建立好的AC自动机，点1是根，紫色的是失败指针。若匹配到点7，需要沿着7->2->1把所有的单词数量加起来。如果事先就把结果sum放在点7，就可以省时了。那么当某些点的单词数量发生变化时，假设点2的单词数量加1，那么点2,6,7的sum都要加1，这还是比较慢
2014-04-06 13:04:57
1476
原创 土地购买 [DP斜率优化]
经典的题目，土地购买：Farmer John需要买下n（≤50000）块长方形的土地，每块的花费就是长宽之积（就是面积）。他可以一次买多块土地，价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换。问Farmer John在合理分组购买土地下，最少需要的花费。首先，如果一块土地被另一土地包含（比如5*10的土地包含4*6的土地），那么这块土地就不用考虑了，从数据中去掉。然后按土地的宽度排序
2014-04-06 13:04:47
987
原创 poj 1236--Network of Schools [强连通分量]
#include #include #include using namespace std;const int N = 107;int n;bool edge[N][N];void Init(){ scanf("%d\n", &n); for (int i = 0; i n; i ++) { int t; scanf("%d", &t);
2014-04-06 13:04:36
479
原创 图的探索 强连通分量的相关概念
在了解这个前，先得明确一下定义：割点（也作“关节点”）：如果在图G中去掉一个顶点(自然同时去掉与该顶点相关联的所有边)后图的连通分支数增加，则称该顶点为G的割点。割边（也作“桥”、"关节边"）：假设有连通图G，e是其中一条边，如果G去掉（删去）e后是不连通的，则边e是图G的一条割边。强连通图：有向图 G=(V,E) 中，若对于V中任意两个不同的顶点 x 和 y ，都存在从x 到 y 以及从 y 到
2014-04-06 13:04:33
680
原创 ioi 2005--河流 [左儿子右兄弟]
有一棵树（结点数≤100），在根有一个伐木场，每个结点都有若干木头，每条边都有个距离，所有的木头都要往上运，运过一条边的代价为木头数量乘以边的长度。现在可以在某些结点新建k（≤100）个伐木场，建立伐木场后，木头就不一定要运到根了，可以直接运到新的伐木场。问在合理建设伐木场下，最小的代价是多少。这很容易想到树形的动态规划，设f(i, j)为这以i为根的子树新建j个伐木场的最小代价。可是如何转移呢？
2014-04-06 13:04:31
1156
原创 poj 1273--Drainage Ditches [网络流dinic算法]
#include #include #include using namespace std;const int N = 207;const int M = 207;int n, m, nedge;int from[N], to[M 1], next[M 1], cap[M 1];int pre[N];void Insert(int a, int b, int c){ to[nedge
2014-04-06 13:04:24
545
原创 GDKOI 2012--mmm含树
这是今年GDKOI的一题：有一棵树，开始时所有结点的值都是0。有多个操作，每个操作有两种：1.对某个点增加w，设dis（i，j）为点i到点j的最短距离，那么某个结点增加w时，对于任意一个结点j，它的值会增加w + dis（i，j）。2.询问某点的值。w可以忽略，因为整棵树都要加上w，只要记下所有w的和就可以了，输出答案时再加上。这题的突破口就是只需要求一个点的值，这就取决于其他发生变化的点对该点的
2014-04-06 13:04:19
621
原创 spoj 375--Query On a Tree [树链剖分]
贴个qtree的代码：#include #include using namespace std;// 读入优化inline int getInt(){ int res = 0; char ch; for (ch = '#'; ch '0' || ch > '9'; ch = getchar()); for (; ch >= '0' && ch '9'; ch = ge
2014-04-06 13:04:17
471
原创 探究 树链剖分
链可以看做是一种特殊的树，当一棵树退化成了链，某些问题就变得容易解决，也有很多数据结构支持这样那样的操作，线段树就是其中一种。从而我们可以想象，能否把一棵树也分成很多条链，从而来解决一些问题呢？这就有了树链剖分。形象点说，树链剖分就是把一棵树分成多条链（称为“重链”），链与链之间有一些边相连，当操作在链上时，可以用线段树来维护，但在链与链之间的边（称为“轻边”，也叫“轻链”）就需要直接维护。在重链
2014-04-06 13:04:14
551
原创 放象棋 矩阵中的DP题
题目的意思很简单：在n * m的矩阵中放置若干个炮（可以不放），使得没有一个炮可以攻击另外一个炮。炮的攻击方式和中国象棋的一样，中间只要有一个棋子就能打到对面。答案mod 9999973。这个题目一开始我想得很接近了，但没想到用DP，觉得是组合数学。首先可以把问题转化一下：没有一列或一行有两个以上的炮，这样炮于炮之间就不能攻击了。也就是说，每行或每列，要么不放炮，要么放一个或两个，有三种可能。又因
2014-04-06 13:04:11
631
原创 DP的另一个角度 数列划分
有个长度小于40000数列，把它分成若干段，使得各段花费总和最小。一段的花费为该段不同元素的个数(不妨设有x)个，那么花费为x的平方。看到题目，不难想到动态规划的做法。设f(i)为前i个元素最小的花费，然后枚举最后一段放多少个元素，不妨设为k个，那么f(i)=min{f(i-k-1)+cost}。这当然是可行的，但时间复杂度不容乐观。再思考，发现每一段最多只有200个不同的元素，若大于20
2013-07-23 14:53:21
713
原创 网络流dinic算法
遇到过不少网络流的题目，直接找增广路径的方法时间复杂度实在受不了。常面临TLE的问题。通过学习这个dinic算法，不仅代码短，效率也高。该算法的重点在于一个层次图，是在普通增广的方法上加了优化，普通的增广是每次在图上四处游荡，直到找到汇点为止。dinic算法就是把每个点都给一个等级level，把它们分在不同的层次之中，对于点u，v只有满足level(v) = level(u) + 1，才能通过
2013-07-23 11:19:08
810
原创 斐波纳契数列 线段树的维护
像一般的数列维护一样，这题也差不多。有一个数列a，修改操作是将a[i] .. a[j]的值都加上一个d，询问操作就有点不同，给出i和j，求出a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i)模上一个数的结果。其中fib就是斐波纳契数列，即fib(0) = fib(1) = 1，对于fib(i
2013-07-23 10:49:17
782
原创 线段树经典题目 矩形面积
有N（100000）个长方形，并且它的边长平行于x轴或y轴（范围50000）。求这N个长方形覆盖的面积，重叠部分的面积只算一次。在平面上的一些统计的题目，往往是用线段树，把x轴作为扫描线，然后把y轴映射到线段树上。这题也是如此：若坐标范围太大，可以将其离散化，这题不需要。如图，有两个矩形。竖细线作为扫描线，把y轴映射到线段树。在处理每一条扫描线的同时，首先统计线段树中已经被覆盖
2013-07-23 09:55:59
869
原创 mmm含树 查询点的提示
这是今年GDKOI的一题：有一棵树，开始时所有结点的值都是0。有多个操作，每个操作有两种：1.对某个点增加w，设dis（i，j）为点i到点j的最短距离，那么某个结点增加w时，对于任意一个结点j，它的值会增加w + dis（i，j）。2.询问某点的值。w可以忽略，因为整棵树都要加上w，只要记下所有w的和就可以了，输出答案时再加上。这题的突破口就是只需要求一个点的值，这就取决于其他发生变化
2013-07-22 21:24:22
810
原创 树链剖分
链可以看做是一种特殊的树，当一棵树退化成了链，某些问题就变得容易解决，也有很多数据结构支持这样那样的操作，线段树就是其中一种。从而我们可以想象，能否把一棵树也分成很多条链，从而来解决一些问题呢？
2013-07-22 09:27:31
838
原创 矩阵中的DP题 放象棋
题目的意思很简单：在n * m的矩阵中放置若干个炮（可以不放），使得没有一个炮可以攻击另外一个炮。炮的攻击方式就不用多说了。答案mod 9999973。这个题目一开始我想得很接近了，但没想到用DP，觉得是组合数学。首先可以把问题转化一下：没有一列或一行有两个以上的炮，这样炮于炮之间就不能攻击了。也就是说，每行或每列，要么不放炮，要么放一个或两个，有三种可能。又因为行列是交错的，每放一个炮，对行
2013-07-18 07:57:18
641
原创 摩天楼 DP优化
有N（≤1300）栋摩天楼，从左往右排成一行。第i栋的高度是i个单位，并且每栋摩天楼都有颜色（有些摩天楼的颜色相同），将这些摩天楼排列，有多少种排列的方法，使得从左往右看去，看到不多不少刚好L栋摩天楼，答案mod 1000000009。这里定义一下“看到”，首先若某栋摩天楼左边有比它高的，那就看不到。如果从左往右依次连续看到的两栋（或以上）摩天楼颜色相同，会误认为是一栋。由于这个关系到次序
2013-07-17 15:45:27
971
1
原创 几何和网络流的结合 战火星空
这题一开始折磨了我一个上午，下狠心重编，结果一下就过了。看来重编也算是个好方法。题目大意：在平面上有N个boss，boss始不会动，还有M架小飞机，给出小飞机的飞行路线（是线段，飞到终点后消失），还有射程（即一个圆的半径），飞行速度，能量，每攻击boss一个单位的时间就要消耗一个单位的能量（攻击的时间可以是小数），boss不能在同一时刻被多架飞机攻击。求boss被攻击的最大总时间。首先要知
2013-07-15 19:32:20
756
原创 奶牛合作 对于位操作的敏感
有n( 首先比较敏感的就是编号不算大，是2的20次方，还有就是and操作的结果只和0的个数有关系，如果某位有一个0，那么结果必然是0。所以对每一位进行考虑（指的是将数字转成二进制的某位）：假如有4有奶牛，编号依次为1、2、3、4：位 3 2 11 0 0 1 //最左边的0称为第三位，中间的0为第二位，1是第一位2 0 1 03 0 1 14 1 0
2013-07-12 08:23:19
706
原创 线段树多个信息的传递（加法和乘法） seq
用线段树对一段的数据进行单纯的加法、乘法，这些都不难，只需要在某个区间内做个懒标记，然后经过每个结点时都把懒标记往下传递。 如果有多个标记，最简单的就是加减混合。多个信息的难点就在于如何把信息结合起来，要知道5 + (6 * 2)是不等于(5 + 6) * 2的。 这题需要把懒标记写成d * x + y，原数据是d，先乘上x再加y（x的缺省值是1，y是0）。 如果有一
2013-07-11 19:04:28
859
原创 寻找图中的数字8
这是一道来自UASCO的一道有趣的题目（2013 US Open, Gold），给出一个图：.................................*******......*....*.......*.*......*....*.....*.............*...****.....................**.*..*..*...
2013-06-18 20:13:13
832
原创 同构树的判断 poj 1635
题目的描述比较长，总的意思就是给出两棵有根树，判断它们是不是同构树。所谓的同构树，定义我也不太知道。按字面上的意思就是两棵结构相同的树。如第一棵树和第二棵树就是同构树，它们和第三棵树不是同构树：并且，同构树它们有一一对应的点。对于任意一棵有根树，都可以用括号表示法来表示，可以去http://www.byvoid.com/blog/directed-tree-bracket-
2013-06-18 08:38:07
2975
原创 计算两直线的交点 poj 1269 我的第一道几何题
设读入的四个点分别为A, B, C, D。首先，算出矢量AB和CD，如果它们的叉积为0，则说明它们的方向是相同或相反的，也就是这两条直线的斜率相等。若斜率相等，则要进一步判断它们是否为同一条直线，那只需要判断点C是否在直线AB上，如果矢量CA和矢量AB的叉积为0，则说明它们的方向是相同或相反的，那么点C就在直线AB上。若斜率不相等，则要求交点。如图，C’D’平行CD，v、w、u
2013-06-04 16:32:45
705
原创 一道贪心题
有n的学员，每个学员有身高 h 和跳跃力 g 两个参数，有一堵高L的墙，若某学员要跳出去，则可以让其他学员搭成塔，满足 没有跳出去的学员(包括该学员)sum(h) + 该学员g >= L，这个学员就可以跳出去。已经跳出去的学员不能回来，通过合理安排学员跳走的顺序，最多能够跳出多少个学员。首先把每个学员 的 h + g从小到大排序，若某个学员 i 能跳出去，那么就跳出去。当某个学员不能跳出去时
2013-05-16 08:01:52
508
转载 KM算法的简单总结 二部图的最大权匹配
我们都知道有最大匹配，但如果说要加上费用，也就是已知每两个匹配的价值，要求出最大价值的匹配。这个可以用费用流，但KM算法的效率要远远比费用流好。KM算法有点贪心的思想，是通过不断的放宽费用的流量来实现的，当发现找不到匹配时，就一点点地放宽。至于最小权，我没有去找过代码。但其实可以把权值取相反数，再求最大权也是一样的。摘自 百度百科：KM算法求的是完备匹配下的最大权匹配：
2013-05-16 07:26:44
1119
原创 炸弹 树形地图
题目大意：在一个50*50的地图内，有些是空地，另外的是障碍物，空地是连成一棵树。若在某空地放置一个炸弹，那么在同一列和同一行且没有障碍物阻拦的格子都被炸到（类似于泡泡堂。。。）。询问至少需要多少个炸弹才能把所有的格子都炸到。题目中很关键的一个字眼就所有的空地是一棵树，这促使我们往树形动态规划的方面去想。构建一棵二叉树，左子树表示在同一行的空地，右子树表示同一列的空地。那么，若把某个节点炸
2013-05-15 21:54:19
795
原创 优化到极限 好点
题目大意：有一个N*M的网格，左下角的坐标是(0, 0) 右上角的坐标是(m, n)， 即一共有(N+1)*(M+1)个整点， 在任意两个整点连一条线段，若没有其他整点在这条线段上，且该线段长度在[L...H]之间，那么这两个整点叫做好点，求有多少对好点。答案mod B。1 首先要解决的一个问题，若给出两个整点，要判断它们是不是好点。这很简单，只要看它们的横坐标的差和纵坐标的差是不是互质的（为
2013-05-15 19:36:46
649
原创 矩形计数
题目大意：在一个以(0,0)为左下角，(w,h)为右上角的矩形内，有n个标记。统计有多少个小矩形，满足端点都在大矩形内的整点上，且平行于x轴和y轴，且这些矩形不包含任何一个被标记的点（包括边界上和端点）。这些矩形可以是退化的矩形（即面积为0）。答案mod 1 000 000 007。w，h ，n 首先将所有的点进行离散化，那么对于每一个枚举出来的矩形（图中加粗矩形），如图，统计出有多少
2013-05-15 18:47:49
1226
原创 "字串转换vert" 矩阵乘法 巧妙加点
给出两个字符串S和T，长度相等，由小写字母‘a’、‘b’、‘c’组成。每次操作，你可以对字符串S进行如下操作之一：1、 选择S的一个字符‘a’,把该字符变成字符‘b’，费用是cost[0]。2、 选择S的一个字符‘b’,把该字符变成字符‘c’，费用是cost[1]。3、 选择S的一个字符‘c’,把该字符变成字符‘a’，费用是cost[2]。你的目标是把字符串S变成T，但是总费用不能
2013-05-10 09:54:59
798
原创 树路径中的分治算法 poj 1741
分治算法也可以在树上应用，详细可以看看《IOI2009 中国国家集训队论文 分治算法在树的路径问题中的应用 （漆子超） 》这篇论文。 这里主要对树的分治进行简单的总结。 树的分治快在哪？重点就在树的中心上，树的重心是指在某棵树中，把某个点去掉后，结点最多的子树的结点数最少。 这样，每次取重心来进行讨论，省下的递归处理，并且深度不超l
2013-04-25 19:55:49
790
原创 动态规划和字符串匹配（KMP、AC自动机）
最近学了关于字符串匹配主要的两种方法，做了一些题目，发现这可以动态规划结合，题目中往往有“……T是S的子串……”这类字眼，而且答案要求“最少、最多、多少种”一类的问题。解决这类问题往往是要记录一个“匹配到哪一位”的状态，然后考虑当前状态可以更新哪些新的状态，下面列举两道题目： KMP 有两个字符串S和T（1 ≤ |S| ≤10000， 1 ≤ |T| ≤ 1000），问题是至
2013-04-17 19:12:01
1030
原创 poj 3167 KMP好题
题目大意：给出A，B两个序列（|A|≤100,000,|B|≤25,000），序列中元素的大小1≤S≤25,然后在A里面找出满足B特征的子序列（当然子序列和B的长度要相等）,输出所有A中满足条件的子序列的开端下标。如样例：A 5 6 2 10 10 7 3 2 9B 1 4 4 3 2 1不妨用#i表示B序列的第i数，则#1和#6在B序列中是相等且是最小的，所以在满足条件的子序列中
2013-04-07 19:15:29
650
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人