gungnir__-CSDN博客

原创 poj 3635 BFS 最短路变形

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16131【解题报告】题意比较明确。给定N(N<=1000)个点的图，要求从S到E花费最少。其中每个点可以加油，给出每个点的油价。一个单位距离消耗一个单位油。车辆有最大储存油量。可以把这道题目理解为是一个二维的最短路，其中这个“路”在这里并不是两点之间距离，

2016-03-20 22:15:51 404

原创 HDU 1548 BFS入门

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1548【解题报告】从A出发，问到B的最短路径。其实就是一个最短路问题。使用优先队列维护一下就好。不熟悉的人可能会用深搜去求解，不过暂时没想明白深搜会错到哪里，留个坑以后补。暂时远离ACM圈，以后随心情做点题，一切事情随缘吧。【参考代码】#include<iostream>#includ

2016-03-20 13:22:04 350

原创 codeforces 589H DFS

【题目链接】 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106786#problem/D【解题报告】给定n个点和m条边的无向连通图，和k个特殊点，任意两个特殊点之间连一条路，任意一个特殊点不能是两条路的端点。问最多能连多少条路。这个题目我是不会的（图论思维真的很弱。。。）。这个题还是重点要学习怎么分析题目的。对于一个连通

2016-02-25 22:58:21 493

原创 CodeForces 589F 二分答案

【题目链接】 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106786#problem/B【解题报告】这道题目对我来说关键在于读对题意。题意是：有n盘菜，每道菜有一段可以吃的时间。the gourmet想要吃完所有n道菜，并且每道菜花的时间相同并且尽可能长，问你能不能做到。如果可以，输出吃这n道菜的总时间。裸二分，二分

2016-02-25 15:50:22 962

原创 ZOJ 3582 概率DP

【题目链接】 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4624【解题报告】左右各有n个灯，灯亮的概率为P，是独立事件。且灯打开后就不会熄灭。问两遍各至少m个亮的期望。照例用递推。设dp[i][j]表示左边亮i个右边亮j个这个状态能够达到目标状态的期望。易知：dp[i][j]=sigma{ p*dp

2016-02-25 15:43:32 120

原创 POJ 2096 概率DP入门

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21521【解题报告】一共有n种bug，s个系统，每天发现一个bug（一共有无限多个bug，bug的种类和属于哪个系统是独立随机事件），问至少找齐 n种bug，每个系统至少找到一个bug的期望天数。我们使用递推的方法来解决这道题目。设dp[i][j]表示已

2016-02-25 14:50:46 359

原创 Codeforces 629C 简单DP

【题目链接】【解题报告】比赛的时候跑去做D了，这道题只是简单看了看，赛后补题把它补掉。这个题目只要想通了还是很水的。题意很简单，给你一个长度为m的串S，让你求不同的串P和Q的方案数使长度为n的串P+S+Q为一个合法括号序列。合法的括号序列要满足： 1.左括号和右括号数量相同 2.该串的任意一个前缀满足左括号数>=右括号数。那么我们设dp[i][j]表示长度为i的串，(比)多j个的方案数

2016-02-22 01:27:27 840

原创 Codeforces 521C 组合数取模（乘法逆元）

【题目链接】 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106914#overview【解题报告】之前很少遇到组合数取模的问题（做题太少了)，所以就GG了……组合数取模这一问题在算法竞赛中还是很常见的，必须扎实掌握。回到这道题目来，你需要在n个数之间放k个加号，然后求出所有方案的和。我们知道正向思维，即求出所有的方案，然

2016-02-20 18:34:07 1772

原创 HDU 5125 序列型DP

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5125【解题报告】求A的最长上升子序列，其中A中至多有M个元素可以被B中同位置元素替换。考虑到数据范围只有1e3，所以完全可以用O(n^2)的方法来求LIS，但是由于有了B数组的加入，所以我们需要考虑Dp的状态要设置两个，一个是从上一个状态的a转移过来，一个是从上一个状态的b转移过来。所

2016-02-12 05:20:58 1176

原创 HDU 1695&4135 容斥

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4135http://acm.hdu.edu.cn/showproblem.php?pid=1695【解题报告】题目其实很简单，考虑到容斥需要的几个基本操作需要打熟练，就更新这么一篇blog上来。hdu4135很裸。给出一个N，求A,B区间内和N互素的数都个数。那么我们如果知道有多少数和N不互质，

2016-02-12 04:24:08 264

原创 UVa 11825 状态压缩DP

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18913【解题报告】《训练指南》上状态压缩DP的例题。照样谈一些自己的体会。这道题目有一个地方是值得学习的，就是状态压缩之后如何枚举一个集合的子集。其他地方并没有什么难点。状态压缩之后的DP转移式很简单。#include<iostream>#in

2016-01-01 23:19:30 311

原创 UVa 10603 BFS+优先队列

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19527【解题报告】 lrj紫书中路径寻找问题的例题。大部分细节书中都有说明，不再赘述。说一点自己的感想。书里面说算法的正确性不是显然的，可是我觉得应该是显然的吧？每次找到队列里dist值最小的状态，以它来更新ans值，并且拓展其他状态。假如当前我们找到

2015-12-31 21:21:18 295

原创 UVa 11134 贪心

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34086【解题报告】题目大意：在N*N的棋盘里放N个车，使彼此不互相攻击（即不同行，不同列），每个车可以放在一个子矩阵里(给出矩阵左上角，右下角的坐标)，请给出任意一种放车的方案，如果不存在，输出”IMPOSSIBLE”。这题的贪心解法还是很值得认真体

2015-12-30 18:24:53 309

原创 POJ 3254 状态压缩DP

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21819【解题报告】状态压缩dp入门题。因为一层最多只有12个节点，容易想到我们用一串二进制数表示它，然后映射到对应的十进制数上。那么我们可以一层一层的转移。这里转移的时候需要满足两个条件。一个状态j，需要满足！(j&(j>>2))。这说明，j

2015-12-28 10:28:57 267

原创 UVA 1451 单调队列

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36267【解题报告】题目大意：给你一个长度为N的01串，求长度>=L的子串中，含有1的个数比子串长度最大的子串的左右端点。简单来说，就是假如我维护一个前缀和sum[i]表示前i个数中1的个数，那么求最大的( sum[i]-sum[

2015-12-27 07:13:28 627

原创 HDU 3507 斜率优化

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=3507【解题报告】花了两天时间，终于搞懂了斜率dp是怎么维护数据的，感觉自己理解力实在是弱的同时，也感叹确实难找到好的题解，有的题解甚至是错误的，比如百度这道题里面非常靠前的一篇blog，讲解思路混乱，同时给出了一个错误的结论：维护一个上凸点集。真不知道，他是如何在代码里维护的事下凸点集的情况里

2015-12-27 05:31:23 252

原创 POJ 2823 单调队列入门题

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16694【解题报告】这题是可以用优先队列做的，这样会简单一些，不过考虑到是为了熟练的掌握斜率优化这一技巧，所以特意通过做这道题目来熟悉单调队列的基本用法。因为考虑到单调队列是从队尾插入，访问队首元素。所以使用了双端队列这一STL。虽然要比手写的模拟队列要麻烦一

2015-12-26 05:38:38 380

原创和中位数有关的构造

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1303【解题报告】思路比较巧妙，重新定义数组，比b大的数设为-1，比b小的数设为1。为什么可以这么想呢？对于中位数而言，我们只关心这个连续序列里有多少个元素比他大，而不关心比他大多少，即比他大的数无论怎么排列都没有关系。也即，数列里的数只有三个性质：大于b，小于b，等于

2015-12-24 04:40:50 290

原创 Codeforces Round# 180 div2

【题目链接】 http://codeforces.com/contest/298这场比赛做的还可以，1hA了两道题，2h的时候做出来第三道。没有想到这场出的都是想法题。尤其是E题，确实是很考构造能力的。官方题解在此，十分清楚。 http://codeforces.com/blog/entry/7437

2015-12-23 06:25:11 245

原创 codeforces 289B 递推

【题目链接】 http://codeforces.com/problemset/problem/289/B【解题报告】 CF round 177 div2. 题目大意，给你一个N*M的矩阵，里面每个元素有一个val，你可以每次对它+d或者-d，问至少需要多少次操作，使得所有元素val相同。如果不可能，输出-1. 这道题做比赛的时候wa了五次。想对了一点，就是给定的n个数一定是模d的剩余相同。

2015-12-22 01:57:22 167

原创 hdu 1542 矩形面积并（扫描线+线段树）

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14795【解题报告】七月的时候做过扫描线线段树，那个时候觉得好难TAT…. 当然现在看是很基础的题目了。这道题根本上还是一个扫描线，不过由于是二维状态下的扫描，所以裸的扫描线是不可取的。因为那意味着O(n^2)的操作。（想想为什么不像一维的扫描线一

2015-12-16 07:46:45 1519

原创 POJ 2828 buy tickets 线段树

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10345【解题报告】题意：每个人有一个value值第i个人来了，站在编号为posi的人的后面售票处编号为0 输出价值序列思路：正着想，是一个插队的问题，由于一个区间都需要更新，复

2015-12-16 06:41:20 298

原创 HDU 3016 线段树单点更新+DP

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=3016【解题报告】这道题目把线段树和DP结合起来了，所以并没有思路。参考了一篇题解，觉得讲的非常好： http://www.cnblogs.com/scau20110726/archive/2013/05/11/3073398.html –Titanium这里面有一

2015-12-15 01:58:46 406

原创 hdu 2795 线段树单点更新

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=2795【解题报告】题目大意：给你一个高为h，宽为w的广告牌，现在有n个广告，每个广告长为l，高为1.每条广告尽可能往广告牌的顶部放（h尽可能小，），同一行尽可能往左放，对于每一个广告输出他在第几行，如果放不下，输出-1.这道题目可以对高h建树，线段树每个节点维护他所代表的区间的最长空位max

2015-12-15 00:23:00 274

原创 POJ 2528 线段树离散化

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14608[解题报告】题目大意：给定长度区间（L，R）//L，R<=1e7，给出N个区间操作，把li-ri区间贴上海报 //N《=1e5 求：有多少张海报没有被完全覆盖这道题目的关键在于，直接开1e7的线段树一定会MLE,但我们观察到一共只有不超过1e

2015-12-14 23:13:11 708

原创 hdu 1540 单点修改+区间合并

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1540【解题报告】题目大意：给长度为N的序列，有三种操作： 1.删除某个点a 2.查询包括点a在内的最长连续区间 3.恢复最后一个被删除的点这道题目和hotel很像，不同的是，hotel区间更新，这里单点更新；在区间查询上，也不尽相同。在我做这道题目的过程中，唯一的难点恰恰在如

2015-12-14 06:54:02 251

原创 POJ 3667 线段树区间合并

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=10354【解题报告】题目大意：长度为N的空位序列，有两种操作： 1.把连续的a个位置填满，如果有多种情况可以满足，选择最左边的。 2.把从a开始连续的b个位置清空这道题目非常类似动态区间最大和的解决方法。对于线段树的节点我们维护三个量： max_pre表

2015-12-14 03:55:19 223

原创 Codeforces 602B

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=284704【解题报告】给学弟挂的练习里面的一道题，一开始看错题了，以为要用尺取法做。吭吭哧哧写了近百行代码。后来看了题解才发现。这道题目严格规定a[i+1]-a[i]<=1(论读题的重要性)。题目是这样的：给定的序列，其中相邻元素的差值不超过1。求

2015-12-13 06:21:59 646

原创 UVa live 3905 扫描线

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16454【解题报告】为了学习线段树的扫描线算法，就特地来做一做扫描线的题目。题意很简单，一个二维平面，给一个固定的矩形，N个流星，每个流星给出初始坐标，和位移的矢量。求问矩形里最多能同时有多少颗流星。这道题目在《训练指南》中作为第一章的例题出现。我认为

2015-12-12 12:13:45 267

原创 hdu 1698 线段树区间修改

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=1698【解题报告】区间修改的模板题目。需要打一个set标记，表示区间（L，R）被修改为v. 在这道题目里。一开始所有结点被赋值为1，之后给Q个修改，把(L,R)修改为1,2，或3.最后求区间和。我的写法采用了刘汝佳在训练指南中使用的写法。【参考代码】#include<iostream>#

2015-12-10 04:49:31 311

原创 POJ 3468 线段树区间更新

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=14607【解题报告】区间更新模板题。操作： (L,R)区间增加V 查询：(L,R)的区间和【参考代码】#include<iostream>#include<cstdio>#include<cstring>using namespace std;t

2015-12-09 13:51:52 284

原创 POJ 3928 线段树单点更新+区间查询

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19613【解题报告】在《训练指南》上看到的这道题目，原题出在树状数组下，考虑到大部分树状数组可以做的题目线段树都可以做，虽然效率低一些，代码长一些，但好处在于维护更方便，扩展性也更强，所以还是用线段树来做这道题目。可能是最近手生，虽然题目很裸，仍然调了一个多小

2015-12-08 21:09:33 308

原创 HDU 5489（2015 Asia Regional Hefei Online F ）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5489【解题报告】题目大意是，在数组A中，删去连续的L个数之后的最长上升子序列（LIS）。为了解决这道题目，我们先来看LIS的nlogn求法：1.维护一个单调递增序列LIS2.对每个点A[i]，找到LIS里大于等于它的第一个位置，尝试把它插入到序列里第x个位置。（二分查找）那么dp[i]表示0

2015-12-08 00:21:02 317

原创求最长回文子串的manchester算法

珠玉在前，有讲解的很清晰的文章帮助读者来理解manchester算法是如何在线性时间内求得最长回文子串的。 http://blog.csdn.net/ggggiqnypgjg/article/details/6645824我觉得构思比较巧妙的地方在于1. 如何解决求长度为奇数和长度为偶数的回文串的算法的统一。解决方法是，引入没有出现在原串里的字符，变偶长回文串为奇长回文串。2.

2015-12-05 00:59:21 865 1

原创 UVa 1400（LA 3938）动态最大连续和

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36216【解题报告】刘汝佳的《训练指南》里，我觉得这道题目讲的不够详细（并且书上貌似有一点印刷错误？）。在网上找了很多题解，不过觉得代码写的很丑。直到我看到了这篇题解，觉得代码写的非常漂亮，就虚心学习了。 http://blog.c

2015-12-05 00:37:40 315

原创字符串单模板匹配学习笔记（一）kmp算法

【参考资料】先上链接：《字符串匹配的KMP算法》-阮一峰 http://kb.cnblogs.com/page/176818/《字符串匹配算法总结》 http://blog.csdn.net/WINCOL/article/details/4795369

2015-12-01 00:56:42 1336

原创 UVa 10891 （区间DP）

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19461【解题报告】题目大意：给你一个N元序列，每个元有一个分数，每次可以从左边拿或者从右边拿任意多。A，B轮流拿，拿完为止，求问A最多比B多拿多少。其中N<=100. 因为两个人都足够聪明，因此当他们任意一人面临一个(i,j)的局面时，因为

2015-11-28 10:44:59 314

原创 HDU 5245 joyful（ 2015 Shanghai Metropolitan J ）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5245【解题报告】题目大意：给你一个N*M个格子的矩阵，每次任意挑两个格子（可以相同）染色，一共染色K次，求被染色的格子的个数的期望。一道普通概率题，解题关键在于如何求一个格子在k次染色后不被染色的期望。现在我们来算第(i,j)个格子不被取中的概率易知 S1=（i-1）^2*N^

2015-11-21 23:31:58 424

原创 POJ 2186 Popular Cows（强连通分量缩点，Tarjan算法）

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16578【解题报告】【参考题解】 http://blog.sina.com.cn/s/blog_48f85e1d0100rzsw.html

2015-11-16 16:19:34 1386

原创 POJ 3710 Christmas Game（Tarjan+博弈SG函数）

【题目链接】 http://acm.hust.edu.cn/vjudge/problem/toListProblem.action#OJId=POJ&probNum=3710&title=&source=【解题报告】【参考资料】《组合游戏略述——浅谈SG游戏的若干拓展及变形》–贾志豪

2015-11-16 16:17:44 304

空空如也

空空如也