2018-Reconquista-C4
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
''' The 35th Petrozavodsk Programming Camp - Contest 2: Ivan Kazmenko Contest 2 '''
[https://official.contest.yandex.com/ptz-summer-2018/contest/8782 Yandex]
== 流水账 ==
【jsb视角】开场10min威威就把A的交互给过了，感觉状态奇好？D是道检索文章的非传统题，懒得写分词，莽了一个字母频率的简单程序，WA26后跑路了。之后跟榜不太顺利。签了B和E后，C磕磕绊绊才搞出来：此时一半时间已经过去。被屠榜的F我们面面相觑不会做，后来我东想西想搞了一个很麻烦的分块打表做法。感觉机位上挣扎了好久，好不容易调对，TLE33。然后不断地修改，打更多的表（与此同时代码长度++，gedit卡的程度++），把map改成哈希，加读入输出优化……感觉万事俱备时，竟然蜜汁ILE34了>_<。以前我从来没遇到过这个问题，挣扎了半天也不知道为啥。很快就封榜了，队友们J没开出来。我就把F打印了给他们看（也没看出啥问题）,短暂地看了看别的题，也没啥思路。
== 总结 ==
=== lsmll ===
对于这场的结果，我认为我作为队长必须要自我检讨，没有对队伍的比赛策略进行干预，让jsb一直连续上机搞F题近2h，特别是根据榜我已经预感到了F题可能不是我们这样做的，可能有更简单做法的情况下。以后再出现这种上题超过1h无果应该果断考虑弃题，或者考虑是否有别的做法。当然，我和lzw没有开出别的题，可能也是个人水平上需要提高。其实D、H题都并不难，如果早点进行调整可能可以做出来。
=== jsb ===
上机搞F，结果自己被搞得意识模糊。[[br]]
要调整策略，学会果断放弃。[[br]]
=== lzw ===
看到F被屠榜就觉得肯定不是像jsb那样打表做的，但是又想不到别的做法，感觉打表也能过，就一直让jsb在机位上调试。J题想了1h+也没有想出来，其实应该早点放弃换别的题。另外有必要提高个人水平，以后有空就做做cf和atcoder的virtual提高一下智商，毕竟个人水平至少能保证题数的下限。
== Solution ==
A: 考虑在无穷远处放半径很大的圆，可以近似看做半平面，用半平面二分出横纵坐标。
B: 每个地址用一个栈模拟进出即可。摊还分析复杂度是线性的。
C: 如果s和t有一位相同，直接搞，否则删掉s的第一位然后check和t相同的位数是否至少有2位。
D：对每个字母k分开考虑：找到所有包含它的串s，暴力枚举s中每个k是否删，得到一些s'。如果s'不在文章中出现，也不是其他字母的s'，那么只要我们遇到s',答案就是k。把每个字母合法的串都预处理出来，随机打乱取前K个，打表一下即可。
E：考虑每个罗马数字的正负号，如果它右边权值比它大的罗马数字种类是奇数个就是负号，否则正号。从右往左加罗马数字，d[val][mask]表示当前值是val，mask是2^7^维护一个类似LIS的东西，然后每次转移往左边加罗马数字，BFS即可。
F：通过第一个x知道s mod 1000000是多少，然后每次加1000000暴力枚举s，通过前面若干个x判断s是否合法。找到s后直接O（n）求出所有x。
G:
H: 直接维护一个长度为100的数组，即可求出2^4^中情况的概率分布。对于给出的情况，算出每种数字出现的比例，和每个概率分布的比例求个距离，找个最近距离拟合即可。
I:
J: 考虑两个筛子a和b，把它们变成a xor b和b不影响答案。 重复这个过程，不断用长度小的去xor长度长的，最终使得a和b都相同，类似辗转相减的过程。最终把n个筛子变成了一个。根据剩下那个的长度判断即可。答案是2的幂次。
See also attachment.
== 补题 ==
D [jsb]
F [lzw]
G []
H [jsb]
I []
J [lzw]Contest Information
The 35th Petrozavodsk Programming Camp - Contest 2: Ivan Kazmenko Contest 2
流水账
【jsb视角】开场10min威威就把A的交互给过了，感觉状态奇好？D是道检索文章的非传统题，懒得写分词，莽了一个字母频率的简单程序，WA26后跑路了。之后跟榜不太顺利。签了B和E后，C磕磕绊绊才搞出来：此时一半时间已经过去。被屠榜的F我们面面相觑不会做，后来我东想西想搞了一个很麻烦的分块打表做法。感觉机位上挣扎了好久，好不容易调对，TLE33。然后不断地修改，打更多的表（与此同时代码长度++，gedit卡的程度++），把map改成哈希，加读入输出优化……感觉万事俱备时，竟然蜜汁ILE34了>_<。以前我从来没遇到过这个问题，挣扎了半天也不知道为啥。很快就封榜了，队友们J没开出来。我就把F打印了给他们看（也没看出啥问题）,短暂地看了看别的题，也没啥思路。
总结
lsmll
对于这场的结果，我认为我作为队长必须要自我检讨，没有对队伍的比赛策略进行干预，让jsb一直连续上机搞F题近2h，特别是根据榜我已经预感到了F题可能不是我们这样做的，可能有更简单做法的情况下。以后再出现这种上题超过1h无果应该果断考虑弃题，或者考虑是否有别的做法。当然，我和lzw没有开出别的题，可能也是个人水平上需要提高。其实D、H题都并不难，如果早点进行调整可能可以做出来。
jsb
上机搞F，结果自己被搞得意识模糊。[[br]]
要调整策略，学会果断放弃。[[br]]
lzw
看到F被屠榜就觉得肯定不是像jsb那样打表做的，但是又想不到别的做法，感觉打表也能过，就一直让jsb在机位上调试。J题想了1h+也没有想出来，其实应该早点放弃换别的题。另外有必要提高个人水平，以后有空就做做cf和atcoder的virtual提高一下智商，毕竟个人水平至少能保证题数的下限。
Solution
A: 考虑在无穷远处放半径很大的圆，可以近似看做半平面，用半平面二分出横纵坐标。
B: 每个地址用一个栈模拟进出即可。摊还分析复杂度是线性的。
C: 如果s和t有一位相同，直接搞，否则删掉s的第一位然后check和t相同的位数是否至少有2位。
D：对每个字母k分开考虑：找到所有包含它的串s，暴力枚举s中每个k是否删，得到一些s'。如果s'不在文章中出现，也不是其他字母的s'，那么只要我们遇到s',答案就是k。把每个字母合法的串都预处理出来，随机打乱取前K个，打表一下即可。
E：考虑每个罗马数字的正负号，如果它右边权值比它大的罗马数字种类是奇数个就是负号，否则正号。从右往左加罗马数字，d[val][mask]表示当前值是val，mask是27维护一个类似LIS的东西，然后每次转移往左边加罗马数字，BFS即可。
F：通过第一个x知道s mod 1000000是多少，然后每次加1000000暴力枚举s，通过前面若干个x判断s是否合法。找到s后直接O（n）求出所有x。
G:
H: 直接维护一个长度为100的数组，即可求出24中情况的概率分布。对于给出的情况，算出每种数字出现的比例，和每个概率分布的比例求个距离，找个最近距离拟合即可。
I:
J: 考虑两个筛子a和b，把它们变成a xor b和b不影响答案。 重复这个过程，不断用长度小的去xor长度长的，最终使得a和b都相同，类似辗转相减的过程。最终把n个筛子变成了一个。根据剩下那个的长度判断即可。答案是2的幂次。
See also attachment.
补题
D [jsb]
F [lzw]
G []
H [jsb]
I []
J [lzw]
附加文件
- 2208_gassa_tutorial.pdf by lsmll