2017-Sp08-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,400px)]]
== 流水账 ==
开场各自看题，不久yzc判断A是个傻逼题，此时有人过D，三人一起看D，感觉D需要推式子，yzc推了一段时间后上机写，写完后过不了样例，下机验算式子，此前已经确认过做法的cjb上机写A，后来yzc换下cjb，40分钟的时候交了第一发D获得奇怪的PE，cjb继续写A，'''A1y48'''. sub突然问到会不会是除0的情况，yzc意识到需要加一个特判，加了之后过了，'''D2y56'''. 接下来三人把除了B以外的题都看了看，发现大家在做F，然后三人判断K是个lct，但有一个操作还没想到很好的处理方法，就让cjb上机敲lct板子，中途sub和yzc基本确认了F是个斜率优化dp，cjb敲完板子后让sub上机写F. cjb和yzc尝试开题，看到G的时候，感觉暴力是10^9^，在想能不能加点优化艹过去，cjb突然意识到板子上有一个位运算优化的同样问题的板子，yzc和cjb算了一发复杂度后感觉刚好够，换下sub去魔改板子，因为对板子不熟悉，中间花了点时间，最后两小时多的时候通过了样例，提交获得tle，打印了代码，让sub继续写F，cjb和yzc决定在板子的基础上进行各种优化，优化它手写的bitset，改函数为引用等等，半个小时后又交了一发，还是tle. sub终于调试出F，提交获得wa，后来改了改还是wa. cjb决定自己上机敲对拍，让sub给yzc讲代码，后来对拍小数据出了几次错，sub修改后在封榜的时候通过了F,'''F3y240'''. cjb和yzc决定最后挣扎一下G，因为本地已经优化到了1.8s，感觉再努力一下就可以了，让sub去思考别的题，cjb和yzc试图使用int128，但还是tle在同一个点，最后sub觉得J上一个平面图的板子就能过了，cjb上机飞速敲板子，sub在最后十分钟努力挣扎，最后还是没搞定，最后3题结束了，Siunaus最后5题，TaZoF和Dominoes最后都是4题，还是比较可惜，我们队做几何题和类几何题都要向风学长学习啊，太稳健了啊！
== 总结 ==
=== chenjb ===
今天这套题比较难，但是非常值得改，需要反思下为什么中间三个小时只过了一题，选择刚G真的合适吗？H那道字符串虽然细节很多，但是做法自己比较清晰(以前自己出过)，应该先让sub尽早写完F而不是不断打断他。另外还是比较想知道G和K到底怎么做，Siunaus的题解里没有，大家好像也没有改这两道题。[[BR]]
updated: sf学长说得对啊，如果这个题真的暴力压位能艹过去，大概有几万只毛子碾过去了啊....
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * B:
    * 题意：求任意某条边和某条对角线的夹角均为pi/2/k的倍数的凸四边形有多少个。k<=150.
    * 题解：很容易想到上下切开后使从上往下的对角线重合即可。发现只要枚举三个角度就可以确定对角线分割底边的比例，大力k^3^排序扫一遍即可。精度有毒。
 * G：
   * 题意：问题关键是在求一个串的循环同构和另一个串的最长公共子串(CLCS)，下面也是在论述一个n^2^求CLCS的做法。
   * 题解：彪爷讲的很清楚了，就不再赘述了...另外论文也在附件里，也可以看看。[[BR]]
      [[Image(G.png,400px)]]
 * I:
    * 题意：以原点为圆心有一半径为R的圆，给定圆外n个点，两点之间有边当且仅当过两点的直线和圆无焦点，求最大团，输出方案。n<=2000.
    * 题解：容易想到通过两切点对应到圆上的区间，发现有边当且仅当区间严格相交（不包含）。性质：其中一区间取补集，环上两区间严格相交性仍不变。因此取基准区间，所有其他区间通过部分在右侧的取补集回到左侧，观察结果区间，有原题变为二维LIS问题。
 * K：树链剖分。对于重边，直接维护。对于轻边，修改时在重链上打标记，询问时看轻边两端标记的时间是否一致即可。

 * [https://wiki.icpc.camp/new-meta/2013-2014%20Petrozavodsk%20Winter%20Training%20Camp,%20Moscow%20SU%20Trinity%20Contest NewMeta]
== 补题 ==
 * ~~B~~ by sub
 * C cjb
 * ~~E~~ by sub
 * ~~G~~ by cjb
 * H cjb
 * ~~I~~ by sub
 * ~~J~~ by sub
 * ~~K~~ by yzc

流水账

开场各自看题，不久yzc判断A是个傻逼题，此时有人过D，三人一起看D，感觉D需要推式子，yzc推了一段时间后上机写，写完后过不了样例，下机验算式子，此前已经确认过做法的cjb上机写A，后来yzc换下cjb，40分钟的时候交了第一发D获得奇怪的PE，cjb继续写A，A1y48. sub突然问到会不会是除0的情况，yzc意识到需要加一个特判，加了之后过了，D2y56. 接下来三人把除了B以外的题都看了看，发现大家在做F，然后三人判断K是个lct，但有一个操作还没想到很好的处理方法，就让cjb上机敲lct板子，中途sub和yzc基本确认了F是个斜率优化dp，cjb敲完板子后让sub上机写F. cjb和yzc尝试开题，看到G的时候，感觉暴力是10⁹，在想能不能加点优化艹过去，cjb突然意识到板子上有一个位运算优化的同样问题的板子，yzc和cjb算了一发复杂度后感觉刚好够，换下sub去魔改板子，因为对板子不熟悉，中间花了点时间，最后两小时多的时候通过了样例，提交获得tle，打印了代码，让sub继续写F，cjb和yzc决定在板子的基础上进行各种优化，优化它手写的bitset，改函数为引用等等，半个小时后又交了一发，还是tle. sub终于调试出F，提交获得wa，后来改了改还是wa. cjb决定自己上机敲对拍，让sub给yzc讲代码，后来对拍小数据出了几次错，sub修改后在封榜的时候通过了F,F3y240. cjb和yzc决定最后挣扎一下G，因为本地已经优化到了1.8s，感觉再努力一下就可以了，让sub去思考别的题，cjb和yzc试图使用int128，但还是tle在同一个点，最后sub觉得J上一个平面图的板子就能过了，cjb上机飞速敲板子，sub在最后十分钟努力挣扎，最后还是没搞定，最后3题结束了，Siunaus最后5题，TaZoF和Dominoes最后都是4题，还是比较可惜，我们队做几何题和类几何题都要向风学长学习啊，太稳健了啊！

总结

chenjb

今天这套题比较难，但是非常值得改，需要反思下为什么中间三个小时只过了一题，选择刚G真的合适吗？H那道字符串虽然细节很多，但是做法自己比较清晰(以前自己出过)，应该先让sub尽早写完F而不是不断打断他。另外还是比较想知道G和K到底怎么做，Siunaus的题解里没有，大家好像也没有改这两道题。

updated: sf学长说得对啊，如果这个题真的暴力压位能艹过去，大概有几万只毛子碾过去了啊....

oipotato

subconscious

题解

• B:
  • 题意：求任意某条边和某条对角线的夹角均为pi/2/k的倍数的凸四边形有多少个。k<=150.
  • 题解：很容易想到上下切开后使从上往下的对角线重合即可。发现只要枚举三个角度就可以确定对角线分割底边的比例，大力k³排序扫一遍即可。精度有毒。
• G：
  • • 题意：问题关键是在求一个串的循环同构和另一个串的最长公共子串(CLCS)，下面也是在论述一个n²求CLCS的做法。
    • 题解：彪爷讲的很清楚了，就不再赘述了...另外论文也在附件里，也可以看看。
      

• I:
  • 题意：以原点为圆心有一半径为R的圆，给定圆外n个点，两点之间有边当且仅当过两点的直线和圆无焦点，求最大团，输出方案。n<=2000.
  • 题解：容易想到通过两切点对应到圆上的区间，发现有边当且仅当区间严格相交（不包含）。性质：其中一区间取补集，环上两区间严格相交性仍不变。因此取基准区间，所有其他区间通过部分在右侧的取补集回到左侧，观察结果区间，有原题变为二维LIS问题。
• K：树链剖分。对于重边，直接维护。对于轻边，修改时在重链上打标记，询问时看轻边两端标记的时间是否一致即可。
• NewMeta

补题

• B by sub
• C cjb
• E by sub
• G by cjb
• H cjb
• I by sub
• J by sub
• K by yzc

附加文件

• 1.png by chenjb
• G.pdf by chenjb
• WC_K.cc by chenjb
• G.png by chenjb