背景 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

传送门：题目
怎么说呢，水题一道，直接用小根堆解决
主要是想通过这道题学习C++STL里面heap的用法
最后还是没有纠结出来，然后发现手写也不会了，就在网上找了一段，挺简洁的，以后就用这个做模板
Continue reading

这道题显然有，矩阵乘法可解（由数据范围可得）

显然有题目要求: f[n]=∑f[i] (n-k<i<n-1),矩阵乘法相关知识自行google，推荐阅读Matrix67写的一篇文章。

所以构造有数组A(k*k):

000…1

100…1

010…1

001…1

因为看k<10,我们可以先计算出f[1]~f[k],然后用矩阵乘法加速，计算出A^(n-k),最后再f*A^(n-k)乘一下就得出了。

我用的是递归式的矩阵二分取幂，后来才知道这样写会显得你很弱智……我也不知道为什么，然后就顺便再复习了一下，快速幂的非递归写法。
Continue reading

☆打鼹鼠
SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊……),于是便无聊地开始玩“打鼹鼠”……
描述 Description
在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为n(n<=1024)的正 方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。而 SuperBrother也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。
Continue reading