2019-Sp015-lyk

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

[http://10.71.10.90/pia/trac/wiki/2019-team2 返回Runespoor]
== 流水账 ==

签到题：A, B , E(代码复杂）

中期题：C , D , F （均有一定难度）

后期题：G， H

== 总结 ==

zqq: 今天我们签到期非常卡。A题我没有想清楚就上去写，所以调了很久，非常卡节奏。H题抄板子抄错了。还好有lyk写D，要不然就崩了

不太多过的题暴力还是不太好过的 @G





== 题解 ==
C ： 多项式技巧，求导，gcd，求根

D ： 凸包求并

E : 暴力+博弈dp

F : AC自动机+数位dp

G ： @jsb
题意：给出有 N=2k(k≤17) 个数的数组 ai。定义数组 bi 为：bi,j=aj⊕i。将这 N 个数组按字典序排序（一样就按编号排），输出最后的排列结果（编号）。多组数据。
　　做法挺巧妙的。有一个关键的性质是：bi,0∼2k+1−1这些数字是可以被 bi,0∼2k−1 和 bi⊕2k,0∼2k−1 顺次连接表示。这样我们就可以类似后缀排序一样做了：先按 bi,0 对每一个数组重分配权值，每次利用上一次结果的两段进行两次基数排序。

H : trie树后缀自动机

[http://acm.zju.edu.cn/pia/trac/wiki/2016-C10-team1 2016-team1]

== 补题 ==

G [zqq]: 后缀数组模板 + 改一下第二关键字位置 + 最后以下标作为第二关键字排序

返回Runespoor

流水账

签到题：A, B , E(代码复杂）

中期题：C , D , F （均有一定难度）

后期题：G， H

总结

zqq: 今天我们签到期非常卡。A题我没有想清楚就上去写，所以调了很久，非常卡节奏。H题抄板子抄错了。还好有lyk写D，要不然就崩了

不太多过的题暴力还是不太好过的 @G

题解

C ： 多项式技巧，求导，gcd，求根

D ： 凸包求并

E : 暴力+博弈dp

F : AC自动机+数位dp

G ： @jsb

题意：给出有 N=2k(k≤17) 个数的数组 ai。定义数组 bi 为：bi,j=aj⊕i。将这 N 个数组按字典序排序（一样就按编号排），输出最后的排列结果（编号）。多组数据。

　　做法挺巧妙的。有一个关键的性质是：bi,0∼2k+1−1这些数字是可以被 bi,0∼2k−1 和 bi⊕2k,0∼2k−1 顺次连接表示。这样我们就可以类似后缀排序一样做了：先按 bi,0 对每一个数组重分配权值，每次利用上一次结果的两段进行两次基数排序。

H : trie树后缀自动机

2016-team1

补题

G [zqq]: 后缀数组模板 + 改一下第二关键字位置 + 最后以下标作为第二关键字排序

附加文件