2017-Sp193-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，H是segment beats，让yzc上机写着。cjb读了A和sub讨论了一下，sub丢了个转化，cjb上机试图把log丢掉，后来发现很麻烦，大力sort，'''A1y38'''。yzc和sub讨论F，'''F1y40'''。yzc继续写H，wa了。cjb上机写C，'''C1y64'''。yzc上机拍H，re之后，cjb表示数组可能开小了，改大之后'''H3y81'''。cjb丢了个口胡的J给yzc，在sub帮助下，yzc上机写J，'''J1y126'''。之后cjb上机抄NTT，然后sub上机写I，写了许久，wa3很难受，cjb表示数组又可能开小了，改大之后'''I2y199'''。此前cjb和yzc讨论了G的性质，之后让sub推式子，'''G1y226'''。
== 总结 ==
=== chenjb ===
A题慌得一笔，直接上sort完事儿了...B要补补，不太懂树同构计数，这场几乎全都是计数题啊...ec是不是也要这样啊TAT
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：首先判定是否每种数字出现次数相同，然后把每种数字依次标记成目标序列中依次的下标，之后对于每个操作sort区间就可以判定了。

 * B：

 * C：f[mask]表示mask状态图的颜色数，预处理出所有独立集submask用来转移，O(3^n^)。

 * D：

 * E：

 * F：球的速度永远是sqrt(v^2^+2tC)，没有碰撞，直接计算即可。

 * G：奇数无解，偶数答案不超过2(把合法括号消掉后必然是一堆右括号接一堆左括号形式)，Ans0=卡特兰数，Ans0+Ans1/2=C(2n,n)，答案等于3*2^n^-2*C(n,n/2)，求组合数直接分解质因数即可。

 * H：Segment Beats! 维护区间最大最小值，支持cover和add，若区间sqrt(min)=sqrt(max)直接cover，如果sqrt(min)+1=sqrt(max)且min+1=max直接减掉定值，否则往两边递归。

 * I：首先将所有数从大到小排序，考虑排序后每一个数作为第k大贡献fk，那么fk=ΣC(I-1,k-1)*2^n-i^Ai，用FFT优化即可。'''sub：“相信会FFT的人都知道我在说啥。”'''

 * J：枚举中点x，遍历子树统计答案。

 * [http://www.cnblogs.com/duoxiao/p/5777703.html 多校题解]

流水账

出门各自看题，H是segment beats，让yzc上机写着。cjb读了A和sub讨论了一下，sub丢了个转化，cjb上机试图把log丢掉，后来发现很麻烦，大力sort，A1y38。yzc和sub讨论F，F1y40。yzc继续写H，wa了。cjb上机写C，C1y64。yzc上机拍H，re之后，cjb表示数组可能开小了，改大之后H3y81。cjb丢了个口胡的J给yzc，在sub帮助下，yzc上机写J，J1y126。之后cjb上机抄NTT，然后sub上机写I，写了许久，wa3很难受，cjb表示数组又可能开小了，改大之后I2y199。此前cjb和yzc讨论了G的性质，之后让sub推式子，G1y226。

总结

chenjb

A题慌得一笔，直接上sort完事儿了...B要补补，不太懂树同构计数，这场几乎全都是计数题啊...ec是不是也要这样啊TAT

oipotato

subconscious

题解

A：首先判定是否每种数字出现次数相同，然后把每种数字依次标记成目标序列中依次的下标，之后对于每个操作sort区间就可以判定了。
B：
C：f[mask]表示mask状态图的颜色数，预处理出所有独立集submask用来转移，O(3ⁿ)。
D：
E：
F：球的速度永远是sqrt(v²+2tC)，没有碰撞，直接计算即可。
G：奇数无解，偶数答案不超过2(把合法括号消掉后必然是一堆右括号接一堆左括号形式)，Ans0=卡特兰数，Ans0+Ans1/2=C(2n,n)，答案等于3*2ⁿ-2*C(n,n/2)，求组合数直接分解质因数即可。
H：Segment Beats! 维护区间最大最小值，支持cover和add，若区间sqrt(min)=sqrt(max)直接cover，如果sqrt(min)+1=sqrt(max)且min+1=max直接减掉定值，否则往两边递归。
I：首先将所有数从大到小排序，考虑排序后每一个数作为第k大贡献fk，那么fk=ΣC(I-1,k-1)*2^n-iAi，用FFT优化即可。sub：“相信会FFT的人都知道我在说啥。”
J：枚举中点x，遍历子树统计答案。
多校题解

附加文件

1.png by chenjb