这道题蛮有意思的..
可以考虑DP，这样来设计状态：
f(ma,mb,mc,n,q)表示a用了ma个1，b用了mb个1，c用了mc个1，当前到第n位，q∈{0,1}表示是否有进位
然后只需枚举当前位a取0，b取0、a取1，b取1、a取1，b取0这三种情况，根据q来判断mc需要增加多少和答案需要增加多少
[Noi2002]Robot
2015年7月14日 19:43
首先翻译下题意：
定义μ'(n) =
{
μ(n) (n = 1(mod 2))
0 (n = 0(mod 2))
}
第一问问n的约数中μ'(n)为1的的欧拉函数之和
第二问问n的约数中μ'(n)为-1的的欧拉函数之和
第三问问n的约数中μ'(n)为0的的欧拉函数之和
[HNOI2011]数学作业
2015年7月13日 22:07
这道题告诉我们快速幂没写对也是会导致WA的...
矩阵乘法模板题,
设A(x) =
(
10^x 1 0
0 1 1
0 0 1
)
(这什么鬼格式啊...哎呀不要在意细节(-ω-))
设B = (0 1 1)^T
1800: [Ahoi2009]fly 飞行棋
2015年7月13日 15:09
（BZOJ上数据范围太小了，这个题有O(n)做法）
首先可知矩形的对角线一定是圆的直径，而且任意两条直径一定可以确定一个矩形
只需求出圆的所有直径个数，任选两条即可(C(x,2),其中x为直径个数)
[Apio2010]特别行动队
2015年7月10日 21:20
这是道DP斜率优化的模板题啊...
首先很容易得出朴素的DP状态转移方程如下:
f(i) = max{f(j) + g(S(i) - S(j))} (0 < j < i)
其中，g(x) = a*x^2 + b*x + c , S(i) = Σ(k = 1,i)xk
展开、化简之后得:
f(i) = max(f(j) + a*S(j)^2 - b * S(j) - 2*a*S(i)*S(j)} + g(S(i))
[HNOI2008]玩具装箱toy
2015年7月09日 19:01
这道题貌似可以用斜率优化，不过不用也行，利用决策单调性同样可以设计出O(nlogn)的算法..
首先可以很容易得到朴素的状态转移方程:(f(x)表示只装前x个玩具的最优解)
f(x) = min{f(k) + cost(k + 1,x)}
其中,cost(i,j)为把[i,j]这个区间内的玩具装到一个箱子里的代价:cost(i,j) = (Sj - Si + j - i - T)^2
其中,Sx = Σ(i = 1,j)Ci，Ci即为第i个箱子的长度
我们可以很容易发现，对于j > i,若cost(k,j) > cost(k,i),那么一定有cost(k,j + 1) > cost(k,i)(原因是cost(k,x)的函数图像开口向上且只有一个极值),而对于j > i,也有若f(j) > f(i),那么f(j + 1) > f(i)(因为f(x)是由cost(i,j)定义的)
也就是说，若f(j)的最优决策是f(i),那么f(j + 1)的最优决策也是f(i)
