2017-Sp135-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门yzc上机写K，wa了之后cjb上机'''C1y14'''，'''A1y16'''，之后yzc '''K2y17'''。cjb丢了D做法给yzc，之后'''D1y36'''。之后yzc和sub研究B，分类讨论了一波，'''B1y72'''。之后打了个表，cjb看了个规律丢给sub，sub上机努力了一下'''G1y91'''。之后三人一起搞H，yzc写完之后爆栈，之后改成非递归之后tle，预处理了一些东西还搞了读入优化，结果mle，无奈把读入优化去掉，'''H4y185'''。之后一起搞F，封榜后5min终于开始写，最后没能调过去，差一组样例过不去。最后7题 rk12，南大一队8题rk 8，感觉不太行，果然我们队不太擅长计数题md。
== 总结 ==
=== chenjb ===
今天我就负责签到，大力签了两个题，秒了个规律，然后字符串题不会做，图论题十分麻烦，只能看队友做计数题了呜呜呜。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：如果n是3的倍数，输出(n/3)^3^，否则如果是4的倍数，输出(n/2)*(n/4)*(n/4)，否则-1。

 * B：把每个串进行内部括号匹配之后，显然剩下的是连续的右括号+连续的左括号。感受一下，应该先拿左括号比右括号多的来进行操作，然后是一样多的，最后是右括号多的，对于三种分别举几个例子来思考排序关键字即可。

 * C：按pair<int,int>排个序，然后三个三个输出。

 * D：显然从左到右贪心取，考虑所有跨过i的约束条件，显然直接考虑l最小的区间即可，用个queue维护一下，然后线段树维护mex值即可。

 * E：cjb

 * F：观察无限序列的式子可以发现，所有下标%n同余的数字他们的值%n也同余，于是我们在一开始的序列中枚举两个同余的数字，计算出他们两个在A B中最早出现的数字相等的位置对，然后就是一个三个元素的积的前缀和的问题，拆开后分别用求和公式可以做到O(1)。

 * G：打表可得，每个数字出现的次数是2的因子的数量+1，二分求和即可。

 * H：可以感受到对于一个区间，最大值在实数序列里也是最大值，左右区间显然无关，分治得到左右区间的期望和概率之后合并即可。

 * I：cjb [https://github.com/zimpha/algorithmic-library/blob/master/StringUtility/lyndon-word-factorization.cc Lyndon-Factorization by Zimpha]

 * J：yzc

 * K：模拟。

 * [https://post.icpc.camp/d/816-2018-multi-university-training-contest-1-solution Official]

流水账

出门yzc上机写K，wa了之后cjb上机C1y14，A1y16，之后yzc K2y17。cjb丢了D做法给yzc，之后D1y36。之后yzc和sub研究B，分类讨论了一波，B1y72。之后打了个表，cjb看了个规律丢给sub，sub上机努力了一下G1y91。之后三人一起搞H，yzc写完之后爆栈，之后改成非递归之后tle，预处理了一些东西还搞了读入优化，结果mle，无奈把读入优化去掉，H4y185。之后一起搞F，封榜后5min终于开始写，最后没能调过去，差一组样例过不去。最后7题 rk12，南大一队8题rk 8，感觉不太行，果然我们队不太擅长计数题md。

总结

chenjb

今天我就负责签到，大力签了两个题，秒了个规律，然后字符串题不会做，图论题十分麻烦，只能看队友做计数题了呜呜呜。

oipotato

subconscious

题解

  • A：如果n是3的倍数，输出(n/3)3，否则如果是4的倍数，输出(n/2)*(n/4)*(n/4)，否则-1。
  • B：把每个串进行内部括号匹配之后，显然剩下的是连续的右括号+连续的左括号。感受一下，应该先拿左括号比右括号多的来进行操作，然后是一样多的，最后是右括号多的，对于三种分别举几个例子来思考排序关键字即可。
  • C：按pair排个序，然后三个三个输出。
  • D：显然从左到右贪心取，考虑所有跨过i的约束条件，显然直接考虑l最小的区间即可，用个queue维护一下，然后线段树维护mex值即可。
  • E：cjb
  • F：观察无限序列的式子可以发现，所有下标%n同余的数字他们的值%n也同余，于是我们在一开始的序列中枚举两个同余的数字，计算出他们两个在A B中最早出现的数字相等的位置对，然后就是一个三个元素的积的前缀和的问题，拆开后分别用求和公式可以做到O(1)。
  • G：打表可得，每个数字出现的次数是2的因子的数量+1，二分求和即可。
  • H：可以感受到对于一个区间，最大值在实数序列里也是最大值，左右区间显然无关，分治得到左右区间的期望和概率之后合并即可。
  • I：cjb Lyndon-Factorization by Zimpha
  • J：yzc
  • K：模拟。
  • Official
附加文件