<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[gungnir0711的博客]]></title><description><![CDATA[]]></description><link>https://blog.csdn.net/gungnir0711</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; gungnir0711]]></copyright><item><title><![CDATA[poj 3635 BFS 最短路变形]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50939296</link><guid>https://blog.csdn.net/gungnir0711/article/details/50939296</guid><author>gungnir0711</author><pubDate>Sun, 20 Mar 2016 22:15:51 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16131【解题报告】 
题意比较明确。给定N(N<=1000)个点的图，要求从S到E花费最少。 
其中每个点可以加油，给出每个点的油价。一个单位距离消耗一个单位油。车辆有最大储存油量。可以把这道题目理解为是一个二维的最短路，其中这个“路”在这里并不是两点之间距离，]]></description><category></category></item><item><title><![CDATA[HDU 1548 BFS入门]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50936204</link><guid>https://blog.csdn.net/gungnir0711/article/details/50936204</guid><author>gungnir0711</author><pubDate>Sun, 20 Mar 2016 13:22:04 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hdu.edu.cn/showproblem.php?pid=1548【解题报告】 
从A出发，问到B的最短路径。 
其实就是一个最短路问题。使用优先队列维护一下就好。不熟悉的人可能会用深搜去求解，不过暂时没想明白深搜会错到哪里，留个坑以后补。 
暂时远离ACM圈，以后随心情做点题，一切事情随缘吧。【参考代码】#include<iostream>
#includ]]></description><category></category></item><item><title><![CDATA[codeforces 589H DFS]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50742138</link><guid>https://blog.csdn.net/gungnir0711/article/details/50742138</guid><author>gungnir0711</author><pubDate>Thu, 25 Feb 2016 22:58:21 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106786#problem/D【解题报告】 
给定n个点和m条边的无向连通图，和k个特殊点，任意两个特殊点之间连一条路，任意一个特殊点不能是两条路的端点。问最多能连多少条路。 
这个题目我是不会的（图论思维真的很弱。。。）。 
这个题还是重点要学习怎么分析题目的。对于一个连通]]></description><category></category></item><item><title><![CDATA[CodeForces 589F 	二分答案]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50738336</link><guid>https://blog.csdn.net/gungnir0711/article/details/50738336</guid><author>gungnir0711</author><pubDate>Thu, 25 Feb 2016 15:50:22 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106786#problem/B【解题报告】 
这道题目对我来说关键在于读对题意。 
题意是： 
有n盘菜，每道菜有一段可以吃的时间。the gourmet想要吃完所有n道菜，并且每道菜花的时间相同并且尽可能长，问你能不能做到。如果可以，输出吃这n道菜的总时间。 
裸二分，二分]]></description><category></category></item><item><title><![CDATA[ZOJ 3582 概率DP]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50738275</link><guid>https://blog.csdn.net/gungnir0711/article/details/50738275</guid><author>gungnir0711</author><pubDate>Thu, 25 Feb 2016 15:43:32 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4624【解题报告】 
左右各有n个灯，灯亮的概率为P，是独立事件。且灯打开后就不会熄灭。 
问两遍各至少m个亮的期望。 
照例用递推。 
设dp[i][j]表示左边亮i个右边亮j个这个状态能够达到目标状态的期望。 
易知：dp[i][j]=sigma{   p*dp]]></description><category></category></item><item><title><![CDATA[POJ 2096 概率DP入门]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50737676</link><guid>https://blog.csdn.net/gungnir0711/article/details/50737676</guid><author>gungnir0711</author><pubDate>Thu, 25 Feb 2016 14:50:46 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21521【解题报告】 
一共有n种bug，s个系统，每天发现一个bug（一共有无限多个bug，bug的种类和属于哪个系统是独立随机事件），问至少找齐 
n种bug，每个系统至少找到一个bug的期望天数。我们使用递推的方法来解决这道题目。 
设dp[i][j]表示已]]></description><category></category></item><item><title><![CDATA[Codeforces 629C 简单DP]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50712607</link><guid>https://blog.csdn.net/gungnir0711/article/details/50712607</guid><author>gungnir0711</author><pubDate>Mon, 22 Feb 2016 01:27:27 +0800</pubDate><description><![CDATA[【题目链接】【解题报告】 
比赛的时候跑去做D了，这道题只是简单看了看，赛后补题把它补掉。这个题目只要想通了还是很水的。题意很简单，给你一个长度为m的串S，让你求不同的串P和Q的方案数使长度为n的串P+S+Q为一个合法括号序列。 
合法的括号序列要满足： 
1.左括号和右括号数量相同 
2.该串的任意一个前缀满足左括号数>=右括号数。那么我们设dp[i][j]表示长度为i的串，(比)多j个的方案数]]></description><category></category></item><item><title><![CDATA[Codeforces 521C 组合数取模（乘法逆元）]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50705666</link><guid>https://blog.csdn.net/gungnir0711/article/details/50705666</guid><author>gungnir0711</author><pubDate>Sat, 20 Feb 2016 18:34:07 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=106914#overview【解题报告】 
之前很少遇到组合数取模的问题（做题太少了)，所以就GG了……组合数取模这一问题在算法竞赛中还是很常见的，必须扎实掌握。 
回到这道题目来，你需要在n个数之间放k个加号，然后求出所有方案的和。 
我们知道正向思维，即求出所有的方案，然]]></description><category></category></item><item><title><![CDATA[HDU 5125 序列型DP]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50654209</link><guid>https://blog.csdn.net/gungnir0711/article/details/50654209</guid><author>gungnir0711</author><pubDate>Fri, 12 Feb 2016 05:20:58 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hdu.edu.cn/showproblem.php?pid=5125【解题报告】 
求A的最长上升子序列，其中A中至多有M个元素可以被B中同位置元素替换。 
考虑到数据范围只有1e3，所以完全可以用O(n^2)的方法来求LIS，但是由于有了B数组的加入，所以我们需要考虑Dp的状态要设置两个，一个是从上一个状态的a转移过来，一个是从上一个状态的b转移过来。 
所]]></description><category></category></item><item><title><![CDATA[HDU 1695&4135 容斥]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50615996</link><guid>https://blog.csdn.net/gungnir0711/article/details/50615996</guid><author>gungnir0711</author><pubDate>Fri, 12 Feb 2016 04:24:08 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hdu.edu.cn/showproblem.php?pid=4135http://acm.hdu.edu.cn/showproblem.php?pid=1695【解题报告】 
题目其实很简单，考虑到容斥需要的几个基本操作需要打熟练，就更新这么一篇blog上来。hdu4135很裸。给出一个N，求A,B区间内和N互素的数都个数。那么我们如果知道有多少数和N不互质，]]></description><category></category></item><item><title><![CDATA[UVa 11825 状态压缩DP]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50446324</link><guid>https://blog.csdn.net/gungnir0711/article/details/50446324</guid><author>gungnir0711</author><pubDate>Fri, 01 Jan 2016 23:19:30 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18913【解题报告】 
《训练指南》上状态压缩DP的例题。 
照样谈一些自己的体会。 
这道题目有一个地方是值得学习的，就是状态压缩之后如何枚举一个集合的子集。 
其他地方并没有什么难点。状态压缩之后的DP转移式很简单。#include<iostream>
#in]]></description><category></category></item><item><title><![CDATA[UVa 10603 BFS+优先队列]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50443767</link><guid>https://blog.csdn.net/gungnir0711/article/details/50443767</guid><author>gungnir0711</author><pubDate>Thu, 31 Dec 2015 21:21:18 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19527【解题报告】 
lrj紫书中路径寻找问题的例题。大部分细节书中都有说明，不再赘述。说一点自己的感想。 
书里面说算法的正确性不是显然的，可是我觉得应该是显然的吧？每次找到队列里dist值最小的状态，以它来更新ans值，并且拓展其他状态。 
假如当前我们找到]]></description><category></category></item><item><title><![CDATA[UVa 11134 贪心]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50436639</link><guid>https://blog.csdn.net/gungnir0711/article/details/50436639</guid><author>gungnir0711</author><pubDate>Wed, 30 Dec 2015 18:24:53 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34086【解题报告】 
题目大意： 
在N*N的棋盘里放N个车，使彼此不互相攻击（即不同行，不同列），每个车可以放在一个子矩阵里(给出矩阵左上角，右下角的坐标)，请给出任意一种放车的方案，如果不存在，输出”IMPOSSIBLE”。 
这题的贪心解法还是很值得认真体]]></description><category></category></item><item><title><![CDATA[POJ  3254  状态压缩DP]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50417353</link><guid>https://blog.csdn.net/gungnir0711/article/details/50417353</guid><author>gungnir0711</author><pubDate>Mon, 28 Dec 2015 10:28:57 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21819【解题报告】 
状态压缩dp入门题。 
因为一层最多只有12个节点，容易想到我们用一串二进制数表示它，然后映射到对应的十进制数上。 
那么我们可以一层一层的转移。 
这里转移的时候需要满足两个条件。 
一个状态j，需要满足！(j&(j>>2))。这说明，j]]></description><category></category></item><item><title><![CDATA[UVA 1451 单调队列]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50411292</link><guid>https://blog.csdn.net/gungnir0711/article/details/50411292</guid><author>gungnir0711</author><pubDate>Sun, 27 Dec 2015 07:13:28 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36267

【解题报告】 
题目大意： 
    给你一个长度为N的01串，求长度>=L的子串中，含有1的个数比子串长度最大的子串的左右端点。 
    简单来说，就是假如我维护一个前缀和sum[i]表示前i个数中1的个数，那么求最大的( sum[i]-sum[]]></description><category></category></item><item><title><![CDATA[HDU 3507 斜率优化]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50411275</link><guid>https://blog.csdn.net/gungnir0711/article/details/50411275</guid><author>gungnir0711</author><pubDate>Sun, 27 Dec 2015 05:31:23 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hdu.edu.cn/showproblem.php?pid=3507【解题报告】 
花了两天时间，终于搞懂了斜率dp是怎么维护数据的，感觉自己理解力实在是弱的同时，也感叹确实难找到好的题解，有的题解甚至是错误的，比如百度这道题里面非常靠前的一篇blog，讲解思路混乱，同时给出了一个错误的结论：维护一个上凸点集。真不知道，他是如何在代码里维护的事下凸点集的情况里]]></description><category></category></item><item><title><![CDATA[POJ 2823 单调队列入门题]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50407272</link><guid>https://blog.csdn.net/gungnir0711/article/details/50407272</guid><author>gungnir0711</author><pubDate>Sat, 26 Dec 2015 05:38:38 +0800</pubDate><description><![CDATA[【题目链接】 
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=16694【解题报告】 
这题是可以用优先队列做的，这样会简单一些，不过考虑到是为了熟练的掌握斜率优化这一技巧，所以特意通过做这道题目来熟悉单调队列的基本用法。因为考虑到单调队列是从队尾插入，访问队首元素。所以使用了双端队列这一STL。虽然要比手写的模拟队列要麻烦一]]></description><category></category></item><item><title><![CDATA[和中位数有关的构造]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50391716</link><guid>https://blog.csdn.net/gungnir0711/article/details/50391716</guid><author>gungnir0711</author><pubDate>Thu, 24 Dec 2015 04:40:50 +0800</pubDate><description><![CDATA[【题目链接】 
http://www.lydsy.com/JudgeOnline/problem.php?id=1303

【解题报告】 
思路比较巧妙，重新定义数组，比b大的数设为-1，比b小的数设为1。 
为什么可以这么想呢？对于中位数而言，我们只关心这个连续序列里有多少个元素比他大，而不关心比他大多少，即比他大的数无论怎么排列都没有关系。 
也即，数列里的数只有三个性质：大于b，小于b，等于]]></description><category></category></item><item><title><![CDATA[Codeforces Round# 180 div2]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50384151</link><guid>https://blog.csdn.net/gungnir0711/article/details/50384151</guid><author>gungnir0711</author><pubDate>Wed, 23 Dec 2015 06:25:11 +0800</pubDate><description><![CDATA[【题目链接】 
http://codeforces.com/contest/298

这场比赛做的还可以，1hA了两道题，2h的时候做出来第三道。没有想到这场出的都是想法题。尤其是E题，确实是很考构造能力的。 
官方题解在此，十分清楚。 
http://codeforces.com/blog/entry/7437]]></description><category></category></item><item><title><![CDATA[codeforces 289B 递推]]></title><link>https://blog.csdn.net/gungnir0711/article/details/50376059</link><guid>https://blog.csdn.net/gungnir0711/article/details/50376059</guid><author>gungnir0711</author><pubDate>Tue, 22 Dec 2015 01:57:22 +0800</pubDate><description><![CDATA[【题目链接】 
http://codeforces.com/problemset/problem/289/B【解题报告】 
CF round 177 div2. 
题目大意，给你一个N*M的矩阵，里面每个元素有一个val，你可以每次对它+d或者-d，问至少需要多少次操作，使得所有元素val相同。如果不可能，输出-1. 
这道题做比赛的时候wa了五次。想对了一点，就是给定的n个数一定是模d的剩余相同。]]></description><category></category></item></channel></rss>