2016-E09-team2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||TaZoF||E||MLE|| || ||G++||1904||2016-10-04 16:53:36||
||TaZoF||E||MLE|| || ||G++||1883||2016-10-04 16:51:26||
||TaZoF||E||WA|| || ||G++||1884||2016-10-04 16:48:10||
||TaZoF||D||AC||1648||2308||G++||1876||2016-10-04 16:42:37||
||TaZoF||D||WA|| || ||G++||1807||2016-10-04 16:20:39||
||TaZoF||B||WA|| || ||G++||814||2016-10-04 15:36:35||
||TaZoF||E||MLE|| || ||G++||1798||2016-10-04 15:21:56||
||TaZoF||E||MLE|| || ||G++||1743||2016-10-04 15:20:05||
||TaZoF||E||MLE|| || ||G++||1705||2016-10-04 15:17:46||
||TaZoF||E||MLE|| || ||G++||1807||2016-10-04 15:11:01||
||TaZoF||E||RE|| || ||G++||1949||2016-10-04 15:04:54||
||TaZoF||E||MLE|| || ||G++||1765||2016-10-04 14:50:11||
||TaZoF||G||AC||9416||109||G++||1022||2016-10-04 14:49:07||
||TaZoF||E||MLE|| || ||G++||1665||2016-10-04 14:38:31||
||TaZoF||E||RE|| || ||G++||1665||2016-10-04 14:38:01||
||TaZoF||E||RE|| || ||G++||1646||2016-10-04 14:34:21||
||TaZoF||E||MLE|| || ||G++||1647||2016-10-04 14:33:35||
||TaZoF||G||WA|| || ||G++||1019||2016-10-04 14:15:34||
||TaZoF||A||AC||1888||374||G++||476||2016-10-04 13:36:41||
||TaZoF||A||WA|| || ||G++||571||2016-10-04 13:23:29||
||TaZoF||L||AC||5412||624||G++||1284||2016-10-04 13:00:04||
||TaZoF||K||AC||5564||171||G++||676||2016-10-04 12:42:47||
||TaZoF||C||AC||9240||1310||GCC||389||2016-10-04 12:29:13||
== 流水账 ==
开场我们很快过了三个简单题，'''C1y14'''，'''K1y27'''，'''L1y45'''。之后我与hzf学长讨论A题，starve学长写G。A题在忽略了一个问题错了一次之后'''A2y81'''。starve学长的G貌似碰到了一点问题，我替学长写G，不过一开始错了...starve学长发现E似乎是回文树裸题，我检查G的时候学长就在写E，然而不断MLE...G题我把记忆化部分去掉之后就通过了，不过不是很理解，准备结束后再思考思考，'''G2y154'''。
之后starve学长继续尝试节省E的空间但是并没有成功，hzf学长似乎想到了B和J的做法，可惜后来都发现了错误。最后starve学长放弃了E写了写D，'''D2y272'''。最后我们想了想E，觉得只要用Manacher就可以了，但是时间不太够了。
== 总结 ==
* 做得不好的地方
* 套用模板太盲目，而且模板比较偏。套用之间时空复杂度没有仔细分析。
== 题解 ==
C,G,K,L比较简单，略过...
=== A - ATM Machine ===
设f[i][j]表示还有i次警告，且已知ATM里最多还有j的钱的期望步数。由于ATM机里有多少钱是等概率的，所以如果我们这次取走了k的钱，就会有k/(j+1)的概率被警告，(j+1-k)/(j+1)的概率不被警告。所以容易得到转移方程f[i][j] = min(k/(j+1)*f[i-1][k-1] + (j+1-k)/(j+1)*f[i][j-k])。
这是一个三方的转移方程，但是我们知道，如果警告次数大于log次，只要使用二分的策略就可以了。所以我们只要预处理i = 0~15的情况即可，这样就是O(n^2^logn)的了。读入询问的时候把警告次数和15比较一下，如果高于15就当作15.
=== D - How Many Triangles ===
找锐角三角形不太容易，我们把问题变成找钝角和直角三角形。我们只要枚举钝角或直角的顶点，然后把其它点极角排序一下就能用线性的时间做了。应该还是比较经典的方法。
=== E - Interesting ===
设L[i]表示所有右端点在i处的回文串的左端点位置之和，R[i]表示所有左端点在i处的回文串的右端点位置之和。显然答案就是对所有L[i]*R[i+1]求和。
L[i]应该怎么算呢？如果我们能用sumL[i]表示所有右端点在i处的回文串的中心位置之和*2，sizL[i]表示所有右端点在i处的回文串的数量。很显然我们有L[i] = sumL[i]-sizL[i]*i，R[i]同理。因为我们要从左到右枚举i，所以只要用差分的方式算出sumL[i]和sizL[i]。
=== J - Prefix ===
感觉是出题人的恶意，空间给得那么少...？
如果我们能把所有字符串的前缀哈希一下，这个问题就变成了“求一段区间内有几种不同的值”。这个问题强制在线的话可以用可持久化线段树来完成。
不过哈希函数不是很靠谱...我们可以改用一棵Trie树来维护所有字符串的前缀。
== 补题 ==
=== TsReaper ===
~~E~~,H,~~J~~| User | Problem | Result | Memory | Time | Language | Length | Submit Time |
| TaZoF | E | MLE | G++ | 1904 | 2016-10-04 16:53:36 | ||
| TaZoF | E | MLE | G++ | 1883 | 2016-10-04 16:51:26 | ||
| TaZoF | E | WA | G++ | 1884 | 2016-10-04 16:48:10 | ||
| TaZoF | D | AC | 1648 | 2308 | G++ | 1876 | 2016-10-04 16:42:37 |
| TaZoF | D | WA | G++ | 1807 | 2016-10-04 16:20:39 | ||
| TaZoF | B | WA | G++ | 814 | 2016-10-04 15:36:35 | ||
| TaZoF | E | MLE | G++ | 1798 | 2016-10-04 15:21:56 | ||
| TaZoF | E | MLE | G++ | 1743 | 2016-10-04 15:20:05 | ||
| TaZoF | E | MLE | G++ | 1705 | 2016-10-04 15:17:46 | ||
| TaZoF | E | MLE | G++ | 1807 | 2016-10-04 15:11:01 | ||
| TaZoF | E | RE | G++ | 1949 | 2016-10-04 15:04:54 | ||
| TaZoF | E | MLE | G++ | 1765 | 2016-10-04 14:50:11 | ||
| TaZoF | G | AC | 9416 | 109 | G++ | 1022 | 2016-10-04 14:49:07 |
| TaZoF | E | MLE | G++ | 1665 | 2016-10-04 14:38:31 | ||
| TaZoF | E | RE | G++ | 1665 | 2016-10-04 14:38:01 | ||
| TaZoF | E | RE | G++ | 1646 | 2016-10-04 14:34:21 | ||
| TaZoF | E | MLE | G++ | 1647 | 2016-10-04 14:33:35 | ||
| TaZoF | G | WA | G++ | 1019 | 2016-10-04 14:15:34 | ||
| TaZoF | A | AC | 1888 | 374 | G++ | 476 | 2016-10-04 13:36:41 |
| TaZoF | A | WA | G++ | 571 | 2016-10-04 13:23:29 | ||
| TaZoF | L | AC | 5412 | 624 | G++ | 1284 | 2016-10-04 13:00:04 |
| TaZoF | K | AC | 5564 | 171 | G++ | 676 | 2016-10-04 12:42:47 |
| TaZoF | C | AC | 9240 | 1310 | GCC | 389 | 2016-10-04 12:29:13 |
流水账
开场我们很快过了三个简单题，C1y14，K1y27，L1y45。之后我与hzf学长讨论A题，starve学长写G。A题在忽略了一个问题错了一次之后A2y81。starve学长的G貌似碰到了一点问题，我替学长写G，不过一开始错了...starve学长发现E似乎是回文树裸题，我检查G的时候学长就在写E，然而不断MLE...G题我把记忆化部分去掉之后就通过了，不过不是很理解，准备结束后再思考思考，G2y154。
之后starve学长继续尝试节省E的空间但是并没有成功，hzf学长似乎想到了B和J的做法，可惜后来都发现了错误。最后starve学长放弃了E写了写D，D2y272。最后我们想了想E，觉得只要用Manacher就可以了，但是时间不太够了。
总结
- 做得不好的地方
- 套用模板太盲目，而且模板比较偏。套用之间时空复杂度没有仔细分析。
题解
C,G,K,L比较简单，略过...
A - ATM Machine
设f[i][j]表示还有i次警告，且已知ATM里最多还有j的钱的期望步数。由于ATM机里有多少钱是等概率的，所以如果我们这次取走了k的钱，就会有k/(j+1)的概率被警告，(j+1-k)/(j+1)的概率不被警告。所以容易得到转移方程f[i][j] = min(k/(j+1)*f[i-1][k-1] + (j+1-k)/(j+1)*f[i][j-k])。
这是一个三方的转移方程，但是我们知道，如果警告次数大于log次，只要使用二分的策略就可以了。所以我们只要预处理i = 0~15的情况即可，这样就是O(n2logn)的了。读入询问的时候把警告次数和15比较一下，如果高于15就当作15.
D - How Many Triangles
找锐角三角形不太容易，我们把问题变成找钝角和直角三角形。我们只要枚举钝角或直角的顶点，然后把其它点极角排序一下就能用线性的时间做了。应该还是比较经典的方法。
E - Interesting
设L[i]表示所有右端点在i处的回文串的左端点位置之和，R[i]表示所有左端点在i处的回文串的右端点位置之和。显然答案就是对所有L[i]*R[i+1]求和。
L[i]应该怎么算呢？如果我们能用sumL[i]表示所有右端点在i处的回文串的中心位置之和*2，sizL[i]表示所有右端点在i处的回文串的数量。很显然我们有L[i] = sumL[i]-sizL[i]*i，R[i]同理。因为我们要从左到右枚举i，所以只要用差分的方式算出sumL[i]和sizL[i]。
J - Prefix
感觉是出题人的恶意，空间给得那么少...？
如果我们能把所有字符串的前缀哈希一下，这个问题就变成了“求一段区间内有几种不同的值”。这个问题强制在线的话可以用可持久化线段树来完成。
不过哈希函数不是很靠谱...我们可以改用一棵Trie树来维护所有字符串的前缀。
补题
TsReaper
E,H,J
附加文件
- 2016-E09-team2.zip by TsReaper
- E.cpp by TsReaper
- J.cpp by TsReaper