2018-team11-016
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(HW11.PNG,700px)]]
== 总结 ==
=== zb ===
今天打到一半脑子有点不行了，出去水了会手机，真实脑袋疼，可能是没休息好。
状态还可以吧，没太大遗憾，尽力而为了，不过周哥是真的厉害，把D给过了。
其实剩下的题我应该能做出来的，后来状态也不太行。
=== zyh ===
D题上来一看想了一会就秒了，上机写完交就是WA。这时候应该自己随便出点数据测一下，但我查代码逻辑查了半天也没想着手玩的事。
而且也不该查不出来还吊在那里，白白浪费很多时间，以后一定要注意。
=== sj ===
读了几个题，想了L的做法，摸鱼。
== 题解 ==
A.ATM Mechine
题意：取出所有余额，余额不超过K，余额不足会失败，最多失败W次，问期望操作次数。
做法：直接暴力转移所有状态，观察到W很大后无意义，状态数其实很小。
C.Divide the Sequence
题意：最多把一个序列分成多少个每位前缀和都大于0的串
做法：倒着枚举，和大于0答案+1重新计数
D.How Many Triangles
题意：给若干个点，求能画出多少不同的锐角三角形。
做法：锐角三角形个数等于锐角个数减去钝角个数*2再/3。0°算锐角，180°算钝角可以解决共线问题。枚举一个点再按极角序排序后枚举另一个点求出多少锐角即可。复杂度O(n^2^log(n))
极角排序不能直接用graham的cmp函数，没法处理平角和0度角的比较。于是就用了atan2，但是这个函数很慢，所以预处理出每两个点调用atan2的结果。
但是最后也跑了4992/5000ms，觉得应该有更优雅的做法。
E.Interesting
题意：求Σi*j i到j由俩个回文串组成。
做法：manacher预处理，然后求出每个位置作为起点和重点的回文串下标之和。
G.K-wolf Number
题意：[L,R]有多少相邻K位互不相同的数。
做法：数位dp，注意前导0的问题即可。
K.Two
题意：俩个数组有多少对相同子序列。
做法：f[i][j]表示以i,j结尾答案，转移统计即可。
L.World is Exploding
题意：求一个序列中两个不重叠的升序对和降序对的总数。
做法：容斥，先预处理以每一个点为终点/起点的升序对/降序对个数。总升序对和降序对个数乘积-在某一个点有重合的对数。
总结
zb
今天打到一半脑子有点不行了，出去水了会手机，真实脑袋疼，可能是没休息好。
状态还可以吧，没太大遗憾，尽力而为了，不过周哥是真的厉害，把D给过了。
其实剩下的题我应该能做出来的，后来状态也不太行。
zyh
D题上来一看想了一会就秒了，上机写完交就是WA。这时候应该自己随便出点数据测一下，但我查代码逻辑查了半天也没想着手玩的事。
而且也不该查不出来还吊在那里，白白浪费很多时间，以后一定要注意。
sj
读了几个题，想了L的做法，摸鱼。
题解
A.ATM Mechine
题意：取出所有余额，余额不超过K，余额不足会失败，最多失败W次，问期望操作次数。
做法：直接暴力转移所有状态，观察到W很大后无意义，状态数其实很小。
C.Divide the Sequence
题意：最多把一个序列分成多少个每位前缀和都大于0的串
做法：倒着枚举，和大于0答案+1重新计数
D.How Many Triangles
题意：给若干个点，求能画出多少不同的锐角三角形。
做法：锐角三角形个数等于锐角个数减去钝角个数*2再/3。0°算锐角，180°算钝角可以解决共线问题。枚举一个点再按极角序排序后枚举另一个点求出多少锐角即可。复杂度O(n2log(n))
极角排序不能直接用graham的cmp函数，没法处理平角和0度角的比较。于是就用了atan2，但是这个函数很慢，所以预处理出每两个点调用atan2的结果。
但是最后也跑了4992/5000ms，觉得应该有更优雅的做法。
E.Interesting
题意：求Σi*j i到j由俩个回文串组成。
做法：manacher预处理，然后求出每个位置作为起点和重点的回文串下标之和。
G.K-wolf Number
题意：[L,R]有多少相邻K位互不相同的数。
做法：数位dp，注意前导0的问题即可。
K.Two
题意：俩个数组有多少对相同子序列。
做法：f[i][j]表示以i,j结尾答案，转移统计即可。
L.World is Exploding
题意：求一个序列中两个不重叠的升序对和降序对的总数。
做法：容斥，先预处理以每一个点为终点/起点的升序对/降序对个数。总升序对和降序对个数乘积-在某一个点有重合的对数。
附加文件
- HW11.PNG by szb