2019-team154-019

从 Trac 迁移的文章

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

原文章内容如下：

== 概述 ==

自主训练第一场

2019 Suggestions 2

2018 ICPC CERC

[http://opentrains.snarknews.info/~ejudge/team.cgi?SID=981359ba5b001ccd&action=140 Opentrains 6316]

[[Image(0914.png,700px)]]


== 总结 ==


=== dafu456 ===

第一次晚上打比赛，感觉还不错，虽然我比较划水，但是今天题目的做法“非常精彩”。

我感觉我在哪里见过L题，是一个不公平游戏的博弈题，但是不是特别确定结论，就没有最先写。和peh讨论了一下I，我上去写，过了。dzf看了A，有思路，就写了，是对AC自动机的改写，然而有点曲折，最后还是过了。期间我和peh看了一下其他题的题面，C题的题面非常“耐人寻味”，好在peh最后看懂了。上去写的时候做法有点问题，然后我提了一个不标准的做法（难以证明、复杂度成迷的做法）就过了。后来我写了L，结论没记错真是万幸，虽然WA了一发，最后的情况漏了一个细节。J，peh单挑一发过。D题是神奇的物理题，peh物理大师上去先写了一发，挂了。我们看了题目之后，对题面产生了怀疑，我甚至产生了弃题的想法去做BG。最终我们还是在题意不明、没有clarification的情况下尝试了这题，推了相当久的物理公式，写了一些鬼都看不懂的变量名（我们过了以后半小时都不知道写了啥），脑袋都要掉了。封榜后，考虑G，WA，没办法。

啊，这场真神奇。


=== 题解 ===

C：dafu方法：每次暴力枚举往右移多少位，但是pow(40, 6)肯定会超时，“剪枝”是：每次移动的时候必须覆盖第一个0。不知道对不对，反正过了。

I：枚举a（1~100），里面枚举b（a+1~1000），再枚举c（b+1~a*b*c<=1000000）,对应的a*b*c计数器+1，然后算前缀和，总共20行搞定。

L：不公平游戏，给出石子堆和两个人分别的拿的上限A, B，要求每次操作从某一堆拿一些石子（大于0），拿到最后的赢。先考虑公平，A=B或者x<=min(A,B),普通的博弈，找sg函数的规律。再考虑不公平，若A>B则先手必胜，否则先手需要一步把情况变成对自己有利的公平游戏，否则必败（考虑换到对面）。关键在于最后枚举从最大的一堆拿多少个使得结局满足要求，当然若x[n-1]>A则先手必败。

概述

自主训练第一场

2019 Suggestions 2

2018 ICPC CERC

Opentrains 6316

总结

dafu456

第一次晚上打比赛，感觉还不错，虽然我比较划水，但是今天题目的做法“非常精彩”。

我感觉我在哪里见过L题，是一个不公平游戏的博弈题，但是不是特别确定结论，就没有最先写。和peh讨论了一下I，我上去写，过了。dzf看了A，有思路，就写了，是对AC自动机的改写，然而有点曲折，最后还是过了。期间我和peh看了一下其他题的题面，C题的题面非常“耐人寻味”，好在peh最后看懂了。上去写的时候做法有点问题，然后我提了一个不标准的做法（难以证明、复杂度成迷的做法）就过了。后来我写了L，结论没记错真是万幸，虽然WA了一发，最后的情况漏了一个细节。J，peh单挑一发过。D题是神奇的物理题，peh物理大师上去先写了一发，挂了。我们看了题目之后，对题面产生了怀疑，我甚至产生了弃题的想法去做BG。最终我们还是在题意不明、没有clarification的情况下尝试了这题，推了相当久的物理公式，写了一些鬼都看不懂的变量名（我们过了以后半小时都不知道写了啥），脑袋都要掉了。封榜后，考虑G，WA，没办法。

啊，这场真神奇。

题解

C：dafu方法：每次暴力枚举往右移多少位，但是pow(40, 6)肯定会超时，“剪枝”是：每次移动的时候必须覆盖第一个0。不知道对不对，反正过了。

I：枚举a（1~100），里面枚举b（a+1~1000），再枚举c（b+1~a*b*c<=1000000）,对应的a*b*c计数器+1，然后算前缀和，总共20行搞定。

L：不公平游戏，给出石子堆和两个人分别的拿的上限A, B，要求每次操作从某一堆拿一些石子（大于0），拿到最后的赢。先考虑公平，A=B或者x<=min(A,B),普通的博弈，找sg函数的规律。再考虑不公平，若A>B则先手必胜，否则先手需要一步把情况变成对自己有利的公平游戏，否则必败（考虑换到对面）。关键在于最后枚举从最大的一堆拿多少个使得结局满足要求，当然若x[n-1]>A则先手必败。

附加文件