2017-Sp92-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，不久后E和I有人过，sub读了I，上机，CE了一发后'''I1y16'''。cjb和yzc秒了D，yzc上机wa了2发，之后让sub看了看，找到了bug，'''D3y48'''。sub研究E，cjb和yzc研究G，之后一度以为开出了J，cjb上机写J，后来发现问题，换sub上机'''E1y83'''。yzc上机G wa了。之后cjb和sub重新理论了J，cjb上机重新写J，debug信息没删，'''J2y128'''。yzc上机写B，获得the，下机和sub理论，后在思考做法。cjb和sub研究C，cjb上机敲了tarjan，sub上机写C，后来发现cjb的tarjan有问题，yzc思考好了B，上机'''B2y214'''。之后cjb上机修改tarjan，之后sub C wa了两发。进入封榜，yzc告诉cjb，他之前和sub大概理论了M，sub表示尝试一发很快，yzc在机下也证明了结论，'''M1y263'''。之后yzc和sub发现C的做法是错的，修正了结论，最后疯狂改，疯狂交，不能通过。今天6题rk17，交大8题rk4，NTU 8题rk7，福大7题rk10。
== 总结 ==
=== chenjb ===
C有点可惜，M应该更早拿下，虽然没有影响太多，还是要注意一些信息的沟通。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：没有很大的边权就是一个简单的树形DP。由于边权都是2的幂次，于是使用set维护二进制位并启发式合并即可。

 * C：仙人掌染色。没有奇环二分染色，否则需要颜色就是最短奇环。对环上染色先染完一轮，随后正负轮替即可。

 * D：先判断必然，显然区间肯定是台阶式的严格上升(下降的)，扫一遍就知道是不是必然了。然后从左到右贪心找到最远的R，从右到左贪心找到最远的L，如果R和L碰在一起，就至少有一个解，否则无解。

 * E：发现只要考虑链的数量的每条链的大小即可。考虑全零的情况，大力推式子即可。

 * F：定义可折叠位置为以这个点为中心的最长回文串能顶到边界的点，则单元素集合为可折叠位置数，多元素显然是左半边的可折叠位置数*右半边可折叠位置数，最后加上空集。

 * G：

 * H：

 * I：求点和多边形有两条垂直的外切线，取x最小值，y最小值直接输出即可。

 * J：对于极大平面图，三染色是唯一的，染完之后答案就是sum[0]*sum[1]+sum[0]*sum[2]+sum[1]*sum[2]-m。我们随便取一条边的两个点扔进queue，类似于topsort，每个点如果只剩一种选择就进queue，这样肯定能染完所有的点，出现矛盾就GG。

 * K：

 * L：可以发现s1(x)%p在p无奇因子时无法取遍所有值。直接大力求出即可。特判s0的情况，p是2的幂次时直接-1。

 * M：
== 补题 ==

流水账

开场各自看题，不久后E和I有人过，sub读了I，上机，CE了一发后I1y16。cjb和yzc秒了D，yzc上机wa了2发，之后让sub看了看，找到了bug，D3y48。sub研究E，cjb和yzc研究G，之后一度以为开出了J，cjb上机写J，后来发现问题，换sub上机E1y83。yzc上机G wa了。之后cjb和sub重新理论了J，cjb上机重新写J，debug信息没删，J2y128。yzc上机写B，获得the，下机和sub理论，后在思考做法。cjb和sub研究C，cjb上机敲了tarjan，sub上机写C，后来发现cjb的tarjan有问题，yzc思考好了B，上机B2y214。之后cjb上机修改tarjan，之后sub C wa了两发。进入封榜，yzc告诉cjb，他之前和sub大概理论了M，sub表示尝试一发很快，yzc在机下也证明了结论，M1y263。之后yzc和sub发现C的做法是错的，修正了结论，最后疯狂改，疯狂交，不能通过。今天6题rk17，交大8题rk4，NTU 8题rk7，福大7题rk10。

总结

chenjb

C有点可惜，M应该更早拿下，虽然没有影响太多，还是要注意一些信息的沟通。

oipotato

subconscious

题解

  • A：
  • B：没有很大的边权就是一个简单的树形DP。由于边权都是2的幂次，于是使用set维护二进制位并启发式合并即可。
  • C：仙人掌染色。没有奇环二分染色，否则需要颜色就是最短奇环。对环上染色先染完一轮，随后正负轮替即可。
  • D：先判断必然，显然区间肯定是台阶式的严格上升(下降的)，扫一遍就知道是不是必然了。然后从左到右贪心找到最远的R，从右到左贪心找到最远的L，如果R和L碰在一起，就至少有一个解，否则无解。
  • E：发现只要考虑链的数量的每条链的大小即可。考虑全零的情况，大力推式子即可。
  • F：定义可折叠位置为以这个点为中心的最长回文串能顶到边界的点，则单元素集合为可折叠位置数，多元素显然是左半边的可折叠位置数*右半边可折叠位置数，最后加上空集。
  • G：
  • H：
  • I：求点和多边形有两条垂直的外切线，取x最小值，y最小值直接输出即可。
  • J：对于极大平面图，三染色是唯一的，染完之后答案就是sum[0]*sum[1]+sum[0]*sum[2]+sum[1]*sum[2]-m。我们随便取一条边的两个点扔进queue，类似于topsort，每个点如果只剩一种选择就进queue，这样肯定能染完所有的点，出现矛盾就GG。
  • K：
  • L：可以发现s1(x)%p在p无奇因子时无法取遍所有值。直接大力求出即可。特判s0的情况，p是2的幂次时直接-1。
  • M：

补题

附加文件