这两天，在vjudge上找了一套曼谷的区域赛来做，大部分的题目都是很水的，有两道题完全没思路，剩余的几道都是稍微想一想就能出解的。
A.Volume Control
题目大意
对给出的n，求出所有不同的i×j，(0<=i,j<=n)
做法
这题最初并没有什么思路，n的范围是30000，时限是7s，所以我想有没有什么稍微暴力一点的方法。
首先想有没有可能从ans[i-1]推出ans[i]。
其实每多一个数i，增加数字一定都在i×j (j<=i)集合里。
那么这个集合里有多少是和之前重复的呢？
如果i×j和之前的重复了，那么必有i × j == s × t，其中s, t < i。
设i = a × b，s = p × a，t = q × b, (p < a, q < b)，则j = p × q。
因此，把所有满足j == p × q的j去掉，那么剩余的就是增加i后增加的个数。
通过枚举i的约数a，之后枚举p，q，即可得出所有的j。
注意在枚举a的时候，a是逐渐变大的，所以p的范围越来越大，q的范围越来越小。而且在枚举p，q的时候会有一些重复。
因此我们可以直接另p递增，而不是每次枚举约数a的时候都需要重新枚举。
B.Combination
知识点
打表找规律……
题目大意
给出l，r，求C(i,j)(l<=i<=r, 0<=j<=i)中奇数的个数。
做法
首先可以感觉到对每一个i，从C(i,0)到C(i,i)都要算，所以先对每一个i打一个sum(C(i,j))的表。
打表会发现从2^i开始就会重复出现之前的，而且从2^i到2^(i+1)的和是从2^(i-1)到2^i的和的三倍。
因此对整段的2^i到2^(i+1)直接累加，对两端的通过递归求解。
C.Mesh Cutter And D.Location
这两题看起来是两道计算几何，没有思路……
E.Zeroes
签到题。
题目大意
给出l到r求出对所有的l <= i <= r，i！的末尾的0的个数有几种不同的情况。
做法
可以发现，从l到r中有几个5的倍数就会有几个不同的0的个数。于是求出l和r-1中5的倍数的个数即可。
F.Fishing
知识点
简单的dp
题目大意
R × C (1 <= R, C <= 100)的矩阵，上面有个数，代表打鱼的收益，也代表放鱼失去的收益，然后现在规定：放两次鱼，打一次鱼，每次放鱼，都要求本次放鱼的ij均大于上次放鱼的ij，捕鱼也是这样，但是捕鱼和放鱼之间没有限制的联系。求这样的最大收益。不限制打渔次数。
做法
设f[i][j][k]是捕k次鱼，最后捕鱼的位置<=i，j的最大值，而g[i][j][k]是放k次放鱼，最后放鱼的位置<=i，j的最小值。两个状态转移方程相似，只不过一个是min一个是max。
|
|
最后求捕i次鱼同时放2×i次鱼的最大值即可。
G.Landmine Cleaner
知识点
推理。
题目大意
1000×1000的方块，每块有可能有一个‘L’标记，并且每一块可以算出来一个值：由它周围有效的9（包括自己）块推出来，如果它有就额外+3，然后9个中有几个L就+几，最大12.现在，给出一个有效状态的转化之后的方块，求出初始状态。
做法
显然从最左上的开始试着推，左上可以确定，然后（1,2）怎么搞？发现（1,1）（2，1）（1,2）（2,2）的总数因为（1,1）已经知道了，只剩（1,3）（2,3）两块了，又能够无视它定出来（1,2）。
然后想（1,3），虽然（1,3）还是能够定出来，但是（1,4）就不好弄了，关键是（2，x）的都不知道，重点来了：我们不妨把（2，x）同时确定下来，这样两行一块推。
（2,1）好定，（2,2）由于4个定了3个，这个发现也很重要，可以定（2,2），之后发现已经行了，因为之后的（1,3）可以定了，那么（2,3）呢？因为（1,2）周围定了5个，所以减一下就好了。
之后一直推完第一行，然后第三行，先把第二行信息弄掉就和刚才的一样了。
重点：首先试着去推，发现（1,4）不行去想（2，x），然后很重到的是（2,2）的减法，搞出来了，然后（1,3）之后（2,3）同样的减法。
群里某大神说高斯消元可做，但是并没有尝试去写……
H.Hidden Plus Signs
知识点
搜索。
###题目大意
30×30的方格，在一些方格中填1可以构成一个’+’号，它的长度只有可能是3、5、7、9、11，而且长宽相等，这些加号可以重叠，如果某一个格子有i个’+’号覆盖，那么这个格子的数字为i。不过每个加号的中心不能再其他加号上。求对于给出的矩阵，里面有多少个加号。最多不超过9个。
做法
由于加号数目较少，则可以通过枚举加号的中心来进行搜索。一个格子如果是加号的中心，那么他必须是’1’，而且他四周的数字必须都大于1。
I.The Programmers
知识点
裸的网络流。
题目大意
有p个人，s个参赛地点，每个参赛地点的容量为C，每个人只会去某几个地点参赛，问最多有几个人可以参赛。
做法
可以发现这是一个二分图，从源点向每个人连一条容量为1的边，从每个人向他想去的参赛地点连一条容量为1的边，从每个地点向汇点连一条容量为C的边，之后跑最大流即可。数据比较水，很快就能过。
J.Blanket
知识点
从数据范围小的入手，暴力。
题目大意
给出n个毯子，每个毯子长度无限，但是每a段是厚的，b-a段是薄的。有M个人坐标在0~M-1，问对每个人有几个毯子的厚的部分覆盖到了他。
做法
由于a，b很小(<=16)，所以直接暴力求出前16个的结果，后面的可以映射到前面。
K.Concert Tour
也是简单的dp。题目大概说的是有i个城市，每两个城市之间可以直接联通，花费给出，第i个月在地j个城市的收益也给出，求最大收益。
直接dp就好。
L.City
水题……想通了就很简单。
题目大意
有n×m块格子，每个格子可能与他上下左右四个格子连任意条边，现在给出每个格子的度，但是有一个格子未给出，求这个格子的度。
做法
这明显是一个二分图。二分染色后把两个集合的度之和相减即可得出。