集训队作业part1topcode50题part

1、第一部分: TopCoder 题目泛做： : 说明50 道题, 并填写每题题目大所有题目来自于TopCoder :关于TopCoderArena的使用可见SRM的序号, 可到ArenaPractiseRoomsSRM中寻找, SRM仅需做DivI 的分数最高一题(LevelThree, 1000分)TopCoder Arena 仅接受面象语言Java/C+/C#/VB. 因此使用Pascal 的同学可以考虑学习使用C+, 或者也可以去TopCoder 主页上测试数据进行离线测试。测试数据的方法为：打开TopCoder 主页AlgorithmMatch Archive选择相应的比赛选择一个DIV

2、 I Leader(点ID 前面的黄色小圆点)进入到Statics 之后选择最下方相应的/stat?c=problem 泛做表格状态1，方向指向N。并往反方向进行下一走K(K=4*108)步能取i1方向起ai 设数组 fi记录两个信息：1）到达i1 方向的最小步数；2）设数组ci表示从位置i1fi更新 fj(i=0 的最小非负整数tmp时间复杂度是O(1)算法总复杂度为状态在 两行，而且M=22，所以很容易联想到状态压缩 DP。M+1 个格子覆盖状态为k 所用的最值得注意的是，k 最大为 223，如由于只有四种连通块可用，它们对 k 值的影响是有限的，也就是说，很多 k 值次只需要枚举出现过的

3、 k 值就可以，不k 216。算法总复杂度为状态定义有趣数为：十进制下，每一位（非首位）数字都比它前一位divisor(divisor=500) 整qi表示i 1 的十进制数。有趣数可表示成 qa1 + qa2 + 500qi%divisor是循9q 出来。fijkij个 q组成的数余数为k的个数。转移时需要1状态有 n(2=n=50) 支球队，0到n-1。每支球队都有一个初始分4 场比赛1分0球队最高是多少？4n个结果，必须保证赢的个数fijki支球队，赢球队0 的最高。转移时，对每支球k 场匹配。注意：为使球队0 靠前，规时间复杂度为O(n*8n*4n*43)5状态4 7 组成的数为幸运数

4、，能被幸运数整除的数为近似幸运数。问：a到b之间，1b的近似幸运数1 a-1 的近似幸运数个数。数倍数的幸运数，共有 1000 多个。状态按照下图规律构建f(x)示左点集前i 位匹配右点集状态j 费用。转移时，枚举左点集 i状态N*N(N=18) 第 i 行字符C的个数为 Ai。现可以将C往向干，要求使得第 i 列字状态定义除数四元组a,b,c,d为存在某个数的所有约数%40,1,2,3枚举四元组a,b,c,d，总共是 504O(1)状态在 N*M 的矩阵要求每一行或每一列都不能有相同的数，问：字典序最小的填法？ r*c 的矩阵存在合法填法当且仅当任意 di都小于等于 min(r,c)。 N(

5、N=20)个点的无向图，现要求添加连通块，并且任意两点之间最多只有两条简单路径，问：有多少种不生 成树个 数公式： nm2 m ai。n 是总点数，mb12*b22*bk2*(k-1)!/2。结合(b1 b2 bk) (b1 + b2 bk) (k1)!nmk1 m ai。根据乘法 k 的乘积和。进而求出情况 3。 起来比较疼状态花园里有一堵墙，现要用给出N(1N=40)条边靠墙围一块矩形许把任意一条边砍成两段，问：矩形面积最大Sum 为是所有边的总和。假设墙X 没有包考虑墙的邻边Y 时，可转换成X 状态N(2=N=100) 个点，M(=50)条边的有向图，每条边都有一个距Ace0走到点一条边

6、是损毁不能走 e 问，情况下，Ace从点0 1 首先对于点 i，求出任意删去连接它的边后，情况下，到达终点1 的距然后从终点 1 出发做一次特殊的 dijstrai的最短路必须大于等di。10 的最状态K（K=100）跳看作父节点，中兔子往左跳看作设数组fijk表示经过i次跳跃当前位置深度为 j，当前位置与目标位置 LCAk 的方案数。转移只需要考100次跳跃，j的范围也就只有 200。时间复杂度为状态给定一幅 N(N,=50)地图里有一个和一个出空和还有77 种颜色，可压缩表示。fijvk当前位置(i,j)安全颜色状态为v，颜色为k 状态下到达pi的机率是的。现最多只能经过一次的格子，问：根

7、据最优状态N(N=5000)个格子，终点在格子 N，有一颗 子，为1至d。每一次移动，用扔出一z，然后棋子向前移z步，假如超过了N，Alice的棋子所在的位置 x， Bob 棋子所在的位置y，Alice 开始，Alice 和 当棋子到达N-d,N-1后，他每一次子都在N-d,N-1A获胜概率为 A N-d-x 步就能保证棋子到达N-d,N-1BN-d-y 步。因AB N-d-min(x,y)就能保证两者都在N-d,N-1，可用公式直接计算A 的获胜概率。状态给 定 一 幅 N*M 8 个。Alice 能对Alice 共有多少种不同的假如用二进制表示行和列是否已经被全变成黑色，那状态将到达 24

8、0。仔细观察可以发现，那些初始时不存在黑而不存在黑点的行和列只需要个fijrc表示初始存在黑点ij，和初始不存在rc 的状态下方案 d(n,d=9)和一个原始串 s(s.size=50)， 定义合法s.size相等，任意连续 n 个字符出现的不同字符小于等等于原始串 s 的合法字k(k=1018)小的合法字符串是什fiji 个字符已经固nj的状态能字符是可以任意取的，所以最后 n 个字少个字符。因此定义 n 个字符压缩规则当前新加字符在最后 n 个中没有出现，则在j 末入1；2，当前新加字符在s k 状态给定一幅无向图，有若干个点，总点数不100i 行上的点i-1i+1行存在边n行会与1行存在

9、边。问：该图的n 为偶数，那图10。那么把这一层单独提取N=47 部分配AliceBob看。A和 两人都把所有看AB的队列A 的队列空的情况，分配给 A的需要t时间看完，B看完第一部需要 tb1，假如 ttb1，则 A 队列空了。B看完第二部需要时间tb1，假t+ta1=2 时，必定是每一行或是每一列以 XYXY 这种字符交替出现N或M1时特殊处理。现只讨N,M=2。最终答案是行的方案数+列的方案iXYXYk格子的方XYXY出现的，只要规定一2*2 的矩阵，就规定了这幅图。最多状态在一副 放至多 10 种不同的棋子，每种有若干颗，总棋子数=N*M。任意一行或一列只允许摆放相同种类的棋子。问：有

10、多少种不同的摆放方gkijk 种棋子恰好占据了 i 行 j 列的方案数。设数组fkij表示前k种棋子恰好占据了 i 行 j 列的方案数。通过数组 g 组合出来。状态给定一幅N(N=14)N 个点的有根树，问：图中进行求解。DP Fijk表示表示图k，以点 j 为根的生成树有多少状态有N(N=50)只兔子算出兔子的最高以及最低得分。现给定 x 和 y(x,y=N)，问：最终排x y 只兔子设数组Fijk表示兔子i 为选中的k 兔子的组合。为了方便转总的时间复杂度为状态给定一幅 N(N=50)个点的有向图， 0同在任意一点都能到达 0。 反方向通过人数的上限。现在图上随机分布 修改一些边上的权值，

11、使得任何情况下，所有每一个点必须保证顺时针和逆时针走到出口的人数和不小于 N。而且对于相邻的人数是 Num，那么点 j 往同方向的必须不少于NumDP fij表ij 人顺时针走到出口，逆时针有 N-j人的代价。DP转移要稍微优化一下。算法时间复杂度是O(N*M)状态给 定 一 棵 N (N=200)的有根树，最多可添加 K(K=100)条额外边，问：从根出发遍历树上所有边后回到2*k 个表示以点i 为根的里固定了j 个额外状态有NK种子里某一种苹果最多有 子的集合，然后这些箱子里选一个苹果。问：每种苹果被选中的概率fiji，苹果j k 种苹果的概率为N Sum_Apple fijNum / j

12、i=1 k in 重点在于如何求fij，Sum_Apple 最多500000i 都单独求一次定义数组gj表示不包含箱子i 组成j 的概率，tj表示所有箱子组成苹果总数为ji苹果处理出所有箱子的 g 时间复杂度是状态N 个人按某顺序排现 给 定 限 定 时 间 T(T=222) ， 人 数N(N=18)以及排列的限制，问：有多少种排列T 时间里所有人都443222即，假如被两个人卡住，则所需的当前的不是未集合中最大的，但比已经的最小的大，那么未中最大的人必定当前的比已经的最小 小，那么，比它大的的人只会示状态，i 表示已的集合，j 表示排列。时间复杂度为O(N*2N)状态一种数字加密方 法：把连

13、续 X 个相同的 个长度=500 的经过来若干个不相邻的字符作为 Y，而且要求若干个不相邻的字符作为 Y，而且要求Y不能相等。而这里的可选的Y 跟一次还原的X 有密切关系。DPFijk表示状态，i表i个已经进行还原一次还原，j表示状态经典的路人关灯问题+特殊的二分图限制条件。问：最小的花费只有16 台和16 个数，数据规模不大，考虑用压缩 DP 进行求解。DPFijk表示状态，i表示当前经过的的区间的左端点；k是二进制数，表示哪些数还没打印；j表示当前位置在左端点还是右端点。 Fijk记录打印剩余的数需要还需要状态有N(N=20)个已知M(M=4)个待定码可选-1,0,134种情况，每种状态现

14、有 重量 X，每一次都会用给定N(N=N)，L(x)x 张卡表需写的个数的上限。答案必定符合 状态有两个点数不超过 50 的凸包，外凸含着内凸包。随机在外凸包上选一个点，找到凸经过这两点的直线穿过a 和凸包上的一条边，求出该边a 为最远点的点集区间。枚举bab的中垂线，求出a b 点优a 为光源，求内凸包O(n3)。思路很清状态平面上有N(N=50)个点，要求画两个互不相交的凸包覆盖所有的点，问：两个凸包面积较大值的最小值是多N2 条边。枚举状态定义函数 f(x)=x/m (x m 的倍数)x+1m,n (m,n=106)，问：有多少个数经过n次f函数后刚好第一次变成 1？g(x)x 次恰好第

15、一次1 有多少个。一个数经过一步可变成两个数，一个是 x-1，一个是 x*m。简单推算 g(x)=g(x-1)*2。但这样会出现一些不合法的情况。例如 1*m-(m-1)=1。 状态Alice,Bob F 三人玩射击，给出每个9 种，每一列 举 每 种 结 果 对 scoreA,killedA,数最小可能是多少，最入绝对值都小于等于 121,2组出现的次XF 取胜的回合数。根据 1,2 组的次数，对 killedF F 取胜回合数X 是否合法。最时间复杂度为O(10002)状态m(m=40)棵树，能种在每棵树要求相邻的树与它有一定距离，问：有DP Fijki 棵树，j+1 块紧连着的连接块，j

16、 个间隔，m棵树连成一块连接块需要占 后m+1个位置空格，那方案数就是状态一幅上下无限延伸的 地 图 由 N*M(N,M0mid需要变大，否则mid 需要变小。ai bj 匹配的费用是-max(a*b,a+b)+mid*min(a*b,a+b)，求取 K 个匹配的最小费用。spfa 求 状态给定一幅 N(N=20)个点的无向图，通过每现有 M(M=20)个晴天段，每次移动都要在晴天下。时光机能回到过去时刻，但花费时间是过去时刻与当前时刻的时间差，而且时光机启动一次需额外花费时间 T(T=109)，问：从 0到 N-1 所需的最小时AB，枚举可能用KA到Bdijkstra作预处理，然后再用类似d

17、ijkstra 计算从关状态N*M (N,M=100)的图，里面有空地，有，现要在空地中选一些点组成一个凸型，问：有多少Fvijk1k2：v表示第几行；i，j表示连续块的左右端点；k1，k2 分别表示 算法总时间复杂度O(N*M2)状态) 黑白矩阵里，每次选定一个格子使它与周围 方）都取反色。初始全部格子都是黑色，每个格子只能点一次，问：列中涉及的元的个数 k。最后答案为 状态大楼有H 层， 0H-1N 座电梯， 0至N-1。电梯有初始的位置，并且它们移动时相对距离不变。电H/N 步，要求每一层都有电梯停留过。问：有多少种不同的初始分布 组合 ？ 把电梯初始位置看作递增数组 a， b，b0=0

18、ai+bjFij表示连续块大小大于 1，j 座电梯覆盖 i 层的方案数；Gij表示连续块大小等于 1，j 座电梯覆盖 i 层的方案数；DD1个单位，方案数则是 a,b 数组的互补性质，要求连续块大小为 1a11b1必定等于 1 ，由此得出， Gij 实质就是 最终答案就是要求出 FHN + FHH/N。H和N都非常大，但实际需 有 N=50 个字符串，任意两个串 s1，s2Len(s1)2s2)2( 定义 Len(s)为字s 的长度)。问：从 1 串的最短路LCP长度LCP 长度的平方和就要最大。在此引入 LCPtrie 叶节点LCP长度平0 1 未必是相并不影响 LCP。那么可经过交换一些点0 1 是相邻的LCP给 非 负 整 数状态K,A,B,lower,upper 和正整数N(所有数f(X,Y表示 1*K%N,2*K%N答案表示为 f(B,upper) - f(B,lower-1) - sqrt(X)段，每段 sqrt(X)sqrt(X)求的是0,Ysqrt(X)*K%N 第二段里0,Y 内的数相对于第一段里之 后 同 理 。 时 间 复 杂 度 为状态在平面内，Alice 在 (Tx,Ty=800每一步她(badi,badi即边长为 好到达(Tx,Ty的方案数？（badi10 的倍先忽略 bad（原地不动可看作一种 bad ）限制，考虑横坐标，设 DP 数组 sum