Training-2016.08.12
这场训练的题目可以在这里找到：2016 Multi-University Training Contest 5
计划改的题目： E,H(已补),J(已补)
这场训练的代码在这里
A题
题意：你的账户中有x块钱，但你不记得是多少钱了，只知道x是在[0, K]中均匀分布的整数。当你尝试取y块钱的时候，
如果剩余钱数≥y，则取出，否则则会受到警告。问在受到不超过w次警告的前提下，期望最少需要多少次可以将账户里的钱
全部取出？
设计DP状态f[i][j]表示剩余钱数在[0,i]区间均匀分布，且我还剩余j次警告，转移是
$ f[i][j] = min( f[k-1][j-1] * \frac{k}{i+1} + f[i-k][j] * \frac{i-k+1}{i+1} + 1) $
我们发现状态是O(n^2)的，转移是O(n)的，显然会TLE。
但我们又很容易找到这样一种决策：即每次折半去尝试，这样我保证最多只需要log(n)次即可将钱全部取出。
而最优决策肯定不会比这个决策差，也就是说，j我们只需要枚举到log(n)级别就可以了，并不需要枚举那么多，因为
答案并不会变优。
所以最终复杂度 $ O(n^2 * log(n)) $
C题
题意：给一个序列A，将其分成尽可能多的区间，且满足每个区间中的每个前缀和都大于等于0。
我们考虑从后往前贪心，对于一个a[i]<0，我们找到第一个j满足sum(j ~ i)>=0，则就可以从这里拆一段出来。
为什么是对的呢？如果中间又出现小于0的项怎么办呢？可以发现即使出现小于0的，也一定会在里面就被满足掉，不会
伸到外面来，因为如果伸到外面，则sum(j~i)也一定<0
D题
题意：给定平面上n个不同的点，问能组成多少个锐角三角形？N<=2000
考虑非锐角三角形的情况：三点组成的图形中包含了一个直角/钝角/平角，也就是说，锐角三角形数量就是
“三角形”的数量-直角-钝角-平角
所有角的数量-锐角-零角 = 直角+钝角+平角
所以我们可以枚举角的顶点，然后将剩余的点极角排序，扫一遍统计出锐角和零角的个数，就可以算出答案了。
Trick：
- 用叉积排极角序的时候必须找一个最左下角的点，否则反向共线的情况会出问题，当然如果排序时加上象限判断就不会有问题了。。。（但是这题这样会TLE）
G题
题意：定义K-wolf number为任意相邻k位数字均不相同的数，问[L,R]中有多少个 K-wolf 数。
数位DP，考虑f[i][sign][zero][mask][len]，表示还剩下i位数字需要确定，sign表示是否卡
到上界，zero表示是否前面全选了0（前导0不会加入k的限制）不能选的数的集合是mask，当前已经
确定的数的位数为len，的方案数。
转移挺弱的……
Trick：02和2是两种不同的集合，但是会映射到相同的mask，，这也是为什么我要记len，否则会出错……（写得丑的过）
H题
题意：给一棵树，每个点有个权值(1~100000)，每个点的收益是它的子树的权值的中位数，现在你可以将一个点的权值改为100000，
问最大总收益是多少。
我们将第i个点的权值改为100000后，只有从它到根的路径上的点的收益可能会变化，发生变化的点是那些mid[j] <= a[i]的点j，
它们的收益将会从原来中位数变成中位数后面那一个。也就是说，只要我们能够求出每个点的子树中权值的中位数和中位+1的数，就
可以用树状数组来维护答案了。而子树中第k大的权值我们可以用dfs序+主席树方便地求出。
而树状数组维护答案是这样的：dfs整棵树，树状数组中存储的是从点x到根的路径上所有的点的答案的增量，每走到一个点x，我们就
将增量md2[x] - md[x]放在md[x]的位置上，表示如果我们选取了一个小于等于md[x]的人将他的权值改为100000后，就可以得到
这个增量，求出当前这个人x修改后总收益的增量就是在树状数组中求一个后缀和。
J题
题意：给n个字符串，n<=10W,串长总和<=10W,问从第L个字符串到第R个字符串有多少个不同的前缀？
转化题意，相当于问从L到R这些字符串在Trie树中的节点个数。
那么一个字符串对应着Trie上的一些节点，把节点编号当做hash值，即问从L到R这几组值中，不同的值有多少个。
这个问题我们可以用可持久化线段树来做：
对每个位置i，我们都记一个next[i]表示value[i]下一次出现的位置，那么要求[L,R]中不同的值有多少种，就相当于是问[L,R]中next>R的有多少个。
那么我们可以以next为时间轴，倒着插入下标i到权值线段树中，那么以rt为根的线段树就表示next>=rt的下标位置有哪些（下标作为权值）这样就可以做到O(logn)查询了（嗯查询跟普通线段树一样）
K题
题意：给两个序列A，B，问有多少对（A’,B’）分别是A、B的子序列，且A’=B’。
DP：设f[i][j]表示A的前i位，B的前j位的答案，转移则是：
f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + (a[i]==b[j]) * (f[i-1][j-1] + 1)
意思是，f[i][j]要加上不包含j的所有的合法序列、不包含i的合法序列，但是同时不包含i和j的被算了两次，
所以要减掉。而如果a[i]==b[j]，则f[i-1][j-1]中的所有合法序列我都可以在后面添上a[i],b[j]这一对，
构成一个新的合法序列，最后再+1则是a[i],b[j]单独构成一个合法序列。
An undergraduate at Shanghai Jiao Tong University who studies CS.