- 博客(69)
- 收藏
- 关注
RSS订阅原创 ACdream 1415 最短路+桥的判断
Important RoadsProblem Description The city where Georgie lives has n junctions some of which are connected by bidirectional roads. Every day Georgie drives from his home to work and back. But the r
2016-06-21 09:55:38
735
原创 POJ 1141 Brackets Sequence 区间dp
Brackets SequenceDescription Let us define a regular brackets sequence in the following way: Empty sequence is a regular sequence. If S is a regular sequence, then (S) and [S] are both regular seque
2016-06-07 19:47:28
638
原创 HDU 2089 不要62
不要62Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。 不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6和2
2016-06-07 16:52:52
909
原创 hdu 4405 Aeroplane chess 概率dp入门题
DescriptionHzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probabilit
2016-04-13 22:02:48
475
原创 hdu 3586 Information Disturbing 树形dp+二分
Description In the battlefield , an effective way to defeat enemies is to break their communication system. The information department told you that there are n enemy soldiers and t
2016-04-12 12:57:24
367
原创 hdu 2296 Ring AC自动机+DP
Description For the hope of a forever love, Steven is planning to send a ring to Jane with a romantic string engraved on. The string's length should not exceed N. The careful Steven knows Jan
2016-04-12 12:57:22
314
原创 poj 3691 DNA repair AC自动机+DP
Description Biologists finally invent techniques of repairing DNA that contains segments causing kinds of inherited diseases. For the sake of simplicity, a DNA is represented as a string cont
2016-04-12 12:57:20
292
原创 hdu 1520 Anniversary party 树形dp水题
Description There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the superviso
2016-04-12 12:57:15
359
原创 hdu 1561 The more, The Better 树形dp水题
Description ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？ Input 每个测试实例首先包括2
2016-04-12 12:57:13
315
原创 hdu 4123 树形dp+rmq
Description Bob wants to hold a race to encourage people to do sports. He has got trouble in choosing the route. There are N houses and N - 1 roads in his village. Each road connects two hous
2016-04-12 12:57:10
402
原创 POJ 2761 Feed the dogs 求区间第k大 划分树
Description Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs every day for Wind. Jiajia loves Wind, but not the dogs, so Jiajia use a special way to fe
2016-04-12 12:57:08
333
原创 hdu 4585 shaolin 平衡树
Description Shaolin temple is very famous for its Kongfu monks.A lot of young men go to Shaolin temple every year, trying to be a monk there. The master of Shaolin evaluates a young man mainl
2016-04-12 12:57:03
361
原创 *hdu 4616 Game 树形DP
Description Nowadays, there are more and more challenge game on TV such as 'Girls, Rush Ahead'. Now, you participate int a game like this. There are N rooms. The connection of rooms is like a
2016-04-12 12:56:59
373
原创 hdu 5379 Mahjong tree 树形DP入门
Description Little sun is an artist. Today he is playing mahjong alone. He suddenly feels that the tree in the yard doesn't look good. So he wants to decorate the tree.（The tree has n vertexs
2016-04-12 12:56:56
330
原创 CF 581F Contest Page 树形DP
Description It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on n main s
2016-04-12 12:56:52
303
原创 hdu 2778 LCR 模拟题
Description LCR is a simple game for three or more players. Each player starts with three chips and the object is to be the last person to have any chips. Starting with Player 1, each person
2016-04-12 12:56:47
1331
原创 hdu 2896 病毒侵袭 AC自动机
Description当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋――我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~ 但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要
2016-04-12 12:56:45
340
原创 hdu 2222 Keywords Search AC自动机模板题
Description In the modern time, Search engine came into the life of everybody like Google, Baidu, etc. Wiskey also wants to bring this feature to his image retrieval system.
2016-04-12 12:56:43
255
原创 poj 1185 状态压缩
Description司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它
2016-04-12 12:56:38
358
原创 hdu 3001 Travelling 旅行商问题变形 三进制的压缩dp
Description After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not
2016-04-12 12:56:34
430
原创 poj 3311 Hie with the Pie 旅行商问题变形 记录最短路径压缩状态
Description The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deli
2016-04-12 12:56:29
504
原创 zoj 2587 kmp的应用
DescriptionLong long ago, there was a coder named Marlon. One day he picked two string on the street. A problem suddenly crash his brain...Let Si..j denote the i-th character to the j-th character
2016-04-12 12:56:27
211
原创 hdu 3746 kmp求字符串循环节
这道题应该可以早就过的，却拖了一下午=_=，主要是我遇到了很奇怪的问题，现在还不知道原因。 那就是我一开始写的输入是： while(T--&&(scanf("%s",s+1)!=EOF)){ ......}一直wa，最后实在感觉没错，很无奈，照着别人的代码一个字符一个字符比对，发现改成以下格式就过了： while(T--){
2016-04-12 12:56:23
339
原创 hdu 3336、4763、2594 kmp next数组的理解、模板题
hdu 3336 Count the string Description It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the n
2016-04-12 12:56:18
446
原创 KMP复习小结
kmp能够实现单模板串的快速匹配。 备忘：cstring 头文件里的char* strstr 函数也是比较一个字符串是否为另一个字符串的子串，与KMP功能相同，速度究竟谁快？ 经过测试，aaaaaa…….aaaab(len =1000) 去匹配 aaaaaaa…..aaab(len=1000000) strstr 函数用了将近一秒钟,而kmp算法只花了不到0.1秒的时间。除了这种极端的情况外
2016-04-12 12:56:16
204
原创 poj 2411 Mondriaan's Dream 状态压缩dp
Description Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he had to use his toilet paper to
2016-04-12 12:56:11
246
原创 poj 2823 线段树
An array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each tim
2016-04-12 12:56:02
309
原创 poj 2352 树状数组
Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are n
2016-04-12 12:56:00
188
原创 poj 2528 数的离散化+线段树
在一面墙上贴海报，贴的顺序给出了，求最后能被看到的海报数量。纯粹的线段树模拟题。但数据范围给了10^7，超内存了。实际上这里用了一个小技巧，虽然墙的宽度是很大的，但海报数量只有10000，所以这10^7个数中真正用到的数很少，这样的话就只需要把没用到的数给“删去”，剩下来的数从小到大映射为新的数，这样空间复杂度就大大降低了。这就是数的离散化。比如题目给的样例：1 42 6
2016-04-12 12:55:55
232
原创 poj 2155 二维线段树
在一个二维数组中，每次对一个矩形内所有数据进行取反操作，并实时询问某一位置的值。 一般线段树只支持对一维数据进行更新和查询，但是这题给的是二维数据啊！ 这里就需要用到二维线段树了，即树套树，外层线段树的每个结点里面都有一颗线段树。 在实现二维线段树的时候，一开始用加build函数的方式，记录每个结点左右孩子的编号，但超内存了，所以直接用二维数组表示二维线段树，左右孩子编号通过计算得到：设父亲
2016-04-12 12:55:53
296
原创 hdu4758 hdu2825 hdu4057 AC自动机与状态压缩dp的结合
最近做到好几道关于AC自动机与状态压缩dp的结合的题，这里总结一下。 题目一般会给出m个字符串，m不超过10，然后求长度为len并且包含特定给出的字符串集合的字符串个数。 以HDU 4758为例： 把题意抽象为：给出两个字符串，且只包含两种字符 'R'、'D'，现在求满足下列条件的字符串个数： 1、字符串必须包含上述两个字符串。 2、字符串长度为(m+n)，其中包含n个'D'，m个'R'
2016-04-12 12:55:48
379
原创 windows本地评测批处理脚本
在任意文件夹中放入“data.in”和“data.out”文本文件，它们分别表示输入文件和输出文件。 当然还有将被评测的代码文件“代码.cpp”。 将下面的批处理代码复制进txt文件，改后缀名为.bat，放入文件夹。 @echo offstart /wait 获取时间.exe set t1=%errorlevel%代码 代码.outsta
2016-04-12 12:55:46
349
原创 POJ 2299 Ultra-QuickSort
题目大意就是要求数组中逆序数的对数，和51nod1019一样，可以用树状数组。先对所有数进行排序，还要记录每个数原来在数组中的下标，在排好序的数组中，从小到大依次访问，假设访问到第i个数，用树状数组查询1~i-1的数中原始下标小于等于k的个数（k是第i个数的原始下标）。同时动态更新树状数组。#include#include#includeusing namespace
2016-04-12 12:55:42
219
原创 hdu 4568 旅行商问题dp
这个题目题意描述不清，没有说明只能进入一次。题目意思很好理解，不再重复。思路也比较好想，先计算每两个宝藏区的最短路，和每个宝藏区到边界的最短路，然后dp解决。在计算最短路的时候，用优先队列优化的Dijkstra算法。在-1的处理上有些小技巧。 但是！但是！！，我之前的思路是dp[i]表示状态i的最小cost值，并没有经过严格证明和认真思考导致wa好多次。实际上这个思路在计算
2016-04-12 12:55:37
372
原创 [数据结构-查询区间最小值小结(RMQ问题(Range Minimum Query)）]
查询区间第k大可以用划分树，而查询区间最小（最大）值可以用代码更简单的Sparse-Table（ST）算法（Tarjan发明）。 原理很简单，代码也很短： 令d(i,j)表示从i开始的，长度为2^j的一段元素最小值，那么可以用递推方法计算： d(i,j) = min( d(i,j-1) ， d(i+2^(j-1) , j-1) ) void RMQ_init(const vector
2016-04-12 12:55:33
836
原创 [数据结构-树状数组小结]
树状数组又叫二叉索引树 参考《训练指南》P194 动态求连续区间和，可以动态更新数据，支持以下两种操作： 1、 对某一元素进行更新操作。 2、 查询某一连续区间的元素和。 对于正整数x，我们定义lowbit(x)为“x的二进制表示中最右边的1所表示的值”，例如lowbit(11001100) =100 （这里的11001100、100都是二进制表示），在程序实现中lowbit(x) =
2016-04-12 12:55:30
322
原创 [数据结构-划分树小结]
划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值。 先看下图已经建好的划分树是什么样子的，原始数组是[1,5,2,3,6,4,7,3,0,0]，并把它作为树的第0层，然后把这些数中较小的数再组成[1,2,3,0,0]，顺序还是遵照原数组的顺序，同样将较大的数再组成[5,6,4,7,3]。把这两个数组作为树的第二层，它们的父亲则是第一层的原始数组
2016-04-12 12:55:28
366
原创 [其它-GarsiaWachs算法]51nod 1023 石子归并v3
1023 石子归并 V3 基准时间限制：2 秒 空间限制：131072 KB 分值: 640 难度：8级算法题 N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 例如： 1 2 3 4，有不少合并方法 1 2
2016-04-12 12:55:23
1160
原创 [dp专题-四边形不等式优化]51nod 1022
1021 石子归并 V1 N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。 例如： 1 2 3 4，有不少合并方法1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)1 2 3 4 => 1 5 4(5) => 1 9(1
2016-04-12 12:55:19
882
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人