2017-Sp241-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

XIV Open Cup named after E.V. Pankratiev. GP of Kharkiv
== 流水账 ==
出门各自看题，上了个E，先re再wa，sub上了个A，'''A2y43'''。cjb上了个假G，然后yzc '''E4y57'''。之后sub给了G的做法给yzc，结果tle了，卡不过去。cjb抄了个半平面交，结果wa了。抽空cjb和yzc讨论了H
，又wa了。卡了很久，什么题都过不去。终于cjb和yzc搞出了H，'''H4y168'''。sub给了个F的做法，yzc上机wa了，cjb换了个板子，结果tle了。终于发现不用sort，'''I8y205'''。F fix了之后还是wa，只好先让sub上去写G，G也wa了。cjb上了个猜想，D也wa了。封榜后，sub fix了G，'''G2y265'''。努力搞F，终于过了，'''F4y278'''。最后三人一起艹D，一直都wa，构造不够给力。
== 总结 ==
=== chenjb ===
今天血妈爆炸，毛哥哥封榜后疯狂出几何题被艹翻在地。半平面交那个问题其实一直以来都有，这个板子一定要好好整理才行，另一个就是那个F，大家都一下子搞过去了，我们浪费了大量的时间，而我和yzc都对他没有太多办法，而其他题都是几何，两个字符串难度也比较高，可以说这是对我们队最不利的场了，还好封榜后还是稳住出了2题，如果D再简单一点的可以出第7题，只是他的构造实在过于tricky了....我也应该早点去开这两个题，毕竟毛哥哥封榜后还顺手过了一个我觉得很不可做的字符串，被困住了还是应该早点开起新题，不然就太匆忙了。这两天罚时都有点爆炸啊，控制一下啊....
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：上面最大位加1，下面最大位加1，直到不再更优即可。

 * B：二分环长，把东西放在环上，有两种情况，构成一个环，一种是包含圆心，另一种不包含，包含圆心的情况内角和360度，否则等于最大内角，注意精度。

 * C：可以归纳证明a[i,j] xor a[i,1] xor a[1,j] xor a[1,1] xor ((i+1)*(j+1))=0，如果(1,1)没被确定，那就枚举，然后推得第一行第一列互相之间相等或者不等关系，用并查集来维护这些关系，最后计算自由元的数量，求2的幂次即可。

 * D：若i的二进制里1的个数为偶数，则s[i]=a，反之为b，这个串称为Thue-Morse串，有以下性质：s[2i]=s[i]; s[2i+1]=-s[i]; s[j]=s[j+1] -> j is odd; 不存在 s[j]=s[j+1]=s[j+2];等。可以推出不存在i>=0,l>0并且s[i..i+l]=s[i+l..i+2l]。构造t[i]=f(s[i]s[i+1])，f(aa)=0,f(ab)=1,f(ba)=2,f(bb)=3，可以证明这个串不会有重复。然后，因为s中所有aa只会出现在baab，所有bb只会出现在abba，所以我们可以把f(bb)=3变成f(bb)=0，同样也不会有重复，所以就构造出了最小解。

 * E：按题意模拟，不会tle。

 * F：第i位到最后的和一定是i的倍数，从前往后放即可。

 * G：找出所有%p的解，对于每个解可以算出f(x)和f(x+p)的差，由于和p的关系是线性的，所以直接求逆元即可。

 * H：最弱去打对面最弱，最强去揍对面最强，不行的话就用自己最弱去对碰对面最强。

 * I：二分答案后，将线段往里push，然后用半平面交判定是否有面积。

 * J：建出凸包，对每个问题在凸包上下壳上二分。

 * K：预处理lcp[i][j]代表i-shift和j-shift的最长公共前缀，然后简单分类讨论预处理出f[i][j]代表i..j-1是否大于j..i-1，将f[i][j]放进bitset b[i][j]，将f[j][i]放进bitset b[i][j]，设i是串b开头，j是串c开头，k是串a开头，枚举i和k，f[i][k]判定b+c>a,b[k]判定a+b>c的j的个数，c[i]代表c+a>b的b数量，&起来数一下i+1..k-1内有多少个1，用一个bitset再&一下就好，复杂度O(n^3^/64)。

 * L：固定一个点，枚举与它相邻的其他三个点，这三个高度差就是平面法向量在立方体坐标系中三个方向的投影长度，构造反射变换使得立方体坐标系可以变为标准坐标系，随后代入x,y,z，即可得到立方体的三边向量。

XIV Open Cup named after E.V. Pankratiev. GP of Kharkiv

流水账

出门各自看题，上了个E，先re再wa，sub上了个A，A2y43。cjb上了个假G，然后yzc E4y57。之后sub给了G的做法给yzc，结果tle了，卡不过去。cjb抄了个半平面交，结果wa了。抽空cjb和yzc讨论了H

，又wa了。卡了很久，什么题都过不去。终于cjb和yzc搞出了H，H4y168。sub给了个F的做法，yzc上机wa了，cjb换了个板子，结果tle了。终于发现不用sort，I8y205。F fix了之后还是wa，只好先让sub上去写G，G也wa了。cjb上了个猜想，D也wa了。封榜后，sub fix了G，G2y265。努力搞F，终于过了，F4y278。最后三人一起艹D，一直都wa，构造不够给力。

总结

chenjb

今天血妈爆炸，毛哥哥封榜后疯狂出几何题被艹翻在地。半平面交那个问题其实一直以来都有，这个板子一定要好好整理才行，另一个就是那个F，大家都一下子搞过去了，我们浪费了大量的时间，而我和yzc都对他没有太多办法，而其他题都是几何，两个字符串难度也比较高，可以说这是对我们队最不利的场了，还好封榜后还是稳住出了2题，如果D再简单一点的可以出第7题，只是他的构造实在过于tricky了....我也应该早点去开这两个题，毕竟毛哥哥封榜后还顺手过了一个我觉得很不可做的字符串，被困住了还是应该早点开起新题，不然就太匆忙了。这两天罚时都有点爆炸啊，控制一下啊....

oipotato

subconscious

题解

  • A：上面最大位加1，下面最大位加1，直到不再更优即可。
  • B：二分环长，把东西放在环上，有两种情况，构成一个环，一种是包含圆心，另一种不包含，包含圆心的情况内角和360度，否则等于最大内角，注意精度。
  • C：可以归纳证明a[i,j] xor a[i,1] xor a[1,j] xor a[1,1] xor ((i+1)*(j+1))=0，如果(1,1)没被确定，那就枚举，然后推得第一行第一列互相之间相等或者不等关系，用并查集来维护这些关系，最后计算自由元的数量，求2的幂次即可。
  • D：若i的二进制里1的个数为偶数，则s[i]=a，反之为b，这个串称为Thue-Morse串，有以下性质：s[2i]=s[i]; s[2i+1]=-s[i]; s[j]=s[j+1] -> j is odd; 不存在 s[j]=s[j+1]=s[j+2];等。可以推出不存在i>=0,l>0并且s[i..i+l]=s[i+l..i+2l]。构造t[i]=f(s[i]s[i+1])，f(aa)=0,f(ab)=1,f(ba)=2,f(bb)=3，可以证明这个串不会有重复。然后，因为s中所有aa只会出现在baab，所有bb只会出现在abba，所以我们可以把f(bb)=3变成f(bb)=0，同样也不会有重复，所以就构造出了最小解。
  • E：按题意模拟，不会tle。
  • F：第i位到最后的和一定是i的倍数，从前往后放即可。
  • G：找出所有%p的解，对于每个解可以算出f(x)和f(x+p)的差，由于和p的关系是线性的，所以直接求逆元即可。
  • H：最弱去打对面最弱，最强去揍对面最强，不行的话就用自己最弱去对碰对面最强。
  • I：二分答案后，将线段往里push，然后用半平面交判定是否有面积。
  • J：建出凸包，对每个问题在凸包上下壳上二分。
  • K：预处理lcp[i][j]代表i-shift和j-shift的最长公共前缀，然后简单分类讨论预处理出f[i][j]代表i..j-1是否大于j..i-1，将f[i][j]放进bitset b[i][j]，将f[j][i]放进bitset b[i][j]，设i是串b开头，j是串c开头，k是串a开头，枚举i和k，f[i][k]判定b+c>a,b[k]判定a+b>c的j的个数，c[i]代表c+a>b的b数量，&起来数一下i+1..k-1内有多少个1，用一个bitset再&一下就好，复杂度O(n3/64)。
  • L：固定一个点，枚举与它相邻的其他三个点，这三个高度差就是平面法向量在立方体坐标系中三个方向的投影长度，构造反射变换使得立方体坐标系可以变为标准坐标系，随后代入x,y,z，即可得到立方体的三边向量。
附加文件