浙江省选一试讲课.ppt

考虑一个限制A,B，表示A必须在B之前弹出。 对于一个dp[l][r]若l=A=B=r，则A不能作为最后一个弹出，而其它都是可以的。 为什么呢？ 当Ax=B时显然成立。 当l=xA或Bx=r时对于一边是没有影响的，对于另一边在子dp中已经满足了A在B之前弹出。 若l=B=A=r，则B+1~A不能作为最后一个出栈。若这些成为最后出栈的数，则B显然会比A先被弹出。 枚举所有区间和x，判断是否可以转移。 那么我们就有了一个n^3m的做法。 令v[i][j][k]表示在dp[i][j]中k是否可以作为转移。 注意到在每个限制中，不能取的数一定是连续的，因此我们对于每个限制可以枚举每个区间，用并查集维护，时间复杂度降为n^2mα(n)。 观察一个限制A,B，对于它来说，有用的区间一定是l=min(A,B)且r=max(A,B)的，在二维平面中，这本质上构成了一个矩形。 因此我们只要枚举所有不合法的k，在这个矩形中表示出来就可以了。 表示的方法可以通过在4个端点中记录，dp的时候判断前缀和是否大于0就行了。 时间复杂度为n^3+nm。 在一根数轴上有n个怪物，第i个怪物所在位置为ai。 其中有m个点时特殊点，第i个特殊点所在位置为bi。 若两个怪物相邻，则不能将它们拆开，可以认为是一个块。 可以有一个或者多个怪物是一个块。 每次可以将一个块的怪物向左移动或者向右移动直到撞到怪物为止。 问最终最多有多少怪物能到达特殊点。 n=100000,m=2000。 5sec。 4 2 1 8 4 5 7 2 怪物与怪物之间顺序是不会变的。 我们考虑前i个怪物最多能到达多少特殊点。 对于第i个怪物，仅有两种可能。 1：不动。 2：向左移动。 而向左移动的前提是开始时第i个怪物与第i+1个怪物不在同一块。 分这两种情况转移。 枚举一个特殊点，表示最终这个特殊点一定会被怪物到达。 假如这个特殊点所在位置是x,第i个怪物所在位置为y，则相当于从第i-(y-x)个开始的怪物都得向右移动，才能到达这个特殊点。其中第x~y的特殊点都能被到达到。 注意怪物形成一块的情况。 我们可以枚举特殊点，表示这个特殊点最终一定会被到达，令x表示不超过该特殊点位置且位置最大的怪物的位置，这个可以预处理出来。 令y表示第i个怪物所在的位置。 那么当满足x~y的怪物个数不小于x与该特殊点距离时，便可以将这些点向左移动，转移即可。 总复杂度为O(nm)。 有两个栈分别有n和m个数。每次可以从其中一个栈中取出一个数。令k表示不同的输出序列总数，其中第i种输出序列产生方式有ai个。求Σai^2，答案对一个数取模。 n,m=500。 非常经典的题目。 考虑ai^2所表示的意义。 即相同对的个数。 那么我们令dp[i][j][a][b]表示第一种方案在第一个栈取了i个，第二个栈取了j个，第二种方案在第一个栈取了a个第二个栈取了b个且输出序列相同的方案总数。 转移非常简单，枚举下一次两种方案分别在哪个栈取。 实际上i+j=a+b，因此只要3维就能表示状态了。转移是O(1)的。 总复杂度为O(n^3)。 一个游戏里有k种装备，每种装备初始等级为1，每次打败一个怪兽，都会随机掉落一件一种类型的装备，他的等级为[1,t+1]中随机一个数x，其中t表示当时该类型的装备的等级。若x=t+1，则换上掉落的装备，否则不换，然后卖掉不用的装备，等级i的装备能卖i个金币，求打败n个怪兽后的得到的金币的期望。 n=100000,k=100. 根据期望的线性性，我们发现k并没有什么卵用。 可以拆分成k次子任务，即最终答案乘以k即可。 令dp[i][j]表示总共i次战斗，当前装备等级为j能获得的金币期望。 那么显然的有dp[0][j]=0。 对于dp[i][j]，枚举下一个怪兽爆的装备等级，统计期望。 有dp[i][j]=1/k*Σ(x=1-j+1)1/(j+1)*(dp[i-1][max(j,x)]+min(j,x))+(k-1)/k*dp[i-1][j]。 整理可得。 dp[i][j]=1/k*(j/(j+1)*(dp[i-1][j]+(j+1)/2)+1/(j+1)*(dp[i-1][j+1]+j))+(k-1)/k*dp[i-1][j]。 注：此处的/均为除而不是整除。 这样状态就是O(n^2)，转移就是O(1)啦！ 为了要得到一个等级为p的装备，就要在p-1的基础上期望打上kp次。总共为2k+3k+...+pk≈p^2k次。那么打败n只怪兽后，期望的装备等级为根号n/k级别的。 根据这个思路，我们可以推论，当状态dp[i][j]中j越大增加的值越小。 事实上，当n=100000,k=1时，在j700时只会产生非常细微的变化。 因此我们可以将状态中的第二维的上界设成一个界限B。 在保证精度的情况下，能较快