对于构成最小环的点集{x1, x2, …}，其中必定存在一个最大点xk，那么最小环的长度可以由dis[i][j]+m[j][xk]+m[xk][i]来表示，其中i，j均在点集中且小于xk，dis[i][j]是i到j的最短路径。因为xk是点集中最大的那个点，所以i到j的最短路径没有经过编号比xk更大的点。那么要求最小环的长度就可以由小到大枚举一下xk就行了。我们知道，floyd算法最外层每循环一次，就是由一个中间节点k更新点i到j的最短路径。k从小到大枚举，就保证了循环到k的时候，当前i到j的最短路经过的最大节点只可能是k，这刚好满足上面提到的dis[i][j]的定义。所以我们就可以愉快的使用floyd来求最小环了。
背景 Background
一阵狂风吹过
只听“pong”的一声，飘飘乎居士降落了！！！
描述 Description
又是美妙的一天，这天飘飘乎居士要和MM约会，因此他打扮的格外帅气。但是，因为打扮的时间花了太久，离约会的时间已经所剩无几。
幸运的是，现在飘飘乎居士得到了一张nm的地图，图中左上角是飘飘乎居士的位置，右下角是约会的地点。‘.’代表马路，‘’代表房屋。飘飘乎居士只能沿着‘.’行走（也就是不能踏入‘’），而且行走的方向只能为上下左右的相邻格子。为了不让MM等待太久，飘飘乎居士在整个过程中可能会使用一次飘飘神功（也可能不使用，但最多使用一次），使用飘飘神功后，飘飘乎居士可以走进房屋一次（也就是在全程的行走中最多可以走一个‘’,注意，只有一个）；
现在飘飘乎居士想要知道最少需要走多少步，飘飘乎居士才能到达约会的地点。
Continue reading
描述 Description
某一天在网上闲逛的玖君不小心发现了TYVJ，就立刻被TYVJ吸引住了，果断驻扎下来。玖君决定按照顺序来切题，因为离复赛越来越近了，所以他希望能够用最短时间AC掉前面N道题目，完成第i道题目玖君需要花费t[i]个单位的代价。玖君做题有个特点，他喜欢看完几道题后，一次把几道题的代码写完。如果玖君决定一次写完从编号L到编号R的题目，那么他完成这些题目的总代价等于编号L到R题目的代价之和与R之积，即SUM{t[L..R]} R。此外每道题在被切之前都会等待被切，等待的时间，也被算在代价里面，对于每个第k次被切的题，在它被切之前的等待代价为(k-1)S。综上，切完N道题的总代价=第1次切题的代价+第2次切题的代价+…+第k次切题的代价+每道题的等待代价。现在我们想知道玖君切完这N道题目的最小代价。
Continue reading
这两道题都是从我开始接触tyvj的时候就看过的，可是一直没去写，今天终于。。。
P1064 - 新三国争霸
描述 Description
PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。
PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他秒要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。
因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。
N<=300，M<=5000 ，T<=50；
Continue reading
描述 Description
ForeverBell不仅精通破译密码,更是我军的重要代码编写者(至于什么代码,自己想吧).战争的日子是无聊的,有一天,ForeverBell找到了treeboy,出了一个极其简单的问题:给定一段序列,找出这段数列中第k小的数.
为了照顾treeboy的超弱语文水平,ForeverBell极其耐心地解释了这个问题:给定一个整数数列num[1…n],序列中的每个数字都不相同.你需要回答一组格式为Q(i,j,k)的查询,表示”在num[i…j]中第k小的数是多少”.
由于treeboy不仅语文差,而且代码能力巨弱,所以再次找到了你,请你编写一个程序,应对ForeverBell的询问.
输入格式 InputFormat
第一行两个整数n,m.分别是数列的总长度和ForeverBell询问的次数. 1≤n≤100 000，1≤m≤5 000
第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过10^9 。
接下来有m行，每行三个整数i、j、k，代表一次查询，i、j、k满足：1≤i≤j≤n， 1≤k≤j-i+1。
输出格式 OutputFormat
一共m行.第i行表示第i次询问的答案.
样例输入 SampleInput [复制数据]
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
样例输出 SampleOutput [复制数据]
5
6
3
这道题算是模版题吧，看了一下说是什么划分树，不懂。。。然后就百度了一下，然后发现百度上的模版直接就能用了，然后就学习了一下，然后我打算把百度百科上的说明copy下来这里方便查阅。。。
Continue reading
我应该怎么说这道题好呢，只能怪自己英语没有学好吧T^T，为什么造福小众，我决定不翻译题意了，大家自己看吧。。。。
Continue reading
经典问题，RMQ，不过为了增加一下文章长度，我打算贴一下题目
Continue reading
本来说好的每日一题解，因为下午睡了一觉醒来发现已经快十点了，然后才开始做题。。然后发现现在已经过了十二点了。。。
题目可以在这里看：传送门
然后这可以说是一道陈年老题了，我从高中的时候就打算要写，然后一直拖到现在-_-#，根据题意很容易想到可以用并查集来解决，我们可以添加一个节点0，然后有毒的水果都合并到0，然后最后统计一下有多少水果是有毒的就行了。
Continue reading
题目大意：给你一个N (0 < N < 10^5)，把N分解成若干个不相同且值不超过10^5的整数的各个位数的和，例如：N＝17时有，17 ＝ 7 ＋ 1 ＋ 2 ＋ 4 ＋ 3，所以17可以分解成7， 12， 43，这三个不同的整数。
题目其实是比较简单的，解法也有很多种，我就说一个我认为比较有趣的解法。我们可以每次把N加到所求的整数集合里面，然后再把N减去自身各位数字的和得到新的N’，直到N等于零。正确性也很容易验证，注意到我们每次往集合里添加的数必然都是递减的，这就保证了无重复数字的出现，然后按照生成的规则可知，减到N为0的时候自然集合里的所有数的各位数字之和就为最初的N了。
Continue reading
博客好久没有更新了，自从打完补选赛之后就一直一副颓废状态，外加要期末考，得预习课内知识(虽然我到最后还是。。。)，不管怎么样，现在以及放假了，所以我打算兑现之前对自己的承诺，暑假好好做题，所以这段时间应该会比较经常更新一些水题的题解啦( ´ ▽ ` )ﾉ。昨天选拔赛第一场就爆零滚粗，作为一名候补选手，我只剩下今天这个最后一次机会了，好伤感的说T^T，希望写一写题解涨张RP。。。
Continue reading
Write the code. Change the world
Student