http://acm.hdu.edu.cn/showproblem.php?pid=1085 题意;一元的钱有num_1张，2元的钱有num_2张，5元的钱有num_5张，问最小的不能组成的钱是多少。 思路：有限个个数的母函数，并且不知道最好要多少，所以限制条件变成了不同种类钱的个数。统计0到num_1+2num_2+5num_5的方案数，第一个为0的就是答案。

http://acm.hdu.edu.cn/showproblem.php?pid=1398 题意：所有的货币都是平方数，比如1,4,9…问凑出n块钱有多少种办法。 思路：母函数。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年02月25日 星期四 22时15分31秒
 4File Name :code/hdu/1398.cpp
 5************************************************ */
 6
 7#include …

http://acm.hdu.edu.cn/showproblem.php?pid=1028 题意：求整数拆分数。 思路：母函数模板题。关于母函数的学习：http://www.cnblogs.com/syxchina/archive/2011/07/07/2197205.html http://www.cppblog.com/tanky-woo/archive/2010/08/02/121969.html

http://poj.org/problem?id=2926 题意：给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。 思路：拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626

题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。

思路：对曼哈顿距离进行变换。

先看曼哈顿距离的定义

|x1−x2|+|y1−y2|

阅读更多

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有 …

http://140.114.86.238/problem/10925/ Description 有兩個序列S1和S2，各有N個元素。當我們在S1,S2各取一個數字時，總共會有NN這麼多可能的”和”(sum)。請找出這NN這麼多和裡最小的N個值，並將它們加總後輸出。

http://acm.hdu.edu.cn/showproblem.php?pid=1575

题意：A为一方阵，求(A^k)73得到的矩阵的主对角线的和。

思路：矩阵快速幂。模板题。

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月21日 星期日 10时28分33秒
  4File Name :code/hdu/1575.cpp
  5************************************************ */
  6
  7#include …

http://www.lydsy.com/JudgeOnline/problem.php?id=2002

题意+思路： 同codeforces 13 E holes.

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年02月21日 星期日 02时29分39秒
  4File Name :code/bzoj/2002.cpp
  5************************************************ */
  6
  7#include <cstdio> …

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来

n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]….

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

http://www.lydsy.com/JudgeOnline/problem.php?id=3289

题意：中文题目，简单来说就是求某一区间内的逆序对数。

思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。

There are two types of problems solvable by partial sum.

1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).

Solution of all of this problems are the same. You just need to know how to solve one of them.

Example : You are asked some queries on an array …

http://acm.hdu.edu.cn/showproblem.php?pid=5416

题意：给出一棵树（n<=1E5），定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询（q<=10），每组一个s,问有多少对无序点对（u,v）满足f(u,v)=s. 思路：类似codeforces #340 div 2 E XOR and Favorite Number 先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍，统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);

http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意：问给出的区间[a,b]中有多少个美丽数，美丽数的定义是所有数字都不相同，如123是，100不是，333也不是。 思路：预处理1..100000的美丽数，可以把每个数字拆开放在set里，比较set的size和位数来实现。 然后用前缀和。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意： n+2个人取吃饭，每人w元，每k个人可以少付一个人的钱，问最后两个教练每人要付多少钱。

思路：贪心。坑点在读题。。选手n个人，不要忘记两个教练，以及，钱数是两个教练平分。

http://codeforces.com/contest/373/problem/C 题意：n个袋鼠，每个袋鼠的size为a[i],一只袋鼠的size至少是另一只两倍时才能将它装下，被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路：贪心。最多有n/2个袋鼠被装下。先排序，然后贪心即可。

http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给定一个序列，序列由1-N个元素全排列而成，求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路：增加一个元素，如果它两边的元素都出现了，那么段数-1（相当于把两段连接起来合并成了一段），如果两边元素都没有出现，那么段数+1.反过来，减少一个元素时，如果两边元素都出现了，俺么段数+1（相当于把完整的一段断开成两段），如果两边元素都没有出现，那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000，所以判断某个元素是否出现开一个100000大小的布尔数组即可（我竟然傻逼 …

http://codeforces.com/contest/614/problem/C

题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。 思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r,答案就是(R^2-R^2)*PI 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。

写了几道莫队，总结下。 目前只会区间莫队。。树上莫队以后再补。

莫队算法学习

说说我自己的理解： 莫队算法是一类用来处理离线静态区间问题的算法。 必须是离线，而且对区间没有修改。 还要满足，如果我们知道区间[l,r]的答案，那么知道区间[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案都是平凡的。。也就是O(1)可以实现才可以。