http://acm.sgu.ru/problem.php?contest=0&problem=366
这题的意思就是每个东西有2个分量a和b，从N个东西里选K个东西，让这些东西的a分量之和A和b分量之和B，|A-B|最小，在此前提下A+B最大
N<=60000,K<=20,0<=a,b<=50
首先dp的话，要记录当前A-B为t的之后，A+B的最大值。。
暴力DP显然会挂。。优化了半天。。时间在SGU上居然第三: )
首先可以注意到对每个东西(a,b)可以用(a-b,a+b)来表示它，而由于最多选K个东西，所以当相同a-b的东西超过K个的时候。。显然除了a+b最大的那K个之外就没用了。。
所以总过最多也只有20*100=2000个东西。。
然后就差不多了。。Dp一下就可以了。。

http://acm.sgu.ru/problem.php?contest=0&problem=392
这题非常水。。但是居然只有24个人AC。。。囧。。。
看了题目之后。。。。显然我们只需要知道每个询问的hash值和每个位置开始特定长度的hash值就可以了。。
第一个可以快速幂。。第二个倍增掉。。
没了>_<

[Shoi2007]Bookcase 书柜的尺寸

Time Limit:5000MS  Memory Limit:65536K
Total Submit:21 Accepted:7
Case Time Limit:1000MS

Description

Tom不喜欢那种一字长龙式的大书架，他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面，这样需要查书的时候就可以不用起身离开 了。显然，这种书柜不能太大，Tom希望它的体积越小越好。另外，出于他的审美要求，他只想要一个三层的书柜。为了物尽其用，Tom规定每层必须至少放一 本书。现在的问题是，Tom怎么分配他的工具书，才能让木匠造出最小的书柜来呢？
Tom很快意识到这是一个数学问题。每本书都有自己的高度hi和厚度ti。我们需要求的是一个分配方案，也就是要求把所有的书分配在S1、S2和 S3三个非空集合里面的一个，不重复也不遗漏，那么，很明显，书柜正面表面积（S）的计算公式就是：

由于书柜的深度是固定的（显然，它应该等于那本最宽的书的长度），所以要求书柜的体积最小就是要求S最小。Tom离答案只有一步之遥了。不过很遗 憾，Tom并不擅长于编程，于是他邀请你来帮助他解决这个问题。

Input

文件的第一行只有一个整数n（3≤n≤70），代表书本的本数。接下来有n行，每行有两个整数hi和ti，代表每本书的高度和厚度，我们保证 150≤hi≤300，5≤ti≤30。

Output

只有一行，即输出最小的S。

Sample Input

4
220 29
195 20
200 9
180 30

Sample Output

18000

Source

Day2

哎。。回到正常状态了。。开始写解题报告>_<。。。
反正我现在感觉题目神马做多少都是浮云。。。也就那么几个核心思想>_<。。
首先这题自然要dp。。暴力dp记录每层显然不可能>_<。。dp自然需要一个序。。宽度显然不能为我们提供序>_<。。因为对于宽度的操作是和。。而和这玩意是对称的。。。
所以要找一个序。。。
1)Dp要有序。。。寻找序。。
2)神马是序呢。。一般来说是要先决定最重要的>_<。。而高度大的显然比较重要，所以按高度排序。。
那么状态就出来了。。Dp[i][w1][w2]表示前i个柜子，第一个层宽度和w1，第二个层宽度和w2。。
那么第三个层的宽度和也就是可以算出来。。
表示神马呢？表示三层每层最大值的最小和。
考虑第i个放入w1。。如果w1为0。那么由于后面的都比现在的小，第一层最大值就是第i个的高度。。
如果w1不为0.那么对最大值就没有影响。。
就可以做了>_<。。常数要优化一下。。。

NOIP果断悲剧。。。。
哎。。。最后一题我以为是搜索题>_<。。结果是DP。。。
我一通乱搜>_<。。死定了。。。
然后第二题我似乎常数写的好大啊。。。似乎要TLE  >_<。。。
哎。。。这次的题目太xx。。。大家都要400了。。就我要爆0 >_<。。。求鄙视 T_T。。。
哎。。最后春哥还是保佑我了。。。第二题虽然常数很大在我的机子上测各种TLE。。但是测评机非常强大还是让我A了。。。最后一题不知道怎么的在Windows上怎么测都70分测评机上却80囧。。。
我后来搞到了数据和程序发现还真这样。。。。。这。。我写的是确定性的卡时搜索啊真囧。。。
还有就是我还剩1个小时的时候发现第一题写错了囧。。幸好改过来了T_T
哎。。。太弱了。。球鄙视

RT

TC上变红了。。真高欣啊！！！！！！！！

额。。。上两次办“模拟赛”题目出的太狠。。以至于RP爆降。。为了给NOIP加RP。。我决定办场水水的模拟赛。。。难度跟去年一样（骗人我就去shi吧）。。。
见orzoj.org

何为数位过程类题目呢？（我瞎编的名词）
就比如说我和谐社会模拟赛的第一题（其实是SGU390）
跟数位有关。还是一个过程。。（汗一个）
题目一：
http://www.orzoj.org/ 上的father
解决这个题目的话。我们需要对这个题目究竟在干神马丽洁清楚。。
这个题目本质上是一个过程，从l进行到r，直接暴力模拟显然是会TLE的。
因此我们需要寻找一种加速的办法。
首先对于无规律的区间[l,r]显然很难加速。
注意到我们可以把区间[l,r]分解成一堆个数不超过O(LogR)的xxxxxx00000-xxxxxx99999这样的区间。。
同时我们可以发现xxx000-xxx999
可以分成10个更小的区间xxx000-xxx099+xxx100-xxx199….balabala
然后我们就可以考虑这个更加规范化的问题了。。
首先我们需要计算出一个子过程的结果，必须知道神马。。
考虑xxx000-xxx999
如果xxx都要知道，显然就知道的太多了～～
实际显然上xxx有意义的只有它的数位和。。于是需要知道一个prefix_sum。。
同时在前面的过程中，可能给现在的过程留下了一些票的价值。。rest
同时要知道序列的长度，都是10的幂次，用10的多少幂表示。。。pow
那么prefix_sum,rest,pow就可以确定一个状态，
计算一下。。发现空间够的。。
求解这个状态可以枚举从0到9一个个进行下一位。。
为了继续过程的进行，状态需要返回两个结果，一个是过程中的答案cnt，一个是剩下来的票数rest。。
接下就明了了。。自己想吧。。orzoj上面也有标程可以参考。。

题目二: SPOJ 2421. Incrementing The Integer
https://www.spoj.pl/problems/ININT/
这个题目的大意就是给两个数a和b，然后对于a可以让它加上它的一个数位。
比如123可以加上1或2或3
要用最少的次数到达b，同时要求方案数（mod一个大数）
看到这个题目。。。数据范围很大。。没法暴力。。。
运用上面的办法。。。我们考虑xxx000-xxx999这样的区间。。
首先开始的位置不一定是xxx000,也可能是xxx008。。所以需要知道开始位置
结束位置也一样。。从991-999。。。
同时如果我们xxx全都知道，显然知道的太多了～～
仔细一想。。其实只需要知道0-9这10个数位有没有出现过。。
0有没有出现过毫无用处。。。所以只要知道1-9是否出现。。有2^9个状态。。
然后用同样的办法分解成10个自区间。。一个个瞎搞过去。。
就差不多了yeah。。。

凑数的文章。。请鄙视。。
这个题目http://www.codeforces.com/contest/11/problem/E
看了一会儿没有感觉到可做性。。囧。。。
。。。然后研究别人的代码。。发现可以二分答案。。。
首先把连续的L和R之间先添上X。。
然后设Dp[i]是前i个数中，个数-长度*答案的最大值同时当前是L。。。。这个玩意非常NB。。
如果Dp[N]>=0那么当前的答案就是可行的。。
然后考虑Dp[i]。。有两个操作可以用，一个是前面+个X，一种是不加X直接搞。。
可以更新掉。。
然后二分乱搞。。。

////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
////////////////////////////我是分割线///////////////////////////////////
o(∩∩)o…哈哈。。你被耍了。。没有题解