国家集训队作业part

1、第一部分: TopCoder 题目泛做(截止日期：CTSC 前 10 天，具体待定)：提交方式: 通过OJ 提交，将开启提交窗口。说明本次作业主要为题目泛做。每位选手原则上应完成给定的 50 道题, 并填写每题题目大 意(无需背景，说明模型即可)、算法 /说明(并注明提交或测试情况)，最终提交表格以及带注释的程序。以下为一些具体说明:1. 所有题目来自于TopCoder : http:/tc2. 关于 TopCoder Arena 的使用可见:http:/wiki/dispetpetitions3. 以下表格给出 SRM 的序号, 可到ArenaPractise RoomsSRM 中寻找, 对

2、于每一次SRM 仅需做 Div I 的分数最高一题(Level Three, 一般为 1000 分)。4. TopCoder Arena 仅接受面象语言Java/C+/C#/VB. 因此使用Pascal 的同学可以考虑学习使用 C+, 或者也可以去 TopCoder 主页上测试数据进行离线测试。测试数据的方法为：打开 TopCoder 主页AlgorithmMatch Archive选择相应的比赛选择一个DIV I Leader(点ID 前面的黄色小圆点)进入到S ics 之后选择最下方相应的比赛题目即可。例子：http:/s?c=problem solution&rm=302281&rd=1

3、3903&pm=10551&cr=83555165. 要求的题目中有两次 SRM 还没比，大家可以考虑参加。泛做表格SR M题目名称题目大意算法状态450RowGameN 个点排成一排，每个点 值，初始在点 1，第奇数次可以向右走，第偶数次可以向左走，每次走的区间内所有点的权值都会被加入到总权值内，权值在任意时刻不能为负，求最大权值和。首先把每个点拆成向左和向右两个点，最终答案 的 形 态 一 定 是 1-i-j-i-j 的循 环。令 disti表示到 i 的最少步数，costi表示到满足 disti的前提下的最大权值和，做 dijkstra即可。Accepte d451BrickPuzzle

4、用 4 种俄罗斯方块覆盖 n * m 板子上状压 DP，状态很稀疏，用哈希存状态。Accepte d的某些点，求最少需要的俄罗斯方块个数。452IncreasingNumber求 digits 位，第 i位不大于第 i + 1位 （ 1 = i digits），且能整除 divisor 的数字数目模 P 的值。转化为 a * 1 + b * 11 + c* 111 + = -111(共digits个 )111% divisor，a + b + c + = 8 的方案数。由于 divisor很小， 所以可以 cnti表示 1, 11, 111,中模 divisor 为 i 的数字数量，然后用 f

5、ijk表示考虑cnt0 i且a + b + c + = j，a * 1 + b * 11 + c * 111 + 模 divisor 为 k 的方案数，递推。注意常数优化。Accepte d453TheSoccerDivOneN 个球队打比赛，赢一场得 3 分，平一场得 1 分，败不得分，告诉你每个球队目前的分数，每个球队还有 4 场比赛没有打，求在最优情况下球队 0的最终名次。fijk表示考虑前 i 支球队，win lose = j， draw = k（每个球队可以对draw 做出正贡献或负贡献）的情况下，分数比球队 0 高的球队数目最少是多少，转移时枚举 4 场球赛的 15 种可能情况。A

6、ccepte d454MegaSum自然数按顺序呈蛇形排列，S(x)表示x 所在的方块与 (1, 1) 之间所有数字 的 和 ， 求 sigma(S(y) | y 所在的方格处于(1, 1)与x 所在的方格组成的矩形之间)。首先确定出 x 所在的位置(r, c)，对于每个数字 t，若 t 所在的位置为 (p, q)，则 t 对 的贡献为 t * (p r + 1) * (q c + 1)，依次处理每层， 可以用公式在 O(1)的时间内计算出 sigma(s + i) * (p + i) | 0 = i n)这样的合式，总时间复杂度 sqrt(n)。Accepte d455ActivateTre

7、e给定 vector tree 和Tree，每次操作可以选择 vector中的一棵树 T 和中的一个节点 V，选择预处理出每对(T, V)对应 的 所 有 合 法 T 。 fmask中所有边的颜 况，枚举所有(T, V)转移。Accepte d中以 V 为根的子树 T，若 T 和 T同构，可以花一定的代价将 T中的边反色，问把的所有边变为黑色的最小代价，每对(T, V)只能被选择一次。456FunctionalEquationf(x)满足 f(2f(x)-x+1)=f(x)+ C,求sigma(|f(xi)-yi|)的最小值.对题目中的条件进行两次 迭 代 后 发 现 f(x+2nC)=y+2

8、nC, 继而 可 发 现 若 确 定 了 f(2i)=i+j, 则 可 确 定 f(2i+2nC)=i+j+2nC,f(2j+1+2nC)=i+j+(2n+1)C, 且每个 i 对应唯一的 j, 不同 i 之间不相关.所以可以建出二分图,求最小匹配.Accepte d457TheSquareDivOne一个m * m 的板子上放有一些C，要求你移动最少的步数，使得每一列的C 数于初始状态下每一行的C数（Ri）相同，求字典序最小解。每个格子建一个点，每一列建一个点，相邻格子之间连费用 1 容量正无穷的边，每个格子到相应的列连费用 0 容量1 的边，源点到每个C格子连费用 0 容量 1 的边，每一

9、列到汇连费用 0容量 Ri的边，求最小的最小费用最大流。为了求字典序最小的解，可以枚举每一条边，并试着让这条边满流，如果可行那么就将这条边强制设为满流，继续运行算法。Accepte d458ModuloFourDivisor用 O(1) 的时间判断是否存在整数N满足其模 4 余 0 的因子数为 c0, 模 4余 1 的因子数为c1, 模 4 余 2 的因子数为c2, 模 4 余 3 的因子树为 c3.分情况 , check(c0, c1, c2, c3)返回是否有满足 条 件 的 N, checkOdd(c1, c3)返回是否有满足条件的奇数 N,具体可参见代码Accepte d459TheC

10、ontest两支队伍分别有N和M 位选手, 要求每队选手之间进行且仅进行一次比赛, 比赛分为 max(M, N) 轮, 每轮 可 以 允 许 m , N)位选手同时比赛, 求字典序最小的方案.一行一行处理, 枚举矩阵的每个元素后判定可行性. 分两种情况, 建立二分图左边表示列,右边表示轮数: 若 N = M 则一定存在合法匹配,直接做, 否则优先满足出现次数多的轮数.Accepte d460TheCitiesAndRoadsDivOne题目给定了一些边, 请你添加额外的边使得形成最多只有一个环的连通图, 求方案数.fsubsetk 表示当前连通分量的情况为 subset,并且是否需要形成一个环

11、的状态为 k 的方案数, DP. Subset 是一个排序后的 vector, 其每个元素对应着 通分量内节点的个数.Accepte d461FencingGarden用木板拼接成一个靠墙的矩形栅栏, 最多可以切割一个木板(也可以不切割), 求面积最大的前提下, 平行于墙的边的长度最大值.注意到三边中至少有一边是完全由不切割的木板组成的, 由二次函数的知识此边的总长靠近对称轴, 面积越大. 所以把木板分成两份, 枚举每份中所有可能的选取情况并排序,对两个数组扫描一遍可得出最优值.Accepte d462WarTransporion一个图，其中某条边被删去了，但是不走到这条边的起始点就无法得知这

12、条边是否被删去。求 1 到 2 在情况下的最短路。枚举每一条边，求出对于每个点在已经发现被删除的边后， 情况下到点 2 的距离 worsti，然后在对点 2做一遍普通的 dijkstra，但 是 每 个 点 的 距 离 disti 必 须 不 小 于 worsti，返回 worst1即可。Accepte d463RabbitPuzzle给定三只兔子在数 轴 上 的 位 置 vector rabbits，每次可以选取一只兔子越过恰好一只兔子把兔子的位置的集合看做点，每个点可以把中间的兔子往左跳或把中间的兔子往右跳，或把距离中间距离较小的兔子往中间跳，这样就得Accepte d跳到另一个点，求 K

13、 步后，兔子位置在 vector nests 的方案数。到了一棵满二叉树（森林），用 fijk表示跳了 i 步，lca(当前点，初始点)的深度为 j，当前的点的深度为 k 的方案数，递推。Ac464ColorfulMaze迷宫里有AG中的字母，每个字母是陷阱的概率为 trapi，你最多能踩一次陷阱，问在最优策略下能到达终点的可能性。用 fijdangsafe表示当前在点(i, j)，已知安全的字母集合为 safe，已知 的字母集合为 dang，最大到达终点的可能性。由于只能踩一次陷阱，dang 中最多有一个元素，递推即可。注意状态间可能有环，而有环的状态时等价的，所以可以用并查集压缩起来一起处

14、理。Accepte d465BouncingDiceGameA 和 B 在 1 n 的格子上玩，轮流掷 D 面并走 D 步，如果走到 n 那么就折返回 来，谁先恰好走到 n 谁就获胜，求 A获胜的概率。先不考虑折返 ，这题可以用dp 在n2 时间内解决，即用 fij表示A 走i 步到达j 的概率，gij表示 B 走i 步到达 j 的概率，枚举 A是在第几轮获胜统计答案，转移时用部分和优化。考虑折返，在 n 步后，A 和 B 必定都在 n d + 1 n 之间，A 获胜的概率为 1 / d + (d 1)/ d) 2 * 1 / d为首项 1/ d，公比(d 1) / d) 2的等比数列， 可以

15、在 O(1)的时间内求解。Accepte d466DrawingBlackCrosses一个 m * n 的黑白板子，最多只有 8个元素被染成黑色，每次操作可以选取一个白色元素并把 同列的所有元素染成黑色，求把整个板子染黑的方案数。称包含黑色元素某一行/某一列为特殊行/列，其余 为 普 通 行 / 列， fijmskRmskC表示剩余 i 个普通行，j 个普通列，剩余的特殊行/列的集合为mskR/mskC 的方案数，转移时枚举选择普通行+普通列/普通行+特殊列/ 特殊行+普Accepte d通列/特殊行+特殊列，j这一维可以省略掉，因为状态必须满足 m - i - numbermskR = n

16、 j numbermskC。467NextHomogeneousStrings一个字符串被称之为 homogeneous当且仅当其任意长度不大于n 的子串中最多有d 个不相同的字母. 求字典序大于等于seed的 第 k 个 homogeneous 字符串.总思路为先枚举 与 seed 的 LCP, 确定下 LCP 后再逐位确定剩下的位. 问题就转化成了给定一个前缀, 求以这个 前 缀 开 头 的 homogeneous 字符串的数量. 用 fis表示考虑前 i 位, i n + 2i 的状态为 s 的方案数. 若某一位是该位字母最后一次出现的位置, 则 s 对应位为 1, 否则为 0.Acce

17、pte d468MallSecurity共 N 层的分层图，第 i 层的点只能向第 i + 1 层连边，第 N 层可以向第 1 层连边，求最大独立集。若 N 为偶数，直接二分图最大匹配，否则：由于10 = N 0 Aq1 -Bq1+ Aq2 sumB 0 Aq1 Bq1 +Aq2Bq2+ Aq3 sumB 0Accepte d安排是好的当且仅当两个人都把所有的 看完。求好的安排数。令 fijk表示处理完前 i 个 ，上式中左边的最大值为 j，且当前值为 k 的方案数，转移时枚举i + 1 场 放到谁的队列里。注意常数优化。470BuildingRoadsm * n 的方格，某些格子有石头，清除

18、掉需要一定的代价，求使 t 对点相通的最小代价（t= 4）。最终清出的路面一定是森林，用 fmskij表示连接 msk 中的点到(i, j)处的最小代价，最后再 DP 一次求森林中每棵树包含什么点即可。Accepte d471ConstructPolyline三 中n 个向量，你可以选择翻转向量或不翻转，求这n 条向量的和的模的最大值。随机 10 6 次最终向量的方于每条向量，若在最终向量上的投影为负则翻转，否则不翻转，更新取最大值。Accepte d472ColorfulTilesM * n 的格子染有 4 种颜色，可以对的格子进行至多K次改变颜色的操作，问使得最终任意两个有公共点的格子颜色

19、不相同的方案数。如果行或列数为 1，则特判掉，否则行或列中一定是 XYXYXYXY 这样循环交替的形式（画个图看看就知道了），行和列单独处理，再减去相交的部分即可。以行为例，用 fijkl表示处理完前 i 行，第 i 行 X = j，Y = k，已经改变过 l次的方案数。相交的部分只需要枚举左上角的 4 个格子就可以确定。Accepte d473RooksPartyM * n 的格子上放t种颜色的 rooks，每 种 颜 色 有 countst 个，若不同颜色的 rook 间不能相互 ，求方案数。预处理 fijk表示将 k个 rook 放到i * j 的格子上且每行每列至少有一个的方案数， g

20、ijk表示考虑前 i 种颜色的 rook， 下 j * j 的格子的方案数。在求解 fijk时，k 的可能取值只能是 counti，所以没必要计算所有的 k。Accepte d474GameWithGraphAndTree给定一幅图和一棵树，要求你对树fijmsk表示以 i 为根的子树中，根节点对应Accepte d中的每个点和图中的每个点进行一一 ，使得树中有的边图中也有，求方案数。图中的节点为 j，且该子树 到图中的点的集合为 msk 的方案数。475RabbitProgrammingN 个兔子 ，每个兔子的分数处于 lowi highi之间， 后取前 qualified 只兔子，其中选出

21、 selected只晋级比赛。问有多少种不同的晋级方案。枚举晋级的兔子中最低兔子 ，对于其他兔子，有三类：第一类必须 qualified 只兔子中，第二类有进入 qualified 的潜力，第三类 不 可 能 进 入 前 qualified。枚举第一类和第二类中晋级的兔子个数，组合数乘起来就是。Accepte d476SpahipEvacuation给定一个图, 其每个节点最多处于一个环中, 边有流量限制. 你的任务是增加某些边的流量, 使无论m 个人如何安排, 所有人总是能到达节点 0. 求最小增加的流量.题目中图的形态是: 一些环+桥. 桥边的容量一定要大于等于 m. 考虑换边, 令 A

22、表示向左的流量, B 表示向右的流量, 则 A 递减 B 递增,同 时 每 个 点 的 Ai+Bi=m. 所以可以用 fij表示考虑前 i 个点, 且当前A 值为j 的最优值, DP.Accepte d477KingdomTour从树根开始遍历树，每条边至少遍历一次，可以使用 K 次传送装置，问最小总花费。令 fij表示以 i 为根的子树中，有 j 个传送端点的最小花费，视 j 的奇偶性增加边权的 1 倍或 2倍，取 frootk * 2 + k * L 的最优值即可。Accepte d478RandomApple有n 个筐子和m 种苹果，首先随机选出一个筐子的非空子集，然后把这个子集中的所有

23、苹果放到一起，随机拿出一个，求拿出 m 种苹果的概率。对于每个筐子的每一种苹果，其最终拿出的概率仅与最终筐子里的苹果数有关。所以可以先用背包处理出包含相应苹果数量的方案数，然后枚举每个筐子的每个苹果，累积对最终做出的贡献。Accepte d479不明中480StringDecryption对由纯数字组成想破头也想不出来的Accepte的字符串进行加密就是把相同一段连续字符压缩成 字符数量+ 字符的形式，告诉你两次加密后的，求初始可能的字符串。DP 啊用 fijk表示处理完前 i 个字符，解密后最后一个字符为 j，且是否存在一次 后残留字符的状况为 k 的方案数，递推。要处理0的情况d481Ti

24、cketPrers有n 个 要打印 n 个数字，只要你一到达某个打印机，就可以在这个 上安装自动工作设备，以后的每一秒打印机里的数字可以+1 或-1，也可以自动打印出你需要的数字，求最小时间。二分 ，C(n, n /2)枚举方向，匈牙利判定是否合法。Accepte d482BalancingAct有一些砝码，某些知道重量，某些不知道重量，问是否能通过天平把所有砝码的重量都确定出来。把已知重量的砝码平分成两组，求出每组砝码任意组合能称出的重量。然后枚举未知重量的砝码的所有组合，确定比当前组合大的最小的能称出的重量和比当前组合小的最大的能称出的重量，然后每个砝码-4 +4 枚举误差，判断称量结果是

25、否与没有误差时相同，若相同则说明某些砝码无法被称出。Accepte d483Sheep河岸边有n 只羊要渡河，你有一只船，每次放入能放入船中的重量最大的一只羊，直到不能放为止，渡河到河对岸。求最小的船容积使得能在 m 次渡河操作内把所有羊都渡虽然题目不满足二分性质，但是可以先二分答案出一个上界，再向下枚举，判断是否可行。由于若容量 C 可行，则 C + max_weight 一定都可行，所以之需要向下枚举 2000 次。可以用线段树在 nlogn 时间内判定。Accepte d到河对岸。484Number1 N 的数字写在 X 张卡片上，每张卡片恰好写 M 个数字，求 X 的最小值。又是想破头

26、都想不出来的题题解很神奇，还是有很多地方不懂，就 当 是 抄 代 码 了 。 M (N, K)返回把1 N的数字写到 K 张卡片上，每张卡片上数字数量和的最小值（忽视恰好放 M 个的限制），可以证明若 M (N, K)= M * K，则一定存在可行解，所以二分 K。另外为了处理 M 的限制，可以令 M = m , N M) 而不改变最优解。Accepte d485Deit给定两个嵌套的凸包, 对于任意外围凸包上的点, 选择 凸包上最远的点走过去, 如果途中遇到了内凸包, 则此点称为 good. 求 选 择 到 good 点的概率.对于 凸包的每条边单独处理, 最后累加答案即可. 任意两个凸包顶

27、点的中垂线与当前边的交点称为重要点,则两个相邻的重要点之间对应的最远点是不变的. 取每一段重要区间和其对应的最远点, 做出凸包的投影在当前线段上的投影, 累加 .Accepte d486BatmanAndRobin把 N 个点分成两个部分，分别求凸包，问较大面积的最小值。枚举一条直线把点分成两部分，分别做凸包更新 。Accepte d487BunnySequence对x 进行一次 F(x)操作：如果 x 是 m的倍数，那么就把 x 除以 m，否则 x = x + 1，求第一次达到 1 进行 F(x)次数为 n 的数字数量。递推取 m = 3 的情况在纸上模拟下前几层就明白了Accepte d4

28、88TheBoringGameDivOne三个人打比赛, A和 B 一组, C 单独一组, 比赛分多轮, 每轮每人可以一个人,可以注意到每轮有 9 种类型, 用 9 个变量表示每种类型的轮数, 这其实就是 9 个变量与 6 个等式的方程求某个式子Accepte d当某个队伍全部后结束.射杀一个队友-1分, 射杀一个敌人+1 分, 告诉你最终三人的得分与次数, 求轮数的最大和最小值.的取值范围个人认为很难不重不漏的考虑所有限制, 看了 题解后依然不解.489AppleTrees在数轴上种 n 棵树，两棵树 i 和 j之间的距离至少为 max(hi, hj)，求方案数。先考虑紧的情况，即两棵树i

29、和j 之间的距离恰好为 max(hi, hj)，然后插空放入没有用到的区间就可以了。首先按 h排序，这样只需要考虑 较大的 h 值，用 fijk表示前 i 棵树，共占了 j 的数轴区间，分成了 k 份的方案数，递推。Accepte d490Infiniab一个无限长宽度为 C 的迷宫里，由 R * C 的pattern 拼接而成，求一个点到另一个点的最短路。向上扩展 X 个 pattern，向下扩展 X 个 pattern，求出(0, j)到(R, k)的最短路，然后矩阵乘法。Accepte d491FoxCardGame两堆石子 A 和 B，每次可以从 A 中取出一个石子 a，从B 中取出一

30、个石子 b，甲的分数增加 max(a * b, a + b)，乙的分数增加 min(a * b, a + b)，求操作 K 次后甲/乙的最大值。二分，费用流判定，用 spfa 会超时，需要用 johnson 做。Accepte d492TimeTravellingGogo求 0 N 1 的最短路。只有晴天时可以出门，可以使用时光机器到之前的某一个时刻。把关键时间点提出来，对于每个点 i，其对应的关键点有 sunnyStarti、 sunnyEndi、 sunnyStarti + v 、 sunnyEndi v，其中v是 i 连出的边的权值，然后建图后 dijkstra。Accepte d493

31、AmoebaDivOne在 m * n 有的fijks0s1 表 示 考Accepte格板上放一个凸包，求方案数。虑前 i 行，当前左右边界是 j 和 k，s0 和 s1 分别表示左边界和右边界的递增状况，朴素是 n 5的，可以用部分和优化到 n 3。d494KnightsOut在 n * m 的棋盘上放马，每放一个马其能 到的格子会变色，问使最终棋盘全黑的方案数。最朴素的想法是把每个点当做一个变量，消元，但这样太 是 (m * n) 3。 发现如果前两行和第一列都确定了，那么其他格子的情况也就都确定了，所以变量可以缩减到 O(n)级别。Accepte d495StrangeElevatorN 层楼房，有一个 M 个块组成的联动电梯，如果这个电梯能够不重不漏地在所有楼层停，就称这个电梯是好的，求好的电梯的方案数。奇怪的递推还是没大想明白，用 F(N, M)和 G(N, M)分别表示最低的块与次低的块相邻、和最低的块与次低的块不相邻的方案数，然后相互递推。Accepte d496YetAnotherHamiltonianPathn 个点，每个点 i赋予一个字符串标识 labeli，u 和 v 之间的权值定义为 length(labeli)2 +length(labelj) 2-length(LCP(labeli, labelj)2，求