2019-team666-0017

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

[[Image(Submissions.jpg,1000px)]]

== 流水账 ==

开场疯狂自闭，到一个小时左右陆续有了B和E的做法，hyw上机写E，没过样例，换tjc写B，'''B1y97'''，yyc接着写A，hyw看出了E的改法以后就和tjc开题，C、G没有开出来，D题一开始卡着后来tjc发现了性质，但还是有一个瓶颈无法实现。yyc一开始写挂了，后来发现dfs序写错调了十多分钟，'''A1y194'''。hyw改E，发现仍有几个细节没有发现还需要继续改，改了一会儿过了，'''E1y229'''。最后yyc写H，wa了3发t了1发，始终看不出为什么超时，没有改完。


== 总结 == 


=== yyc ===

不会写代码*4

=== tjc  ===

B题想到unr3百鸽笼，然后发现不可能求出每个数第几个减到0的概率，于是直接照着期望的线性性想，就做出来了

广义sam好难啊 我要学习一个

=== hyw  ===

这场肝出了E，爽。

然后就是B题真巧妙，队友牛逼。

第一次0dirt场，撒花。

开场开题还可以再快一点。

以及F的复杂度其实是可以过的，以后对于那种算出来大概1e9或者1e8量级的运算量并且超一点点时限的题可以考虑杠一下，有的时候就过了。

=== 题解 ===

A:路径上的点贡献为0，lca子树里的点和子树外的点分类讨论，子树外的点预处理，子树里的点的贡献=lca点的答案和-路径上的编号和+lca的编号和。

B：一个数x排名的期望=\sum_{别的数y} y在x之前变0的概率

然后对于两种数x和y 可以dp出只有xy这两个数的情况下 x在y之前结束的概率

再统计出每种数出现的次数cnt[]

对于值为x的数，答案为1+\sum_{y!=x}{cnt[y]*f[y][x]}+(cnt[x]-1)*f[x][x]

C: 对f(x)和f'(x)求gcd，多项式辗转相除，然后就可以得到所有次数大于1的多项式因子，再用多项式除法求剩下的。

E：博弈+dp+状压，必胜态和必败态一定是连续的区间，设dp[i]和bp[i]表示当前牌mask为i，必胜/必败态的区间（是若干个区间的并，用一个map或者set维护一下），所有能转移到必败态的就是必胜态，即考虑往当前牌的集合里加一张牌，所有必败态区间两端点乘上加入牌的点数得到的区间的并就是新的必胜态区间，注意区间必须是左闭右开保存（否则会漏掉一些情况）。区间合并直接遍历map就可，具体做法是设一个计数器初始为0，遇到左端点++，右端点--，注意如果一个点是多个区间的端点要加或减多次。然后加之前计数器为0的左端点和减之后计数器为0的右端点就是要保留的点，其他点都可以删去。实现中只要维护必败态，必胜态可以把必败取补集得到。注意爆inf。（细节多到爆炸）

[/wiki/2019-team666 返回]

概述

流水账

开场疯狂自闭，到一个小时左右陆续有了B和E的做法，hyw上机写E，没过样例，换tjc写B，B1y97，yyc接着写A，hyw看出了E的改法以后就和tjc开题，C、G没有开出来，D题一开始卡着后来tjc发现了性质，但还是有一个瓶颈无法实现。yyc一开始写挂了，后来发现dfs序写错调了十多分钟，A1y194。hyw改E，发现仍有几个细节没有发现还需要继续改，改了一会儿过了，E1y229。最后yyc写H，wa了3发t了1发，始终看不出为什么超时，没有改完。

总结

yyc

不会写代码*4

tjc

B题想到unr3百鸽笼，然后发现不可能求出每个数第几个减到0的概率，于是直接照着期望的线性性想，就做出来了

广义sam好难啊 我要学习一个

hyw

这场肝出了E，爽。

然后就是B题真巧妙，队友牛逼。

第一次0dirt场，撒花。

开场开题还可以再快一点。

以及F的复杂度其实是可以过的，以后对于那种算出来大概1e9或者1e8量级的运算量并且超一点点时限的题可以考虑杠一下，有的时候就过了。

题解

A:路径上的点贡献为0，lca子树里的点和子树外的点分类讨论，子树外的点预处理，子树里的点的贡献=lca点的答案和-路径上的编号和+lca的编号和。

B：一个数x排名的期望=\sum_{别的数y} y在x之前变0的概率

然后对于两种数x和y 可以dp出只有xy这两个数的情况下 x在y之前结束的概率

再统计出每种数出现的次数cnt[]

对于值为x的数，答案为1+\sum_{y!=x}{cnt[y]*f[y][x]}+(cnt[x]-1)*f[x][x]

C: 对f(x)和f'(x)求gcd，多项式辗转相除，然后就可以得到所有次数大于1的多项式因子，再用多项式除法求剩下的。

E：博弈+dp+状压，必胜态和必败态一定是连续的区间，设dp[i]和bp[i]表示当前牌mask为i，必胜/必败态的区间（是若干个区间的并，用一个map或者set维护一下），所有能转移到必败态的就是必胜态，即考虑往当前牌的集合里加一张牌，所有必败态区间两端点乘上加入牌的点数得到的区间的并就是新的必胜态区间，注意区间必须是左闭右开保存（否则会漏掉一些情况）。区间合并直接遍历map就可，具体做法是设一个计数器初始为0，遇到左端点++，右端点--，注意如果一个点是多个区间的端点要加或减多次。然后加之前计数器为0的左端点和减之后计数器为0的右端点就是要保留的点，其他点都可以删去。实现中只要维护必败态，必胜态可以把必败取补集得到。注意爆inf。（细节多到爆炸）

附加文件