2020-team12-030

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-huaweiday2standing.png, 1000px)]]



== 问题 ==

我们的问题就是菜。

还有，感觉是个数学+卡常场...

很多题目现场证明其需要的引理几乎不可能，因此写暴力或者小dp打表找规律还是最重要的技巧，对于数学题、博弈sg函数题都十分重要，发现只凭人脑思考无果就不能犹豫。。

== 题解 == 

A:暴力+卡常，循环展开大法好。

B: 问题转化为你和tourist共同面对一个子集，如果同样选到某个题则获得（原集合-这个题）的子问题得分，否则就得到这个题的得分。

考场时注意到tourist是主动的一方，显然他会分配概率使得你做什么策略的结果都尽可能接近，于是whn想着先写个O(2^n^ n^3^)的高斯消元然后在优化，结果发现高斯消元就是错的...

事实上，由于tourist分配每道题的概率上限是1，所以他更多时候与样例不同，是不能让你的决策彻底没用的。

其实每个问题可以看成一个一次函数（线段），如果tourist在上面不分配概率则你选他得到的期望得分即为此题得分，如果分配1的概率就是除此问题之外的子问题得分，构成一个一次函数；tourist的策略是，最小化这n个函数的最大值；而我们的最优策略显然是无脑就选那个最大值的题。

然后就是贪心，考虑以线段左端点为关键字倒着排序，每次贪心分配概率使得最大值最大的函数取到最大值次大函数的最大值，然后可以合并两个函数，因为此后要同时对这两个问题分配概率。（斜率合并需要仔细计算，结论是当已经合并了num个函数斜率为k,下一个函数斜率为k0,则新函数斜率为调和平均数1/(num/k+1/k0)).复杂度O(2^n^ n)，写成记忆化会被卡常。


C:答案是phi(n)*C(n-1,k-1)。正解给出了一段很复杂的证明，证明了必须要有一个与n互质的数a出现超过一半次，剩下的数为模n意义下的a的倍数，总共不能超过a的n倍。

我想比赛时能做的就是写个暴力打表找规律……

还有就是看到n<998244353的数据要想到打表阶乘……

D:听说是出题人认为最简单的一道题可过的人很少。待补。

E:待补

F: 不可做

G:每个质数可以拆开考虑，然后我们发现连续的一段n个有质因子p的数，其sg值和普通的取石子一样是n（因为你不管怎么从中间选区间异或值都不会超过n)

因此就每个数筛质因数就行。但是题目不仅需要pollard-rho,还需要常数极好的pollard-rho...去洛谷找板子了...

H: 

I: 沈哲贝写了个平衡树，卡常过了。正解好像是dp

J: 简单题

K:

L: 考试期间想到我们可能要在只剩下红或蓝的结果之前一直下注eps的错误结论...

正解答案是2^(B+R)^/C(B+R,B)。 这可以这样理解：考虑到最终序列有C(n,k)种，我们把钱均分成C(n,k)份，然后每次第i轮有多少个序列是红/蓝就下多少到红/蓝（可以抵消），最后我们会输完

（题解说可以写dp，但是我觉得这个结论想不到也就很难能写dp?)。

现在问题在于B，R的1e12范围和Extreme Wealth判断。

这需要用到斯特林公式(n!=sqrt(2*\pi*n) * (n/e)^n^)或者wallis公式（通过求积分sin^(2k-1)^x,sin^(2k)^x, sin^(2k+1)^x然后相除，先对于B，R中较小的(假设是B）求出2^(B+B)^/C(2B,B)，然后发现

2^(B+B+1)^/C(2B+1,B)=2^(B+B)^/C(2B,B)*(2(B+1)/B+B+1),理论上可以通过估算发现2(B+i)/B+(B+i)连乘sqrt(B)次会至少翻两倍，因此sqrt(B)log1e9次以内就会得到extreme wealth.

但由于题目卡常，所以得设置一个差不多在这附近的参数，特判超过这个次数就直接extreme wealth才能过...

M:签到题，但这个看似要求离散对数的题目把玄机（范围内的最大值藏在样例）里的做法实属初见。。

[/wiki/2020-team12 返回]

问题

我们的问题就是菜。

还有，感觉是个数学+卡常场...

很多题目现场证明其需要的引理几乎不可能，因此写暴力或者小dp打表找规律还是最重要的技巧，对于数学题、博弈sg函数题都十分重要，发现只凭人脑思考无果就不能犹豫。。

题解

A:暴力+卡常，循环展开大法好。

B: 问题转化为你和tourist共同面对一个子集，如果同样选到某个题则获得（原集合-这个题）的子问题得分，否则就得到这个题的得分。

考场时注意到tourist是主动的一方，显然他会分配概率使得你做什么策略的结果都尽可能接近，于是whn想着先写个O(2n n3)的高斯消元然后在优化，结果发现高斯消元就是错的...

事实上，由于tourist分配每道题的概率上限是1，所以他更多时候与样例不同，是不能让你的决策彻底没用的。

其实每个问题可以看成一个一次函数（线段），如果tourist在上面不分配概率则你选他得到的期望得分即为此题得分，如果分配1的概率就是除此问题之外的子问题得分，构成一个一次函数；tourist的策略是，最小化这n个函数的最大值；而我们的最优策略显然是无脑就选那个最大值的题。

然后就是贪心，考虑以线段左端点为关键字倒着排序，每次贪心分配概率使得最大值最大的函数取到最大值次大函数的最大值，然后可以合并两个函数，因为此后要同时对这两个问题分配概率。（斜率合并需要仔细计算，结论是当已经合并了num个函数斜率为k,下一个函数斜率为k0,则新函数斜率为调和平均数1/(num/k+1/k0)).复杂度O(2n n)，写成记忆化会被卡常。

C:答案是phi(n)*C(n-1,k-1)。正解给出了一段很复杂的证明，证明了必须要有一个与n互质的数a出现超过一半次，剩下的数为模n意义下的a的倍数，总共不能超过a的n倍。

我想比赛时能做的就是写个暴力打表找规律……

还有就是看到n<998244353的数据要想到打表阶乘……

D:听说是出题人认为最简单的一道题可过的人很少。待补。

E:待补

F: 不可做

G:每个质数可以拆开考虑，然后我们发现连续的一段n个有质因子p的数，其sg值和普通的取石子一样是n（因为你不管怎么从中间选区间异或值都不会超过n)

因此就每个数筛质因数就行。但是题目不仅需要pollard-rho,还需要常数极好的pollard-rho...去洛谷找板子了...

H:

I: 沈哲贝写了个平衡树，卡常过了。正解好像是dp

J: 简单题

K:

L: 考试期间想到我们可能要在只剩下红或蓝的结果之前一直下注eps的错误结论...

正解答案是2(B+R)/C(B+R,B)。 这可以这样理解：考虑到最终序列有C(n,k)种，我们把钱均分成C(n,k)份，然后每次第i轮有多少个序列是红/蓝就下多少到红/蓝（可以抵消），最后我们会输完

（题解说可以写dp，但是我觉得这个结论想不到也就很难能写dp?)。

现在问题在于B，R的1e12范围和Extreme Wealth判断。

这需要用到斯特林公式(n!=sqrt(2*\pi*n) * (n/e)n)或者wallis公式（通过求积分sin(2k-1)x,sin(2k)x, sin(2k+1)x然后相除，先对于B，R中较小的(假设是B）求出2(B+B)/C(2B,B)，然后发现

2(B+B+1)/C(2B+1,B)=2(B+B)/C(2B,B)*(2(B+1)/B+B+1),理论上可以通过估算发现2(B+i)/B+(B+i)连乘sqrt(B)次会至少翻两倍，因此sqrt(B)log1e9次以内就会得到extreme wealth.

但由于题目卡常，所以得设置一个差不多在这附近的参数，特判超过这个次数就直接extreme wealth才能过...

M:签到题，但这个看似要求离散对数的题目把玄机（范围内的最大值藏在样例）里的做法实属初见。。

附加文件