加载中…
个人资料
暴风雪
暴风雪
  • 博客等级:
  • 博客积分:0
  • 博客访问:43,513
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
搜博主文章
牛人博客

[jmsu]鸟神

[jmsu]鸟神

果冻

android开发必看

大圣

DP+数学大牛

凌风

DP+数据结构

Tornado

数学+计算几何

访客
加载中…
评论
加载中…
博文
标签:

[zz]后缀数组

题目

acm

数据结构

it

分类: 绝密文档

原文:http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html

单独把它列出来是因为这个东西真的很神奇~~~

后缀数组经典思想:多串合并+二分答案+最优性--->可行性

例 1 :最长公共前缀
给定一个字符串,询问某两个后缀的最长公共前缀。   // 直接套用,ans=min( height[ i ] )+rmq    k<i<=j

例 2 :可重叠最长重复子串
给定一个字符串,求最长重复子串,这两个子串可以重叠。   // ans=max( hegiht[ i ] ) 0<=i<len

例 3 :不可重叠最长重复子串( pku1743 )      AC
给定一个字符串,求最长重复子串,这两个子串不能重叠。   // 二分转化为判定性问题

例 4 :可重叠的 k 次最长重复子串( pku3261 )       AC
给定一个字符串,求至少出现 k 次的最长重复子串,这 k 个子串可以重叠。   // 同上,也是二分
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

分类: 绝密文档

poj pku字符串题目推荐及解题报告 ­ 

POJ 1002 - 487-3279(基础) ­ 

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

杂谈

本博客已搬往  http://bbezxcy.iteye.com/
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

最大流

hdoj

3572

task

schedule

it

分类: 图论专区
大致题意:
    有n个工件,已知第i个工件需要pi天加工,而且只能在第si天到第ei天加工这个工件。每天可以并行加工m个工件。求所有工件是否都能在规定期限内加工完成。

大致思路:
    应该算是最简单的网络流题目了吧,把工作和日期都抽象成节点,设源汇点。从源点向每一个工件连边,容量为完成工作所需要的天数。每个工作都向可以加工他的日期连边,容量为1。每个日期都向汇点连边,容量为每天可以加工工件数量的最大值。求出最大流,如果从源点出发的边都满流则说明存在可行的方案。
    最后一道水最大流,结束我的费用流/最大流/最小割学习。接下来,无源汇网络流,有上下界的网络流,差分约束,数据结构神马的,该搞起的都搞起吧~~一想到还有动态规划就头皮发麻

详细代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int inf=1<<30;
const int nMax=
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

状态压缩

最大流

hdoj

3605

escape

it

分类: 图论专区
大致题意:
    在世界末日,有n个人要去m个星球。给出每个人能去的星球和每个星球能容纳的人数。判断是否存在可行的安排方案。n (1 <= n <= 100000), m (1 <= m <= 10) 

大致思路:
    以为是水题上来就直接套二分图多重匹配来做,结果被TLE到各种吐血~~。后来看了题解才明白,这里要用状态压缩。因为所有的人可以按照可以去的星球划分为2^m类人。这样不按照人头来建图而用人的种类来建图,点的规模会大大缩小。终于领会到二进制压缩的妙处了。

详细代码:

#include<iostream>
#include<cstring>
#include<cstdio>
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

最大流

poj

2584

t

shirt

gumbo

it

分类: 图论专区
大致题意:
    已知n个同学和5种衣服,要让每一个人都有衣服穿。已知每个同学可以穿的衣服种类,每种衣服的数量。求衣服的数量能否满足同学的需求。

大致思路:
    标准的二分图多重匹配,设超级源汇点,超级源点向每个同学连边,容量都为1。每个同学都向他需要的衣服连边,容量也是1。每件衣服向汇点连边,容量为其数量。对这个图求出最大流,如果得到的值等于n则表示可以提供给所有人衣服,否则就是无法提供。
(在家里刷了3天终于刷到水题了,擦~~睡个好觉吧)

详细代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int inf=1<<30;
const int nMax=10005;
const int mMax=40000;

class node{
    public:
    int c,u,v,next;
};node edge[mMax];
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

最小割

hdoj

3820

golden

eggs

it

分类: 图论专区
大致题意:
    给出一块n*m的区域,已知区域中的每个格子都可以放金蛋或者是银弹,已知每个格子放金蛋或者是放银弹时可以得到的收益,分别用矩阵map1[][],map2[][]表示。如果相邻的两个格子放的蛋相同的话会扣去一定的收益,金蛋的话会扣去g,银弹s。求收益的最大值是多少。

大致思路:
    (喷:刚放寒假就碰到这么多神题,真的好郁闷啊!!)
    首先,对于某个确定的位置,只能选择金蛋或者银弹的其中一个放上去,从这里可以想到和二分图最大点权独立集有关。其次,如果相邻的位置放的蛋相同的话需要付出一定的花费这个又和hdu 3657:Game有些许相似之处。所以我们这么构图:

按照黑白染色把矩阵中的位置分为A,B两个集合,每个集合中的位置拆为k,k'两个点。对于A集合,从源点向k连边,容量为它放金蛋是的收获,从k再向k'连边容量设为inf,从k'连到汇点,容量为其放银弹时的收益。这样设的目的就是为了使得割必须在源点到k或者k'到汇点上。   
对于B集合,我们做一些改变,把从源点到k的容量设为放银弹的收益
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

费用流

hdoj

4067

random

maze

it

分类: 图论专区
大致题意:
    给出一个由n个点,m条边组成的有向图,对于每条边保留或者删除都分别有不同的消耗值。给出图中的两个点s,t。现在问能否通过删去和保留一些边,使得s的入度==出度+1,t的出度==入度+1,其余的点入度等于出度。

大致思路:
    具体做法就是往欧拉回路上去套。详细思路建图懒得写了,因为写出来和网上其他人的思想也差不多,如果没有用网络流处理入度出度的经验的话一般也看不懂。  如果能够把poj 1637混合图的欧拉回路仔仔细细研究透的话这道题也就不难了!

详细代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=99999999;
const int nMax=3000;
const int mMax=200000;
struct{
    int u,v, cap, cost, next, re;
}edge[mMax];
int ans,maxf;
int k,edgeHead[nMax];
int que[nMax],pre[nMax],di
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

最小割

hdoj

3657

game

it

分类: 图论专区
大致题意:
    给出一个n*m的矩阵,让你从中取出一定数量的数字。如果在矩阵中两两相邻的数字被取到的话需要付出一定的代价。而且给出某些点,规定这些点一定需要取到。求最多可以取到多少点。

大致思路:
    怎么说呢,这道题乍看上去和hdoj 1569:方格取数很相似,也很像是一个二分图的最大点权独立集问题。但是问题出的很巧妙,也就没有办法往模版上面套了。把矩阵中的点按照横纵坐标之和的奇偶性分成两个集合,设超级源汇点,源点第一个集合中的所有点连边,容量为这个点代表的数字的值。第二个集合中的所有点向汇点连边,容量也是这个点的值。第一个集合中点都向他周围的点连边,容量为他们同时被取时的消耗。如果一个点必须取,那就将他和源/汇点的容量设为inf,保证这条边不被割掉。用所有点的权值之和sum减去这个图的最小割得到的就是答案。总的来说,ac后的感受就是,这是一道需要意识流的题目

详细代码:

//hdoj 1565 code
#include<iostream>
#include<cstring>
#include<
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

动态规划

拆点

最大流

hdoj

3998

sequence

it

分类: 图论专区
大致题意:
    题意很简单。给出一列数num[],求出这列数的最长递增子序列len,并且需要求出这列数里面包含出多少长度为len的递增子序列。注意每个数最多只能属于一个子序列!

大致思路:
    首先对这列数求出最长递增子序列len,并得到每个数字的dp值。由于每个点只能被用一次,所以我们把每个数字都拆成两点i和i',连接i->i'容量为1,代表这个点只能被用一次。如果一个点的dp值为0则从源点向i连边,容量为inf。如果其dp值为其最长递增子序列长度len,则连接i'到汇点,容量为inf。对于两个点,i和j,如果num[i]<num[j]且dp[i]==dp[j]-1(也就是第i个数在某个递增子列中扮演第j个数前面的数字的角色)则连接i'->j容量为1,代表这个关系只能被用一次。对这个图求出最大流得到的就是最长递增子列的个数

详细代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
好友
加载中…
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有