国庆集训-DAY1总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
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以内枚举。
评论 (0)
