2016-C23-team2

从 Trac 迁移的文章

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

原文章内容如下：

||Run ID||Time||Size||Problem||Language||Result||
||656||4:34:28||6452||F||g++0x||OK||
||651||4:21:23||6935||F||g++0x||Wrong answer||
||647||4:19:50||6935||F||g++0x||Time-limit exceeded||
||645||4:19:17||6936||F||g++0x||Time-limit exceeded||
||643||4:17:36||6892||F||g++0x||Time-limit exceeded||
||638||4:08:33||6496||F||g++0x||Wrong answer||
||636||4:07:03||6433||F||g++0x||Time-limit exceeded||
||635||4:03:20||837||J||g++0x||OK||
||629||3:54:46||672||J||g++0x||Wrong answer||
||604||2:50:18||1843||H||g++0x||OK||
||595||2:36:16||3107||H||g++0x||Wrong answer||
||593||2:32:31||2937||H||g++0x||Wrong answer||
||587||2:10:41||698||B||g++0x||OK||
||585||2:03:07||1713||D||g++0x||OK||
||578||1:40:39||1764||D||g++0x||Wrong answer||
||569||1:12:57||1816||E||g++0x||OK||
||564||1:00:09||1814||E||g++0x||Wrong answer||
||562||0:57:30||1814||E||g++0x||Wrong answer||
||557||0:36:51||1224||A||g++0x||OK||
||556||0:33:30||1111||E||g++0x||Wrong answer||
||551||0:27:25||1042||E||g++0x||Wrong answer||
||545||0:18:55||1877||E||g++0x||Wrong answer||

== 流水账 ==
=== TsReaper ===
开场比较不好，starve学长觉得E是简单题急忙去敲了，结果因为算法和程序中的一些错误一直没有通过。A题我也比较犯傻想复杂了...开场'''A1y36'''，'''E6y72'''。starve学长搞E的时候我和hzf学长弄清楚了D和H的做法，但是这两题都比较模拟（昨天北京网络赛也是很多模拟，感觉整个人都不太好...），'''D2y123'''，'''H3y170'''。我写D的过程中学长们会了B，'''B1y130'''。

比较可做的题貌似都做完了，我和hzf学长考虑C和J，starve学长尝试几何题F。一开始都没有什么思路，后来J我想到了分类讨论的方法，'''J2y243'''。starve学长的几何题+搜索也经过各种差错之后过了，'''F7y274'''，这场脸还是比较白的...

== 总结 ==
=== TsReaper ===
 * 做得好的地方
   * 通过讨论把不平等博弈变成平等博弈的思路是非常正确的，NP问题用搜索解决的思路也是正确的。
 * 做得不好的地方
   * 代码能力还是有待加强，虽然有比较多的模拟题但是正确率还应该高一点。

== 题解 ==
AE比较容易，H虽然细节多但也容易，略过...

=== C - Decoding Ancient Messages ===
其实就是最大费用流，只不过费用是一个字典序，定义一个struct就好了...大家因为没有见过这种奇怪费用的费用流都没有敢写...

edit: 好吧...的确有一定困难...写的时候有一个小技巧，就是为了不让字典序里某个字母出现次数为负，我们可以在费用流的运算过程中，把上一次算出来的答案做为下一次的初始费用，这样就不会有负数了。

edit2: 转换成最大费用流就方便很多了（比如把费用视为一个50进制的数，这样多选一个字典序小的肯定优），负数问题就不怎么需要考虑了。

=== D - LR ===
显然是区间dp，不过最后答案可能略大，要自己写一个struct来记。

记s[i]表示第i个字符，一个合法区间[i,j]只有两种可能：

 1. 这个区间是一个数，那么s[i]只能是1~9或?，s[i+1]~s[j]只能是0~9或?。确定这个区间可以是数后，我们就把所有?都变成9，就能得到最大的数。
 2. 这个区间是一个函数，那么s[i]只能是L,R或?，s[i+1]只能是(或?，s[j]只能是)或?。确定这个区间可以是函数后，我们枚举逗号的位置（从i+3~j-2）。记lmax表示逗号左右两边都合法时，左边的最大值，rmax表示右边的最大值。则s[i]为L时，答案就是lmax；为R时，答案就是rmax；为?时，答案是max(lmax,rmax)。

=== F - Polygon Guards ===
经过几何的预处理后，问题变成了一般图的最小支配集。把点按能支配的点数排序，搜索一下即可。

=== J - Unfair Game ===
记M = min(A,B)，如果A = B或每一堆石头个数都小等于M，那么这个问题就是一个公平游戏。若一堆石子有x个，很容易得到它的sg函数值为x mod (M+1).

现在我们讨论不公平游戏的情况（也就是A != B，且至少有一堆石头个数大于M），以下提到的sg值都是公平游戏下算出来的sg值。

如果A > B，且初始局面的sg值非0，显然先手必胜（直接把游戏当公平游戏玩即可，不使用一次拿取多于B个石头的操作）。

如果A > B，且初始局面为sg值为0，那么若先手能够通过一次操作，让操作后的局面sg值还是0，那么先手仍然必胜。这是可以做到的。因为至少有一堆石头个数大于M，而sg值的计算公式为x mod (M+1)，那么先手只要从个数大于M的石头堆中拿走M+1个石头就可以了。所以先手仍然必胜。

如果A < B，且初始局面sg值为0，显然后手必胜。

如果A < B，且初始局面sg值非0，那么先手必胜的唯一机会，就是通过一次操作，让操作后的局面sg值为0，而且操作后的局面每一堆石头个数都小等于M。这样，后手就不能通过一次操作，让操作后的局面sg值还是0，从而获胜了。先手要拿走的石头个数x，我们可以通过sg值算出来。也就是说，如果初始局面只有一堆石头个数大于M，而且这堆石头拿走x个之后，个数小等于M，那么先手必胜，否则后手必胜。

== 补题 ==
=== TsReaper ===
~~C~~
Run IDTimeSizeProblemLanguageResult
6564:34:286452Fg++0xOK
6514:21:236935Fg++0xWrong answer
6474:19:506935Fg++0xTime-limit exceeded
6454:19:176936Fg++0xTime-limit exceeded
6434:17:366892Fg++0xTime-limit exceeded
6384:08:336496Fg++0xWrong answer
6364:07:036433Fg++0xTime-limit exceeded
6354:03:20837Jg++0xOK
6293:54:46672Jg++0xWrong answer
6042:50:181843Hg++0xOK
5952:36:163107Hg++0xWrong answer
5932:32:312937Hg++0xWrong answer
5872:10:41698Bg++0xOK
5852:03:071713Dg++0xOK
5781:40:391764Dg++0xWrong answer
5691:12:571816Eg++0xOK
5641:00:091814Eg++0xWrong answer
5620:57:301814Eg++0xWrong answer
5570:36:511224Ag++0xOK
5560:33:301111Eg++0xWrong answer
5510:27:251042Eg++0xWrong answer
5450:18:551877Eg++0xWrong answer

流水账

TsReaper

开场比较不好，starve学长觉得E是简单题急忙去敲了，结果因为算法和程序中的一些错误一直没有通过。A题我也比较犯傻想复杂了...开场A1y36，E6y72。starve学长搞E的时候我和hzf学长弄清楚了D和H的做法，但是这两题都比较模拟（昨天北京网络赛也是很多模拟，感觉整个人都不太好...），D2y123，H3y170。我写D的过程中学长们会了B，B1y130。

比较可做的题貌似都做完了，我和hzf学长考虑C和J，starve学长尝试几何题F。一开始都没有什么思路，后来J我想到了分类讨论的方法，J2y243。starve学长的几何题+搜索也经过各种差错之后过了，F7y274，这场脸还是比较白的...

总结

TsReaper

  • 做得好的地方
    • 通过讨论把不平等博弈变成平等博弈的思路是非常正确的，NP问题用搜索解决的思路也是正确的。
  • 做得不好的地方
    • 代码能力还是有待加强，虽然有比较多的模拟题但是正确率还应该高一点。

题解

AE比较容易，H虽然细节多但也容易，略过...

C - Decoding Ancient Messages

其实就是最大费用流，只不过费用是一个字典序，定义一个struct就好了...大家因为没有见过这种奇怪费用的费用流都没有敢写...

edit: 好吧...的确有一定困难...写的时候有一个小技巧，就是为了不让字典序里某个字母出现次数为负，我们可以在费用流的运算过程中，把上一次算出来的答案做为下一次的初始费用，这样就不会有负数了。

edit2: 转换成最大费用流就方便很多了（比如把费用视为一个50进制的数，这样多选一个字典序小的肯定优），负数问题就不怎么需要考虑了。

D - LR

显然是区间dp，不过最后答案可能略大，要自己写一个struct来记。

记s[i]表示第i个字符，一个合法区间[i,j]只有两种可能：

1. 这个区间是一个数，那么s[i]只能是1~9或?，s[i+1]~s[j]只能是0~9或?。确定这个区间可以是数后，我们就把所有?都变成9，就能得到最大的数。

2. 这个区间是一个函数，那么s[i]只能是L,R或?，s[i+1]只能是(或?，s[j]只能是)或?。确定这个区间可以是函数后，我们枚举逗号的位置（从i+3~j-2）。记lmax表示逗号左右两边都合法时，左边的最大值，rmax表示右边的最大值。则s[i]为L时，答案就是lmax；为R时，答案就是rmax；为?时，答案是max(lmax,rmax)。

F - Polygon Guards

经过几何的预处理后，问题变成了一般图的最小支配集。把点按能支配的点数排序，搜索一下即可。

J - Unfair Game

记M = min(A,B)，如果A = B或每一堆石头个数都小等于M，那么这个问题就是一个公平游戏。若一堆石子有x个，很容易得到它的sg函数值为x mod (M+1).

现在我们讨论不公平游戏的情况（也就是A != B，且至少有一堆石头个数大于M），以下提到的sg值都是公平游戏下算出来的sg值。

如果A > B，且初始局面的sg值非0，显然先手必胜（直接把游戏当公平游戏玩即可，不使用一次拿取多于B个石头的操作）。

如果A > B，且初始局面为sg值为0，那么若先手能够通过一次操作，让操作后的局面sg值还是0，那么先手仍然必胜。这是可以做到的。因为至少有一堆石头个数大于M，而sg值的计算公式为x mod (M+1)，那么先手只要从个数大于M的石头堆中拿走M+1个石头就可以了。所以先手仍然必胜。

如果A < B，且初始局面sg值为0，显然后手必胜。

如果A < B，且初始局面sg值非0，那么先手必胜的唯一机会，就是通过一次操作，让操作后的局面sg值为0，而且操作后的局面每一堆石头个数都小等于M。这样，后手就不能通过一次操作，让操作后的局面sg值还是0，从而获胜了。先手要拿走的石头个数x，我们可以通过sg值算出来。也就是说，如果初始局面只有一堆石头个数大于M，而且这堆石头拿走x个之后，个数小等于M，那么先手必胜，否则后手必胜。

补题

TsReaper

C

附加文件