2017-Sp107-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，cjb读了E，交头接耳了一下，'''E1y9'''。yzc读了I，上机'''I1y32'''。sub读了H，上机'''H1y40'''。然后sub去推B的式子，cjb和yzc理论了一下A的情况，发现很sb，yzc上机写A，因为等比公式记不牢wa了一发，'''A2y52'''。cjb和sub理论了G，cjb上机'''G1y64'''。yzc和sub理论了J，yzc上机tle，改成维护一堆指针，'''J2y100'''。cjb思考了K，决定乱搞，上机顺利地'''K1y115'''。yzc和sub搞了F，上机爆搜打表，'''F1y152'''。三个人讨论B，突然发现可以分治FFT拆式子，cjb上机敲板子，sub和yzc理论C，sub上机写B，wa了之后调整了精度，'''B2y216'''。最后刚构造题C，'''C1y269'''。
== 总结 ==
=== chenjb ===
顺利得令人发指，真难过。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：只会是aaaaa...或者aaaabbbb，统计一下就好了。

 * B：写出式子，分治FFT求得多项式即可，注意式子的精度。

 * C：把n个东西两两分成一组，分到k-1组时，剩下都给第k组，直接枚举即可。

 * D：

 * E：排序，输出海明距离。

 * F：爆搜得到将1拆成k个1/ai的方案，得到每一种方案的ai的lcm，进行合理的去重之后，有效的lcm个数很少，暴力容斥。

 * G：首先第一次询问1/5e9得到a的正负性，然后在[0,1e9+5]范围内二分，考虑正弦函数图像，若query(pi/mid)*sign>0，则r=mid反之l=mid。

 * H：k从0往上枚举，每次求一个矩阵前缀和即可。

 * I：用map把三元组(首字母，尾字母，长度)映射到一个string的vector，模拟即可。

 * J：用sort后的数组将原数组分成几个区间，dp即可，注意到显然根号相等时n越大越好，于是只有根号种转移，用根号个指针维护决策点。

 * K：感受一下parameter会使得叶子数量往下降，写个gen生成对应的参数，询问的时候直接判断就好，实际上更加稳妥的情况下还应考虑度数，可取方差。
== 补题 ==

流水账

开场各自看题，cjb读了E，交头接耳了一下，E1y9。yzc读了I，上机I1y32。sub读了H，上机H1y40。然后sub去推B的式子，cjb和yzc理论了一下A的情况，发现很sb，yzc上机写A，因为等比公式记不牢wa了一发，A2y52。cjb和sub理论了G，cjb上机G1y64。yzc和sub理论了J，yzc上机tle，改成维护一堆指针，J2y100。cjb思考了K，决定乱搞，上机顺利地K1y115。yzc和sub搞了F，上机爆搜打表，F1y152。三个人讨论B，突然发现可以分治FFT拆式子，cjb上机敲板子，sub和yzc理论C，sub上机写B，wa了之后调整了精度，B2y216。最后刚构造题C，C1y269。

总结

chenjb

顺利得令人发指，真难过。

oipotato

subconscious

题解

  • A：只会是aaaaa...或者aaaabbbb，统计一下就好了。
  • B：写出式子，分治FFT求得多项式即可，注意式子的精度。
  • C：把n个东西两两分成一组，分到k-1组时，剩下都给第k组，直接枚举即可。
  • D：
  • E：排序，输出海明距离。
  • F：爆搜得到将1拆成k个1/ai的方案，得到每一种方案的ai的lcm，进行合理的去重之后，有效的lcm个数很少，暴力容斥。
  • G：首先第一次询问1/5e9得到a的正负性，然后在[0,1e9+5]范围内二分，考虑正弦函数图像，若query(pi/mid)*sign>0，则r=mid反之l=mid。
  • H：k从0往上枚举，每次求一个矩阵前缀和即可。
  • I：用map把三元组(首字母，尾字母，长度)映射到一个string的vector，模拟即可。
  • J：用sort后的数组将原数组分成几个区间，dp即可，注意到显然根号相等时n越大越好，于是只有根号种转移，用根号个指针维护决策点。
  • K：感受一下parameter会使得叶子数量往下降，写个gen生成对应的参数，询问的时候直接判断就好，实际上更加稳妥的情况下还应考虑度数，可取方差。

补题

附加文件