2017-Sp263-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门各自看题，sub似乎很懂I的容斥那一套，让yzc上机写了个数星星，'''I2y51'''。cjb上机搜了个矩阵，然后写了F，'''F1y82'''。之后cjb和yzc理论E，说服yzc后，yzc和sub确认做法，上机'''E1y168'''。sub想好了D，上机写D，'''D2y187'''。cjb一直在搞B，辛苦地搞出了个构造'''B2y204'''。之后感觉只能写A了，cjb上了个圆方树板子，结果第一次用遇到了各种问题，辛苦搞到最后'''A6y288'''。
=== chenjb ===
感觉A应该过得更爽快才行，高大爷还是牛逼啊。经过这次，对我们的圆方树板子应该熟悉一层了，也是个好事情。以后仙人掌题也要注意题目的定义到底是广义还是狭义的。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：仙人掌dp，环上正反绕一圈。

 * B：构造两排n个点依次链接-1000，然后对于每个为0的位置，枚举bit，根据其为0/1用左/右对应点连向终点-1000，之后用每排点的第一个点连向终点，权值为250和500。最后没有出边的点连接终点，权值为0。本质上就是构建出or和not。

 * C：

 * D：状压dp，只需要记录有多少个两边都是绿的，dp预处理答案。

 * E：枚举上下边界，对于每个左边界，考虑每只怪兽作为被杀死最强怪兽有多少个区间，考虑每只怪兽最早出现时间，和最早能在什么位置被杀死，一只怪兽能产生贡献的位置就是它能被杀死并且它出现了，并且后面的人都还没出现。

 * F：暴搜出一个任意两行、任意两列都有至少3个位置不同的矩阵，暴力排列判定即可。

 * G：如果没有sort，询问就直接对于每一位求区间多少个1，然后维护抑或操作的效果。插入值的时候抑或上前面的抑或修改，即将这个数字看成一开始就在，经过一些操作之后变成了读入的数字。有了sort，考虑每次sort操作都把上次还没sort的值插入trie，考虑对原始数字维护trie，只要记录sort的时候的抑或操作的效果就可以在trie树上找到第k个人。由于空间不够，所以离线按位分别做，在插入数字的时候只需要取最高的i位，这样可以使常数/2。再随便卡卡常就过了。

 * H：

 * I：二维数点容斥出三维数点答案。

 * [https://icpc.camp/deep-dark-fantasy/20170501 DeepDarkFantasy]

 * [https://icpc.camp/wood-cube/Petrozavodsk%20Summer-2016%20Pavel%20Khaustov%202 WoodCube]

 * [https://icpc.camp/new-meta/2017/2/28%20Pavel%20Khaustov%20Contest%202 NewMeta]

流水账

出门各自看题，sub似乎很懂I的容斥那一套，让yzc上机写了个数星星，I2y51。cjb上机搜了个矩阵，然后写了F，F1y82。之后cjb和yzc理论E，说服yzc后，yzc和sub确认做法，上机E1y168。sub想好了D，上机写D，D2y187。cjb一直在搞B，辛苦地搞出了个构造B2y204。之后感觉只能写A了，cjb上了个圆方树板子，结果第一次用遇到了各种问题，辛苦搞到最后A6y288。

chenjb

感觉A应该过得更爽快才行，高大爷还是牛逼啊。经过这次，对我们的圆方树板子应该熟悉一层了，也是个好事情。以后仙人掌题也要注意题目的定义到底是广义还是狭义的。

oipotato

subconscious

题解

  • A：仙人掌dp，环上正反绕一圈。
  • B：构造两排n个点依次链接-1000，然后对于每个为0的位置，枚举bit，根据其为0/1用左/右对应点连向终点-1000，之后用每排点的第一个点连向终点，权值为250和500。最后没有出边的点连接终点，权值为0。本质上就是构建出or和not。
  • C：
  • D：状压dp，只需要记录有多少个两边都是绿的，dp预处理答案。
  • E：枚举上下边界，对于每个左边界，考虑每只怪兽作为被杀死最强怪兽有多少个区间，考虑每只怪兽最早出现时间，和最早能在什么位置被杀死，一只怪兽能产生贡献的位置就是它能被杀死并且它出现了，并且后面的人都还没出现。
  • F：暴搜出一个任意两行、任意两列都有至少3个位置不同的矩阵，暴力排列判定即可。
  • G：如果没有sort，询问就直接对于每一位求区间多少个1，然后维护抑或操作的效果。插入值的时候抑或上前面的抑或修改，即将这个数字看成一开始就在，经过一些操作之后变成了读入的数字。有了sort，考虑每次sort操作都把上次还没sort的值插入trie，考虑对原始数字维护trie，只要记录sort的时候的抑或操作的效果就可以在trie树上找到第k个人。由于空间不够，所以离线按位分别做，在插入数字的时候只需要取最高的i位，这样可以使常数/2。再随便卡卡常就过了。
  • H：
  • I：二维数点容斥出三维数点答案。
  • DeepDarkFantasy
  • WoodCube
  • NewMeta
附加文件