2017-Sp212-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
开场cjb跳上机子写起了B，yzc和sub讨论了A就上机wa了，然后发现做法naive了，fix之后上机'''A3y55'''。之后sub上机写D，cjb和yzc讨论F，sub '''D1y104'''。yzc上机写F，cjb和sub讨论C，得到了大概做法让sub去准备。然后就开始了爆炸之旅，疯狂调参fix做法艹F，一直在wa11，之后cjb给出了一个感觉天稳的做法还是wa，甚至调参都拍上了。sub写C很痛苦，下机艹了个特例，fix之后变成了tle，tle之后还是wa。yzc加了个自己之前认为已经概括掉的corner case，结果跑过了testcase 11，卡了几发常之后'''F27y276'''。sub交C RE了，fix到最后10min交了还是RE，决定把自己的assert给删掉，然后过了，'''C6y298'''。最后4题 rk9，jsb和咖啡鸡和MIPT都是4题，首尔5题，MSU和MIT 6题，东大7题。
== 总结 ==
=== chenjb ===
楠楠，打怪兽的corner case其实一开始就被yzc提出了，结果被不够强的样例叉掉了，以后这种还是先加上求稳....感觉我的B做法很清真啊QAQ等我补一补就知道是不是自己naive了。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：显然只用考虑每种数字第一次出现位置，考虑用1..x和x..nxtx-1的数字来替换，前一部分只需要用set维护差值最小的数，后一部分需要用线段树或数据结构维护。

 * B：~~快乐判图@cjb~~  '''快乐个屁！摸了！'''

 * C：一刀不那么直的线切在n/2的上方，接下来每次对左右凸包做切，切到的两点，用exgcd向下调整得到刚好不穿过的直线坐标。

 * D：n^2^容斥求出连通奇环外向树数量，去除单环和二元环，然后加上生成树是方案数；生成树数量乘上再加一条边的方案数是贡献和，n^2^容斥dp。

 * E：

 * F：大多数情况下，至少有1只怪会在110(101)轮内死掉，剩下的直接贪心枚举打死顺序，有一种小corner case是所有轮打完之后三只怪都没死(大 boss 的血量是 1+2+3+…+1000 伤害值是 1e9;小怪血量 1 伤害是 1)，要出门直奔大boss。

 * G：

 * H：考虑第一棵树中的每条边(u,v)，它将整棵树分成了两边，对两边分别染色为0，1，则它的贡献为d1(u,v)*sigma(i,1,n)sigma(j,1,n){d2(x,y)|color[x]!=color[y]}。使用dsu on the tree，我们可以维护每条边对应的点的染色，剩下要做的就是改变一个点染色的时候维护第二棵树上所有不同色的点的两两距离，使用动态点分治即可。

 * I：快乐burnside@sub

 * J：快乐生成树@cjb

 * K：

流水账

开场cjb跳上机子写起了B，yzc和sub讨论了A就上机wa了，然后发现做法naive了，fix之后上机A3y55。之后sub上机写D，cjb和yzc讨论F，sub D1y104。yzc上机写F，cjb和sub讨论C，得到了大概做法让sub去准备。然后就开始了爆炸之旅，疯狂调参fix做法艹F，一直在wa11，之后cjb给出了一个感觉天稳的做法还是wa，甚至调参都拍上了。sub写C很痛苦，下机艹了个特例，fix之后变成了tle，tle之后还是wa。yzc加了个自己之前认为已经概括掉的corner case，结果跑过了testcase 11，卡了几发常之后F27y276。sub交C RE了，fix到最后10min交了还是RE，决定把自己的assert给删掉，然后过了，C6y298。最后4题 rk9，jsb和咖啡鸡和MIPT都是4题，首尔5题，MSU和MIT 6题，东大7题。

总结

chenjb

楠楠，打怪兽的corner case其实一开始就被yzc提出了，结果被不够强的样例叉掉了，以后这种还是先加上求稳....感觉我的B做法很清真啊QAQ等我补一补就知道是不是自己naive了。

oipotato

subconscious

题解

  • A：显然只用考虑每种数字第一次出现位置，考虑用1..x和x..nxtx-1的数字来替换，前一部分只需要用set维护差值最小的数，后一部分需要用线段树或数据结构维护。
  • B：快乐判图@cjb 快乐个屁！摸了！
  • C：一刀不那么直的线切在n/2的上方，接下来每次对左右凸包做切，切到的两点，用exgcd向下调整得到刚好不穿过的直线坐标。
  • D：n2容斥求出连通奇环外向树数量，去除单环和二元环，然后加上生成树是方案数；生成树数量乘上再加一条边的方案数是贡献和，n2容斥dp。
  • E：
  • F：大多数情况下，至少有1只怪会在110(101)轮内死掉，剩下的直接贪心枚举打死顺序，有一种小corner case是所有轮打完之后三只怪都没死(大 boss 的血量是 1+2+3+…+1000 伤害值是 1e9;小怪血量 1 伤害是 1)，要出门直奔大boss。
  • G：
  • H：考虑第一棵树中的每条边(u,v)，它将整棵树分成了两边，对两边分别染色为0，1，则它的贡献为d1(u,v)*sigma(i,1,n)sigma(j,1,n){d2(x,y)|color[x]!=color[y]}。使用dsu on the tree，我们可以维护每条边对应的点的染色，剩下要做的就是改变一个点染色的时候维护第二棵树上所有不同色的点的两两距离，使用动态点分治即可。
  • I：快乐burnside@sub
  • J：快乐生成树@cjb
  • K：
附加文件