国庆集训-DAY1总结

Set : SuperOj887
刚好大于的选发和刚好小于的选法数是一样的,因此只需用总的选法数减去分数一样的选法数再除以二
设f(i,j)表示前i堆石子,两个人的选的数xor起来为j的选法数(显然分数一样的选法数为f(n,0))
 

[cqoi2013]二进制a+b

这道题蛮有意思的..
可以考虑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

 
首先翻译下题意:
定义μ'(n) = 
   μ(n)  (n = 1(mod 2))
   0     (n = 0(mod 2))
}
第一问问n的约数中μ'(n)为1的的欧拉函数之和
第二问问n的约数中μ'(n)为-1的的欧拉函数之和
第三问问n的约数中μ'(n)为0的的欧拉函数之和
 

[HNOI2011]数学作业

 
这道题告诉我们快速幂没写对也是会导致WA的...
 
矩阵乘法模板题,
设A(x) =
(
10^x   1      0 
0         1      1
0         0      1
)

(这什么鬼格式啊...哎呀不要在意细节(-ω-))

设B = (0 1 1)^T
 

1800: [Ahoi2009]fly 飞行棋

(BZOJ上数据范围太小了,这个题有O(n)做法)
首先可知矩形的对角线一定是圆的直径,而且任意两条直径一定可以确定一个矩形
只需求出圆的所有直径个数,任选两条即可(C(x,2),其中x为直径个数)
 

[Apio2010]特别行动队

 
这是道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))