国庆集训-DAY1总结

Set : SuperOj887
刚好大于的选发和刚好小于的选法数是一样的,因此只需用总的选法数减去分数一样的选法数再除以二
设f(i,j)表示前i堆石子,两个人的选的数xor起来为j的选法数(显然分数一样的选法数为f(n,0))
 
可以得到如下递推式:
f(i+1,j) = f(i,j) //新的一个两个人都不选
         + f(i,j xor a(i + 1)) //新的一个A选
         + f(i,j xor a(i + 1)) //新的一个B选
然后就可以得到答案是((3^n) - f(n,0))/2
 
Clique : SuperOj888
一个图的最大团等于其补图的最大独立集
因此只需求出其最大独立集
这个是问题是NP的,搜索即可
 
 
HCN : SuperOj889
高精度反素数..采用和普通反素数一样的搜索,外加剪枝
对于枚举到的某一个素数ai,我们可以求出其上界maxi和下界mini
为了求出反素数,我们希望其约数个数最大且值最小
设k = max{k | ai >= 2^k}
假设ai选了pi个,那么若此时选(pi-1)个ai并选多选k个2,此时值显然减小了,因此我们希望约数个数增大
设本来选了c个2
于是有:(pi-1+1)*(c+k+1) <= (pi+1)*(c+1)
解之可以得到pi的一个边界
(下界也可以通过一个不等式解得,不过不管下界也行,因为大多数数的下界都是0)
另外还有一个超强的剪枝:初始个数(2的个数)只需要在1~12以内枚举。