[综合] Number Sequence HDU - 1711 (简单KMP)

题意: 给你T串和模板P串,输出P第一次出现的位置. 分析: 简单KMP,直接用模板. #include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e7; intT[maxn],P[maxn],f[maxn],f2[maxn]; intn...

[综合] Count the string HDU - 3336(KMP+DP, 串前缀匹配自身)

题意: 给定一个串,求用该串所有前缀去匹配这个串次数的总和. 分析: 失配指针数组的应用:dp[i]表示S[0,i-1]串的后缀能匹配的前缀的个数.则dp[i]=dp[f[i]]+1;初始化dp[1]=1; 这里用到的就是失配指针的含义：后缀与前缀. #include<bits/stdc++...

[综合] 剪花布条 HDU - 2087(KMP 贪心选择)

题意: 给定两个串S和T,求S中最多不重叠的包含了多少个T串. 分析:不重叠的话,就是在正常的KMP基础上,匹配到T的末尾的时候,j要回到0. #include<bits/stdc++.h>usingnamespacestd; constintmaxn=1111; chars[maxn...

[综合] 亲和串 HDU - 2203 (KMP 循环移位一个串去匹配)

题意: 判断P串是不是能和T串循环移位K位后的字符串有匹配点 分析:把T往自身后面贴一下变成TT,然后看P在TT中有没有匹配点即可~~~ 这种往后帖一下的思想可以说是一种技巧,比如:求数组挖去连续一块后求剩下的有多少个不同的数. #include<bits/stdc++.h>usingn...

[综合] Seek the Name, Seek the Fame POJ - 2752 (KMP 失配指针数组)

题意: 给定一个串T,找出串T的子串,该串即既是T的前缀也是T的后缀.从小到大输出所有符合要求的子串的长度. 分析:把答案就是f[m]f[f[m]]...依次下去.理解f数组的前缀后缀思想这道题就迎刃而解了. #include<bits/stdc++.h>usingnamespaces...

[综合] 统计难题 HDU - 1251 （Tire树的基本运用）

题意: 给你多个单词,然后在给你一个字符串s,现在要问你以该字符串s为前缀的单词数目有多少个? 分析: 标准的Trie树应用,我们只需要用树节点的v值表示以树根root到当前节点的路为前缀的单词数即可. 在插入新单词节点的时候,该单词节点路过的所有Trie节点v都要+1. 查询的时候,如果能查到该前...

[综合] Remember the Word UVA - 1401 (Trie+dp)

题意: 给你一个由N个单词组成的词典，和一个字符串S。问你S由N中的单词组成的方法有多少种?字典中的单词可以重复使用但是不可重叠。 分析: 令d[i]=x表示S串的后缀[i,L-1]串有多少种构造方式.L=strlen(S).字符从0到L-1下标. d[i]=sum(d[i+len(x)])仅当[i...

[综合] Phone List HDU - 1671(Trie树的基本运用)

题意: 给你多个由0-9构成的字符串集合,问你这个集合中是否有一个字符串是其他字符串的前缀? 分析: 直接构造字典树,然后一一插入每个字符串,判断是否有比当前字符串短或长的同一路径的字符串已经在树中了. #include<bits/stdc++.h>usingnamespacestd...

[综合] Revenge of Fibonacci HDU - 4099 (Trie树运用)

题意: 给你一个数,这个数是斐波那契数列中的一个数的前缀,找出这个前缀的最小下标.且这个下标如果超过了10W还没有符合要求的话,就输出-1.且输入数不会超过40位,且没有前导0. 分析: 直接思路那就是把前10W个斐波那契数列都搞出来构建字典树,然后对每个输入串判断该字典即可.这种想法不可行~,下标...

[综合] Shortest Prefixes POJ - 2001 (Trie树基本运用)

题意: 给定多个单词组成的词典,输出每个单词对应的前缀,使得每个前缀唯一. 如果不存在就输出单词本身.也就是:找出一个前缀,该前缀能唯一表示该字符串. 分析: 建立Trie树,每个节点的V代表有多少个字符串路径上含有它. Find函数里查找每个单词的前缀,知道v值==1返回即可. #includ...

[综合] HDU2157(矩阵的一种 经典问题)

给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数modp的值把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的...

[综合] 最近等对 51Nod - 1571 线段树区间修改 区间最小值

现在有一个序列a1,a2,...,ana1,a2,...,an，还有m个查询lj,rj(1≤lj≤rj≤n)lj,rj(1≤lj≤rj≤n)。对于每一个查询，请找出距离最近的两个元素axax和ay(x≠y)ay(x≠y)，并且满足以下条件： ?lj≤x,y≤rj;lj≤x,y≤rj; ?ax=ay。...

[综合] 导弹防御塔---二分图匹配《lyd算法进阶》

题目描述 Freda控制着N座可以发射导弹的防御塔。每座塔都有足够数量的导弹，但是每座塔每次只能发射一枚。在发射导弹时，导弹需要T1秒才能从防御塔中射出，而在发射导弹后，发射这枚导弹的防御塔需要T2分钟来冷却。所有导弹都有相同的匀速飞行速度V，并且会沿着距离最短的路径去打击目标。计算防御塔到目标的距...

[综合] CodeForces - 1046A （动态开线段树）

CodeForces-1046A 题意： 给一组机器人，每个机器人有x,r,q三个属性。x:坐标，r:视野范围，q:IQ值。 每个机器人视野为：[x-r,x+r]，如果一对机器人相互可以看到，且它们的智商差距不大于K，那么他们可以聊天。问多少对机器人可以聊天。 题解： 先按视野降序排序，后面能看到...

[综合] 4301 Can you answer on these queries III 0x40「数据结构进阶」例题（线段树）

4301CanyouansweronthesequeriesIII0x40「数据结构进阶」例题 描述 给定长度为N的数列A，以及M条指令(N≤500000,M≤100000)，每条指令可能是以下两种之一：“2xy”，把A[x]改成y。“1xy”，查询区间[x,y]中的最大连续子段和，即max(x≤l...

[综合] 4302 Interval GCD 0x40「数据结构进阶」例题（线段树，差分）

题意： 4302IntervalGCD0x40「数据结构进阶」例题 描述 给定一个长度为N的数列A，以及M条指令(N≤5*10^5,M<=10^5)，每条指令可能是以下两种之一：“Clrd”，表示把A[l],A[l+1],…,A[r]都加上d。“Qlr”，表示询问A[l],A[l+1],…,A...

[综合] P1438 无聊的数列（线段树，差分）

P1438无聊的数列 题目背景 无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗） 题目描述 维护一个数列{a[i]}，支持两种操作： 1、1LRKD：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应...

[综合] BZOJ 1150 （堆 + 链表）

数据备份BackupHYSBZ-1150 你在一家IT公司为大型写字楼或办公楼（offices）的计算机数据做备份。然而数据备份的工作是枯燥乏味 的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。已知办公 楼都位于同一条街上。你决定给这些办公楼配对（两个一组...

[综合] 「网络流 24 题」火星探险问题。

#6225.「网络流24题」火星探险问题 内存限制：256MiB时间限制：1000ms标准输入输出 题目类型：传统评测方式：SpecialJudge 上传者：匿名 题目描述 火星探险队的登陆舱将在火星表面着陆，登陆舱内有多部障碍物探测车。 登陆舱着陆后，探测车将离开登陆舱向先期到达的传送器方向移动。...

[综合] 「网络流 24 题」最长 k 可重区间集

#6014.「网络流24题」最长k可重区间集 内存限制：256MiB时间限制：1000ms标准输入输出 题目类型：传统评测方式：文本比较 上传者：匿名 题目描述 给定实直线LLL上nnn个开区间组成的集合III，和一个正整数kkk，试设计一个算法，从开区间集合III中选取出开区间集合S?IS\sub...