集训队作业泛做表格藩

IOI2011中国国家集训队第二次作业第一部分:TopCoder题目泛做湖南雅礼中学何朴藩教练：胡伟栋唐文斌[前言]TopCoderAlgorithm与OI和ACM的竞赛方式区别很大。在这个平台上只允许程序员使用面向对象的语言JavaC++C#VB.net，而且必须按照面向对象的方式解决问题。与NOI传统的比赛题区别明显，语言限制少，允许使用高级语言的各种强大的功能。题目的数据范围一般都不大，时间限制为每个测试点2s，内存限制64MB。SRM（SingleRoundMatch）是比赛的一种。TopCoderAlgo每次比赛有3道题（Level1-3），分值不同（一般为2005001000根据难度有小调整）。题目采用一次性测试，错了得0分，对了按解题的时间得分。可以说TopCoder在考察的方向上是侧重编写代码的能力。我会尽量向读者介绍最优化以及最易实现的算法。表格的内容为SRM450-499的51道DivILevel3的题目(包括453.5)。表格对每道题的题意进行了简明描述，对解法做了讨论。希望这个表格对读者能有一点点帮助。*附带编者的C++参考程序。如果不理解表格里的题解，可以阅读带注释的参考程序。[泛做表格]表格共包括99道有效试题。难度用★表示，星数越多表示题目难度相对越大。难度完全是编者主观意见，难免与读者意见有些不同，请读者多多包涵。SRM近来的题目质量都很不错，基本都是推荐做的。标记AC(51/51)表示作者在练习房间中提交并通过所有SystemTest。编者handle：hpfdf难度导读：LevelCountRatio★35.9%★★2039.2%★★★1223.5%★★★★1223.5%★★★★★47.8%SRM内容450AC★★★[题意]RowGame有N个数的数列，初始时人在最左边的元素上。人需要移动不超过K次，第奇数次移动必须向右走，第偶数次必须向左走。(可以走距离0)。一次移动经过的数字将会被全部累计入人的得分。初始时得分是0.每次移动完成后不允许出现总分<0的情况。求移动完K次以后人可以得到的最大分数。[范围]1≤N≤50|数字|≤400,000,0001≤K≤400,000,000[分析]动态规划，贪心通过研究我们发现，如果没有“不允许分数<0”的限制，人第一次一定会移动到一个点，然后在这个点为结尾的最大子段和中来回运动一直跳满K次。我们枚举这个点就可以求最大值了。加入了限制以后，人的最优策略会产生变化：为了到达目标段，我们可能要在之前的某些段中积累分数，然后移动过来在达到目标段之前，人只会积累分数，一旦积累足够了就会移动人总是会选择一个较大的子段进行积累。我们可以算出以每个数为结尾的最大子段和是多少。然后进行动态规划：e[i]表示最早移动到i的时间。f[i]表示最早移动到i时可以积累的最大分数。注意不会出现延迟一点时间可以增大分数的情况，因为人只可能从较低分的段移动到较高分，一旦积累足够就会跳过来。转移时e是第一关键字，f是第二关键字。[复杂度]时间O(N2)空间O(N)451AC★★[题意]BrickPuzzle用这4种积木任意多，覆盖一个给定的地图。地图中有些格子必须被覆盖，其他的也可以覆盖。不允许翻转旋转，不允许出界和重叠。问是否有解。如果没有输出-1。如果有解，输出最少使用的积木块数。[范围]地图大小1≤N,M≤22[分析]状态压缩动态规划四种拼图都在2行之内，由此我们可以按行来做状态压缩动态规划。经证实此题对时间常数要求极为残酷。需要按单格来转移。F[i][j][mask]表示到(i,j)之前的已经全部填好，对紧接的M+2个格子造成的影响是mask(状态压缩)，此时的最少块数。优化：滚动数组hash状态(由于不会出现单独1个格子被覆盖，左右都没覆盖的情况，所以实际上合法状态总数不超过Fibonacci数列的第M+2项，约10万)[复杂度]时间O(φMNM)φ≈1.618空间O(φMN+2M)452AC★★★[题意]IncreasingNumber求满足一下要求的长度为N的数字序列的总数：十进制里是M的倍数，序列不下降。[范围]1≤N≤10181≤M≤500[分析]动态规划，组合数学我们可以把这样的上升数，看做不多于9个的”全1数”的和。例如，1335=1111+111+111+1+1其中全1数的位数≤N这样一来问题变成了在前N个全1数中选出不超过9个，使得和是M的倍数。注意到M不大。我们可以用动态规划来解决：预处理D[i]表示模M为i的全1数有多少个。F[i][j][k]表示我们已经取了k个模M小于i的全1数，目前的和模M为j的总方案数。F[i+1][(j+x*i)%M][k+x]+=f[i][j][k]*重组和(D[i],x)重组和(a,b)=C(a+b-1,b)细节上，可以利用余数的循环节求D[i]，利用阶乘式求C(i,j)[复杂度]时间O(M2K2)//K=10空间O(M2K)453AC★★[题意]TheSoccerDivOne某足球大赛有N支队伍。现在每支球队都还剩恰好4场比赛没比完、你知道目前所有队伍的积分。每场胜+3分，平+1分，负不加分。求第0号队伍的最好排名。[范围]2≤N≤500≤Score[i]≤106[分析]动态规划首先可以确定的是，0号队伍的4场比赛是全胜的。如果不是这样，答案不可能变得更优。Score[0]一旦确定，我们的任务就是要分配比赛使得分数大于Score[0]的球队尽量少。接下来我们先不看平局。如果全体球队的(胜场-负场)之和为0，那么就一定可以把他们间的比赛匹配好。我们只需要考虑胜场-负场的个数就可以了。加入平局以后，每个球队的4场比赛会有15种情况。我们需要考虑对未分配对手的胜负和平局进行匹配。F[i][j][k]表示1到i的队伍，已经确定的(胜-负)总和=j，还有k个未匹配的平局，比a[0]分高的最少个数。这里j的范围是-4N到4N，k的范围是0到4[复杂度]时间O(N2)//状态为N2,最多有15*4种转移，为常数)空间O(N)//滚动数组453.5AC★★[题意]TheAlmostLuckyNumbers十进制里只包含4和7的数字叫做幸运数字求A到B中有多少个幸运数的倍数。[范围]1≤A≤B≤1010[分析]枚举，搜索，容斥原理1010以内的幸运数字共有2000个左右。一个做法是我们求出，对于任意集合的幸运数字的最小公倍数，求出在A到B中有多少个倍数。然后用容斥原理得到不重复的答案。优化1：使用dfs，一旦中途最小公倍数大于数字范围，剪枝。优化2：从大到小决定幸运数字的取放，这样可以尽快筛去过大的状态。优化3(可选)：删除幸运数里面是其它幸运数倍数的项。注意中途直接乘法求最小公倍数可能会超过longlong/int64，需要移项比较。[复杂度]时间O(2logB)空间O(2logB)454AC★★[题意]MegaSum如上图，定义S[i]为以i数字为右下角的子矩形的数字和。现在输入N，输出所有在N为右下角子矩形内的S[i]的和。答案对1,000,000,007取余数。[范围]1≤N≤1010[分析]数学，数值可以根据规律求出N的位置，可以证明位置坐标的范围是O(sqrt(N))的。假设N在x,y。接下来我们讨论每个数字被算的次数。一个在xi,yi数字被算了(x-xi+1)*(y-yi+1)次。我们可以把整个矩阵拆成若干个横竖条来计算，每个条内的数字是等差数列，被计算次数也是等差数列。可以用数学方法来求两个等差数列对应项相乘的和。提示：Sum(i2,[1,n])=n(n+1)(2n+1)/6注意及时取模防止超过数字范围。[复杂度]时间O(sqrt(N))空间O(1)455AC★★★[题意]ActivateTree给一棵N个节点的有根树，再给不超过M棵有根树，每棵树节点数不超过5个。每次可以用一棵树去覆盖大树中一棵同构的子树（边的方向也必须相同），要求大树的每个点作为根节点不能被同一棵小树覆盖多次。用第i棵树去覆盖每次需要花费整数costs[i]权值，求最小费用的方案，使每条边被奇数次覆盖。[范围]1≤N≤161≤M≤50≤costs≤65536[分析]状态压缩动态规划范围不大。我们可以设F[i][j][mask]表示用前i棵小树，第i棵已经处理完大树中0到j的节点(为根)。大树上所有边的覆盖情况为mask(记录奇偶性)。此时的最小费用。可以使用搜索来得到i小树在大树的j节点的所有同构覆盖方案。建议使用拓扑排序处理输入数据，这样搜索会很简单。注意大树的根节点没有父亲边，也就是说mask的范围是[0,2N-1)[复杂度]时间O(N6M2N)空间O(N+M+2N)456AC★★★★★[题意]FunctionalEquation如上图，f函数是一个定义在全体整数上的离散整数函数。请在所有满足以上要求的函数中找到一个，使如下和式最小：其中x[0..N-1]和y[0..N-1]都是通过输入的随机种子生成的109以内的整数输出最小值。[范围]1≤C≤161≤N≤10000[分析]数学，二分图，状态压缩动态规划设g(x)=2f(x)-x+1,则f(g(x))=f(x)+C，进一步化简得g(g(x))=x+2C由于g(x+2C)=g(g(g(x)))=g(x)+2C可以推出f(x+2kC)=f(x)+2kC我们只需要求出f(0..2C-1)的返回值，就可以求出f在所有整数上的值，也就是说，f函数返回值对2C的余数是一个周期为2C的函数。由于g(g(x))=x(mod2C)，所以g在2C的剩余系中是一个自反函数。每一个g(x)必然和一个x唯一匹配.问题转化成二分图。我们发现x和g(x)的奇偶性一定相反。(根据定义)所以我们把0到2C-1的偶数作为左图，奇数作为右图，根据求出的限制条件建边，求一个最小费用完备匹配即可。注意可以以2C为单位调整模2C相同的点的全体匹配对象。建边时需要用到一个类似求中位数的方法，来达到绝对值差的和最小。最后可以用经典的KM算法。但由于图中最多只有16个点，状态压缩动规也可以通过。[复杂度]时间O(CNlogN+C3)空间O(NC)457AC★★★★[题意]TheSquareDivOne输入N*N的01矩阵。可以交换2个相邻元素。记R[i]表示第i行有多少个1.现在要尽量少的交换使得把矩阵变成第i列有R[i]个1.输出字典序最小的解。[范围]1≤N≤18[分析]最小费用最大流棋盘移动问题是经典的费用流模型。建立棋盘图A[i][j]，对于每一列建立虚拟点col[i].A[i][j]-->A[i’][j’]容量为∞，费用为1(i,j)与(i’,j’)相邻A[i][j]-->col[j]容量为1，费用为0源点-->所有初始是1的A[i][j]容量为1，费用为0col[j]-->汇点容量为R[j],费用为0这样求最小费用最大流，可以求出最少移动次数的情况下满足要求。然而如何保证字典序最优呢我们可以把A[i][j]-->col[j]的边加上一个修正费用设A[i][j]在字典序里面重要性排在第k位。12345678910111213141516A[i][j]-->col[j]容量为1，费用为2k这样就可以求得最小字典序的方案。直接使用实数精度会不够，建议使用压缩的2进制高精度。另外也可以使用枚举删边并多次尝试求费用流的方法来做这道题。[复杂度]时间O(N8)空间O(N4)点数V=O(N2)边数E=O(N2)高精度C=O(N2)单位增广网络增广次数K=O(E)=O(N2)SPFA增广算法O(VEKC)=O(N8)由于spfa算法时间上界宽松，再加上按位压缩优化，该算法可以通过此题。458AC★★★[题意]ModuloFourDivisor如果：存在正整数N，使得N1.正好a个约数模4为0，2.正好b个约数模4为1，3.正好c个约数模4为2，4.正好d个约数模4为3.那么(a,b,c,d)是一个可行的四元组。给4个自然数集合A,B,C,D。求有多少个(a∈A,b∈B,c∈C,d∈D)是可行四元组。[范围]1≤集合大小≤500≤数字≤1018[分析]枚举，数学首先想到枚举数字组合再判断。这样我们只需要一个O(1)的判断方法就能通过本题，即是否存在正整数满足：1.正好a个约数模4为0，2.正好b个约数模4为1，3.正好c个约数模4为2，4.正好d个约数模4为3.我们可以把N的质因子分成3类：第1类是模4为1的第2类只有2第3类是模4为3的那么，最后决定N对应(a,b,c,d)，实际上只跟N的每类因数内部的组合总数有关。也就是说，如果(a,b,c,d)可行，我们一定可以找到一个形为5x·2y·3z的N。这里x,y,z都是自然数。N的约数共有(x+1)(y+1)(z+1)=a+b+c+d个b≥1b和d的大小不受y的影响。经过简单推导我们发现：b+d=(x+1)(z+1)d=(x+1)((z+1)/2)那么如果z是偶数，则有(z+1)/2*2<z+1也就是说b>d，可以直接算出x+1=b–d。注意b和d都必须是x+1的倍数z是奇数时b=d.再看a和c的大小如果y=0那么a=c=0如果y>0那么c=b+d,a=(b+d)*(y–1)对于以上所有情况进行判断即可。总结：b≠0(b=d)OR(b>d)AND(b-d|b)AND(b-d|d)//X|Y：X整除Y(a=c=0)OR(c=b+d)AND(c|a)[复杂度]时间O(N4)空间O(N)459AC★★★★[题意]TheContest在NxM的矩阵中填入尽量少种不同数字，要求每种数字出现次数相同，使得每行每列不存在重复的数。输出字典序最小的解。[范围]1≤N,M≤50[分析]枚举，二分图匹配首先可以确定：一定有Max(N,M)种不同数字，每个数字被选了Min(N,M)次。我们可以采用按字典序枚举+判断是否可行的思路来处理这道题。对于当前行，把要填的数字看成左图中的点，矩阵中的元素看做右图的点。我们只需要按已知条件建立二分图，然后判断是否存在完备匹配即可。注意每个数字必须出现Min(N,M)次。如果还剩p行未确定时，发现某个数字还需要填入p次，那么必须优先匹配这个数字对应的左图中的点。可以证明只要数字出现次数不存在矛盾，那么当前的匹配不会影响到之后的行是否有解。二分图完备匹配可以使用匈牙利算法。[复杂度]时间O(N6)空间O(N2)460AC★★★★★[题意]TheCitiesAndRoadsDivOne一个N个点的无向图，初始时有一些边。保证无重边和自环。现在要添加若干边，使得任意两个点之间都只有1或者2条简单路径。求加边的方案总数。对1234567891取余。[范围]1≤N≤20[分析]状态压缩动态规划任意两个点之间都只有1或者2条简单路径。也就是说图在加边以后必须是一棵树，或者一棵树+1条边的形式。首先对原图进行收缩连通分量，不妨设有M个连通分量。记下每个连通分量的电容量A[i]表示i分量内有多少点。如果原图中已经有1个环，那么我们的问题变成了M个点的生成树个数。如果原图中已经有多个环，那么答案为0。生成树计数有一个经典的状态压缩动态规划方法：F[mask]表示把集合mask的点做生成树有多少种方案。转移时，我们不妨取mask中编号最小的点s1为这棵树的根。如果mask只有1个点，直接F[mask]=1。否则再取次小的点s2.s2一定在树中是s1的某棵子树的根。枚举mask2为s2为根的子树的点集。易得mask2必然包含s2但不包含s1。对于每一个mask2,都有如下选择：F[mask–mask2]*F[mask2]*把s2接在mask–mask2的任意一个节点上方案数。这样累加答案是不会重复的。这个题需要处理环。那么加一维状态。G[mask]表示把mask集合做成一棵树+一个环的方案数。转移时同样求s1,s2,枚举mask2注意只有一个点时G[mask]=(A[s1]-1)*(A[s1]-1)否则有三种情况：mask2内部有环mask-mask2内部有环从s2连2条不相同的边到mask-mask2，使得形成一个新环并连通这样的复杂度是Σ(C[N][i]*2i)=3N优化：设计状态时，我们可以不用单纯的2进制：对于A值相同的连通分量，我们可以只记这类分量在mask中的个数，而不用分别01标记。这样，总共最多只会有5个不同的A值。状态会很可观地减少。[复杂度]时间O(3N)空间O(2N)461AC★★[题意]FencingGarden你需要靠着一个无限长的直线墙壁修一个矩形围栏。有N段可用的篱笆，已知它们的长度。篱笆可以连起来用。你有一把锯子可以把一段篱笆从任意长处据成2段，但是只能锯一次。要求围成的面积最大，面积最大的情况下，平行于墙的那条边要最长。返回平行于墙的那条边的长度。[范围]1≤N≤401≤长度≤108都是整数[分析]折半，枚举做成题目要求的形状，需要拼成3条线段，其中两条必须长度相等。设篱笆总长度为m不妨设平行于墙的那条长度是x显然两条短的必须是(m-x)/2面积是x(m-x)/2如果锯子可以据2次，那么可以直接求f(x)=x(m-x)/2在R+上的最大函数值。根据二次函数的知识，我们知道x=m/2时函数有最大值。因为我们只需要把所有篱笆搁在一条直线上，然后在m/4和3m/4处切开就可以了。只能据一次，说明x和(m-x)/2中至少有一个是必须从原始线段中组合得到的，也就是天然不用锯的。当然，我们希望天然的x和m/2尽量靠近。(二次函数满足凸单调性)或者天然的(m-x)/2和m/4尽量靠近。我们可以把原来的篱笆数组分成2组，分别求出所有的组合长度。(分成尽量平均的两组，最大2^20*2种组合需要考虑)对每组的长度做排序。这样我们可以枚举第一组的组合长度，然后动态在第二组的组合中找到对应的长度，使得两个长度相加离给定的常数最近。由于2^20完全可以承受，这样就可以统计答案了。[复杂度]时间O(2N/2N)空间O(2N/2)462AC★★[题意]WarTransportationN个点的正权有向图。人需要从1号点走到2号点。图中有一条边被删除了，但是人必须走到这条边的起点才知道这条边是否存在。求一个最坏情况下最好的走法使得路径最短。输出最坏情况的最短路。如果删除一条边可以使起点无法到终点，输出-1[范围]2≤N≤100表示边的字符串长度≤2500[分析]最短路，动态规划考虑动态规划：F[i]表示到i之前还没遇到被删掉的边，现在到了i，往终点走的最坏情况最小距离是多少。F[i]=max(max(i被删了一条出边后到终点的最短路best2[i]),max(F[j]+cost[edge])//edge表示i-->j的边)best2可以预处理出来，枚举边再在逆图上算从终点出法的单源最短路。注意F的转移不满足拓扑序，需要用Bellman-Ford或SPFA进行转移。这类动态规划叫做迭代型动态规划。[复杂度]时间O(NM2)空间O(M)463AC★★★★[题意]RabbitPuzzle3只兔子在数轴上的3个不同整点。一个兔子可以绕过另一个兔子跳等长距离，但是不允许跳过多个兔子或跳到有兔子的点上。给出3只兔子的位置A[0..2]，和目标位置B[0..2]。求从A到B恰好K次跳动有多少种不同方案。输出答案对1,000,000,007取模。[范围]|坐标|≤10180≤K≤100[分析]二叉树，动态规划每个状态要么有3个出边(中间向左右，或外侧的一个向内)，要么有2个出边(中间向左右，外侧2个到中间距离相等跳不动)容易想到二叉树的模型。实际上所有的状态组成了无限大的满二叉森林。问题转换成从点p到q走恰好k条边的方案总数。设F[i][x][y]表示走了i步，目前在树中深度是x，和目标节点的最近公共祖先的深度为y，有多少种方案。最后求F[k][H(q)][H(q)]即可[复杂度]时间O(K3)空间O(K2)//滚动数组464AC★★★★[题意]ColorfulMaze在一个NxM棋盘地图上，有唯一的起点和终点。有些格子是障碍，不得进入。人可以在有相邻的非障碍格子间移动。现在有些非障碍格子被标上了颜色A..G(7种)同一种颜色的格子要么都是陷阱，要么都是正常陆地。已知每种颜色格子是陷阱的概率。人必须走入相应的颜色才知道这个格子是否是陷阱。现在规定人有2条命，不能掉进陷阱两次。（可以走过一个陷阱格子）问人使用最优策略时，在最坏情况下到达终点的概率是多少。[范围]1≤N,M≤50概率都是百分数0..100的整数形式给出要求精确到10-9[分析]动态规划假设一个人在地图中走，他一定会记录下：现在的位置，现在已经碰见过的安全的颜色有哪些，还有已经碰到过的陷阱颜色有哪个。注意人不可能同时知道2个陷阱颜色。那么自然的设计状态：F[x][y][mask][k]表示表示目前到了x,y已经有mask集合的颜色确认安全，k为不安全的颜色。此时到终点的最大概率。推荐使用记忆化搜索进行转移。注意这题可能出现状态之间互相依赖的关系，也就是说走一个环但是没有遇到任何新的颜色。这需要进行特殊处理。我们知道这样走出一个环是没有意义的，最终返回值一定相等。我们可以把等价的状态缩在一起然后记忆化搜索。具体实现时，可以动态生成等价状态集合。每一个新集合的第一个被访问的状态为代表，进行最小值记录。另外终点所在的状态集合返回值强行改为1即可。[复杂度]时间O(2CCN2)//C=7表示颜色数空间O(2CCN2)465AC★★[题意]BouncingDiceGame直线上有从左到右编号为1..N的空位。初始时甲的棋子在x号，乙的棋子在y号。有一个骰子，上面有1..D的数字。使用一次骰子就会返回一个1..D的随机数。现在甲乙交替进行投骰子移动棋子。玩家投到了k，那么只能往右移动k格。如果正好到达N，那么该玩家获胜。如果移过了N，棋子就会弹回来往左移动。已知N,x,y,D求甲先获胜的概率。[范围]2≤N≤50001≤x,y,D≤N-1[分析]数学，动态规划初步想法：F[i][j]和G[i][j]表示甲/乙在第i次移动后到达j格子的概率这样由于转移时是计算连续的一段的和，可以用部分和优化。实现均摊O(1)转移。但是我们注意到棋子可能弹回很多次，也就是说，这个游戏可能双方移动很多次都不会出胜负。这样F[i][j]中i的取值会很大。幸运的是，我们发现棋子一旦跳进N-1到N-D的格子，情况就一样了：棋子只可能在这些格子里移动，而且每一步都是1/D的概率到达终点。因为每次至少要跳动一步，所以在N次以内棋子必然跳入这后D个格子之中。于是我们只要把F[i][j]中的i做到N，接下来的胜率可以通过数学方法直接计算，或者多次迭代计算近似值。[复杂度]时间O(N2)空间O(N)//滚动数组466AC★★★[题意]DrawingBlackCrosses一个NxM的01矩阵，每次可以选择一个0，然后把同行同列的所有数变成1。问有多少种不同的操作顺序可以把矩阵变成全1。输出答案对1,000,000,007取余数。[范围]1≤N,M≤20特殊：初始时最多只有8个元素是‘1’[分析]状态压缩动态规划由于每行最多只能选1个，所以选的次数不超过20.我们可以求出选k个格子的方案总数，然后乘以k!再取模。这样一来此题变成了经典的状态压缩动态规划。F[i][j][k]表示前i行中，没有剩余0的列的集合为j，被选过的列的集合为k，有多少种方案数。转移有M+1种：该行不选，或者选一个未被放过且不为”1”的格子。这样复杂度还是有些大，注意到最多只有8列有1，我们可以把全0列放在一起考虑。这样一来可以大大减少状态个数。注意及时取模。[复杂度]时间O(N217M)空间O(217M)//滚动数组467AC★★★★[题意]NextHomogeneousStrings一个合法串的定义是：元素都是小写字母所有长度为N的子串中，都不包含超过D个不同的字母。给出一个小写字母串S，求字典序大于等于S的，长度和S相同的所有合法串中，第K+1个是多少。[范围]1≤D≤N≤91≤|S|≤500≤K≤1018[分析]状态压缩动态规划这题的想法是这样的：用动态规划把求第K小答案的问题转换成求S为前缀有多少个答案的问题。这样，我们从后往前枚举原串的后缀，并把后缀改成一个≥原串的合法字符串。我们可以用F[i][S]来表示长度为i，之前N-1位字符的情况为S，有多少种方案。为了确保后缀比原来的串后缀要大，我们需要枚举后缀的第一位。这样一来，DP时不需要知道详细的字符情况，只需要记录之前N-1位的字符相同情况即可。我们可以用最小表示法：ayax写成0102（arab,owoz都是0102）这样可以大大减少状态总量。接下来处理好dp输出答案即可。需要注意的问题：原串可能本身是合法的，枚举最后的后缀修改字符时应该考虑改成相等。N=1时最小表示法只有一个状态:空数列。特别注意不能访问出界DP时中途值可能会超过1018甚至超过64位整型，这时应使用实数运算判断，如果很大那么换成一个较大的数即可。（因为K≤1018）[复杂度]时间O(N2*State*|Σ|)|Σ|=26空间O(N*State)468AC★★★★[题意]MallSecurity大楼有1到N层，每层有若干个电梯站。只有相邻2层的电梯站间会有直达电梯。第1层和第N层之间也有直达电梯。现在要安置尽量多的保安到所有电梯站上。满足同一条电梯道的两端最多只能有1个保安。问最多可以放多少保安。[范围]10≤N≤50总共最多有100个电梯站边数限制400左右[分析]最大独立集，二分图匹配这一题实际上是求一个N层的这样的图的最大独立集。如果层数为偶数，那么我们可以直接把奇数层都归为左图，偶数层归右图。问题就转换成二分图的最大独立集了，可以用(总点数-最大匹配)来求。同样的道理，如果层数为奇数，我们可以枚举其中电梯站数最少的一层的取舍方案，再把剩下的图化成二分图来处理。最坏情况下，11层共100点，点最少的层至多也只有9个点。29M3可以通过测试数据。[复杂度]时间O(2CM3)//M为总点数空间O(M2)469AC★★★★[题意]TheMoviesLevelThreeDivOne甲乙两个人决定看N部电影编号0到N-1。他们用这样一个方法看：两个人分别有一个等待队列(先进先出)，最开始他们按照电影的编号顺序把N部电影选择放进2个队列（2N种方案）然后每当一个人看完一部对方没有看过的，就会把看完的电影加到对方的队列中，并立即开始队列中下一部电影。告诉你A[0..N-1]和B[0..N-1]分别表示甲和乙看每个电影需要的时间。问有多少种安排方法使得双方不需要任何等待就能分别看完所有电影。[范围]1≤N≤47,0≤A[i],B[i]≤20[分析]动态规划本题很难直接统计合法方案，我们转换思路为所有方案2N减去所有不合法的方案。一个不合法的方案一定只会有一个人等待，等待的人不同，方案就一定不同。我们可以分开来算。假设现在算甲让乙等待的方案总数只看一开始被分配到甲的电影：甲[1][2]XXX乙XXXXXX[1][2]乙需要先完成一开始分配到自己队列的电影才会开始看甲队列中过来的电影。F[i][j][k]表示分配完编号前i个电影时，乙最少还要给自己分配j时间电影才能保证不等待，甲已安排的时间(图中甲行的1+2)-乙安排的时间(图中乙行的X+1+2)的值为k转移有2个：第i个电影可以开始分配给甲，（两行都加一个段,更新状态）那么j要取max(j,k+A[i]),k要变成k+A[i]-B[i]第i个电影可以开始分配给乙（乙行开始的XX变长），那么j要取max(0,j-B[i])，k要变成k-B[i]注意负数状态的存储。当把所有电影分配完时统计j不为0的总数，答案减去之即可。[复杂度]时间O(N3K2)K=20空间O(N2K2)//滚动数组470AC★★★★[题意]BuildingRoads一个NxM的网格地图上有各种岩石，有至多4对城市。摧毁不同的岩石需要的费用已知。现在要摧毁尽量少的岩石，使得4对城市每一对都连通。连通的同一字母表示一块大岩石：费用如下”a”..”z”:1..26”A”..”Z”:100..2600”1”..”9”:10000..90000”0”:100000[范围]1≤N,M≤50每种岩石只有1块。[分析]状态压缩动态规划首先可以根据相邻的相同路地块来建点，相邻的块来建边。最多有8个城市,DPF[i][mask]表示把mask集合的城市连通到i节点所需要的最少花费。这样可以求出把一个特定的城市集合连通到一起需要的最少花费。注意到城市可能不会完全连通到一起，我们需要用第二次DP，求出匹配城市互相连通的最少花费。虽然N2为2500，但由于岩石种类有限，最坏情况下，收缩后的图只有900个点左右，转移需要枚举28的子集，实际上没有达到216。[复杂度]时间O(216N2)空间O(28N2)471AC★★[题意]ConstructPolyline给N个三维非零向量，可以选择把一部分向量反向，使得向量和的模最大。[范围]1≤N≤50|坐标|≤10000[分析]枚举+贪心/随机化本题的二维版本存在一个O(NlogN)的解法：如果答案向量已经确定，那么和答案同侧（点积>0）的向量必然都不取反，异侧的必然都取反。也就是说最优方案一定是一个半平面内的向量不取反，其余的取反。这样我们可以把平面向量按极坐标排序，然后动态维护半平面内向量的和，就能保证求出最大的答案。推广到三维以后，基本假设仍然成立：最优方案一定是一个半球内的向量不取反，其余的取反。这个半球要么只有1个向量，要么可以通过调整使得至少有2个向量在边界上且不改变答案。我们可以枚举这两个边界上的向量，然后用三维叉积求出法向量（即垂直于两个边界向量的新向量。）接着计算半球内外的向量和注意这时边界上的取舍问题，我们可以把问题化简成上面说道的平面问题来做，这样可以保证答案准确。不过由于向量个数较少，随机调整也是一个不错的选择。事实证明后者实现简单，而且可以通过所有系统测试。[复杂度]时间O(N3logN)//这里使用非随机的方法，瓶颈是排序空间O(N)472AC★★★[题意]ColorfulTilesNxM的网格，每个格子可能是G/B/R/Y这4种颜色之一。现在要求改变0到K个格子的颜色，使得没有两个相邻格子同色(对角或公共边相邻)。求有多少种不同的改色方案。求答案对1,000,000,007取余数[范围]1≤N,M≤50K≤N*M[分析]动态规划一个点会有八格相邻，这个限制十分严格。经过实践发现，如果N>1,M>1，那么只会有3种情况：矩阵变成N/2xM/2个颜色情况完全相同的2x2小矩阵，有4!种。奇数行是2种颜色相间出现，偶数行是另2种颜色相间。奇数列是2种颜色相间出现，偶数列是另2种颜色相间。如果N和M有一个为1需要另用DP处理否则枚举第一个2x2的方案，接着分3种情况讨论并DP。注意Case2和Case3都重复算了Case1[复杂度]时间O(4!N3)空间O(N2)473AC★★[题意]RooksParty一个NxM的棋盘上放入K种颜色的车A[0..K-1]个。不同颜色的车不能在同行或同列。问有多少种不同填法。对1,000,000,009取余数[范围]1≤N,M≤301≤K≤10[分析]组合数学，动态规划我们知道一个合法的方案把行列进行重新排列仍然是合法的，那么我们知道：G[i][x][y]表示前i种颜色的车填完以后总共占了x行和y列，再填下一种颜色转移就是填当前颜色的车p行q列接着转移到G[i+1][x+p][y+q]*C[x+p][p]*C[y+q][q].最后空余的行列也可以重新组合。所以我们预先求出F[i][x][y]表示i个车，填x*y的矩阵并没有任何空行列的方案数。每次填一行：F[i+c][x+1][y+d]第x+1行总共填c个，其中有d个是另起的列。由插空的经典方法，我们知道这样共有F[i][x][y]*C[y][c-d]*C[y+d][d]种方法。预处理组合数，注意优化取余运算，就可以通过该题了。[复杂度]时间O(N6)空间O(N4)474AC★[题意]GameWithGraphAndTree一个N个点的无向图，一棵N个点的树。求树和图有多少种点的匹配方法，使得当树中两点有边时，图中匹配对应的点也有边。[范围]1≤N≤14[分析]状态压缩动态规划，树型动态规划F[i][j][mask]表示树中i为根的子树，i对应原图中的j点，mask为原图已经被匹配的点集，这种情况的方案数。常数优化。注意：转移时，易被剪枝的变量应该优先枚举。[复杂度]时间O(22NN2)空间O(2NN2)475AC★★[题意]RabbitProgramming在编程比赛中有M个选手，N道题目。不同的题目有得分Score[0~N-1]。现在已经完成了一些题目的评测。给出所有选手在所有题目上的测试情况(正确/错误)，以及还没有评测的题目的提交情况(提交/未交)。最后要在分数最高的Qualified个选手中任选Selected个人出来作为最终的队伍人选。问一共存在多少种不同的可能的方案。（分数相同时，优先编号考前的）[范围]1≤Selected≤Qualified≤M≤501≤N≤50|Score[i]|≤105[分析]数学/数论首先把已经测完的分数直接算出来，对于没测的分数，我们可以这样想：假设某个方案是可以的，我们不妨设被选中的人交了的题目都得分了，没被选中的人交的题目都错掉了，这样这个方案仍然是合法的。也就是说，我们只需要考虑每个人的最大可能得分和最小可能得分就可以了。关于统计与判重：之后我们枚举最后被选中的人中分最低的选手编号i，并定他得到了最大可能分(如果有分数相等的也只能在i之前)再统计两类人的个数：分数一定比i分数高的人数P分数可能比i分数高也可能低的人数Q这样通过组合数就可以计算答案了。Answer+=C[P][x]*C[Q][Selected–1-x](0≤x＜Selected,Selected–1–x+P≤Qualified)[复杂度]时间O(M2)空间O(NM+M2)476AC★★★[题意]SpaceshipEvacuation一个无向，每个点最多属于一个简单环。0号点为出口。初始时有crewSize个人，可任意分布在图中的任意点上。图有N个点M条边。每一条边(A,B)都有从A到B和从B到A分别的经过次数限制。现在问，最少给图中边的次数限制一共加多少，才可保证所有人都能走到出口。不可解输出-1.[范围]1≤crewSize≤1051≤N,M≤50[分析]树，动态规划不连通输出-1首先猜想最坏情况下一定是一开始所有人都在同一点。也就是我们只需要保证原点到任意点的最大流量都大于等于crewSize即可。这点可被证明。又注意到原图的性质，不难想到利用树的性质来推导，如此一来问题就是求出所有环，环上一定有离根最近的节点R。环上任意节点都必须满足从左走到R路上容量的最小值，加上从右走到R路上的容量最小值，要大于等于crewSize.另外非环边往回走的方向必须要加到大于等于crewSize。对于一个环，每一个可能的起始点，处理好左右两条路径上的数值。(我们看做可以向左或向右从两端流出环，这样就变成链了)L[i]表示环中第i点往左走的流量限制，R[i]表示向右。每个点往左右的流量和应至少为crewSize。而且L[i]+R[i]=crewSize就完全可以不用增加了。不难想到调整完以后，L应该尽量递减，R尽量递增。一个动态规划的方法是用F[i][j]表示环中把前i个点的往左的流量都≥j，且都满足各个位置上L[i]+R[i]>=crewSize，的最少调整次数。这样就可以解决本题了。[复杂度]时间O(N*CrewSize)空间O(N*CrewSize)477AC★★★[题意]KingdomTour一棵N个节点的树，现在从根出发走遍所有的边。每条边通过时都会有费用。现在每条边允许通过边多次，而且还可以进行不多于K次传送(从任意点到任意点)。每次传送的费用都是L。求遍历最后回到根的最小费用。[范围]1≤N≤2001≤K≤100L与边费用≤104[分析]树型动态规划首先可以研究路线的性质。不难发现，一定存在一种最优解，满足一旦进入了一棵子树，完成这棵子树的遍历之前都不会到子树之外的地方去。这点可以通过微调法反证。那么第一感觉是这题比较像树型背包DP.F[i][j]表示以i为根的子树，用j次传送的最少遍历费用。但是光这样状态还不够，我们必须弄清楚路线进出这个子树的状态。算法入选：F[i][j][k]表示i为根的子树，用j次传送的最少遍历费用。这条路径的端点有k个在树根上。(k=0,1,2)k=0表示路径是跳进这棵子树来的，遍历完时也不在根。k=1表示路径是从根走进来的最后不在根，或，我们是跳入开始最后回到根。k=2表示路径是从根进从根出的。根据状态的定义可以按部就班设计转移。这是一个比较直观的做法，实现会稍有复杂。另一个想法：我们注意到一条边只会被经过1或者2次。我们忽略路径的连续性。事实是我们是要把原图改造成一个欧拉图。欧拉图也就是说所有点度为偶数。传送的使用相当于把2个节点加上一个度，走重复的路也相当于加上2个度。在这个基础上求价值最小。这样可以得到一个比较容易实现的动态规划F[i][j]表示i子树，用传送加了j个度，遍历的最少花费。复杂度相同。[复杂度]时间O(NK2)空间O(NK)478AC★★[题意]RandomApple有N个盒子，M种苹果。i盒子里有A[i][j]个j种苹果。保证每个盒子都有至少一个苹果。现在任选一个盒子的非空集合(每个集合被选的概率相同)，再从选中的盒子中任拿一个苹果(每个苹果被选中的概率相同)。问最终拿到每种苹果的概率。[范围]1≤N,M≤500≤A[i][j]≤199[分析]概率，动态规划本题是一道数学概率题。对于每个盒子的每种果子A[i][j]，我们来考虑它将会对最终答案产生多大贡献。对于所有包含i的盒子集合S，贡献为A[i][j]*1/Sum[S]也就是说，如果我们能够求出R=Σ1/Sum[S](S为盒子的非空集合)问题就能得到很好解决。我们发现Sum[S]的取值范围不大，为1到500000左右，我们想到：R中分母为i的项出现了f[i]次。就可以进行DP，f[i]+=f[i–ΣA[j][x]]类似于背包再计算再直接枚举分母累加结果了。注意最后是除以2^n-1[复杂度]时间O(NC)C为果子总数空间O(NC)479AC★★★[题意]TheBoardingDivOne一维空间上有2N个位置，最初有N个人在1..N的位置上，它们要到N+1..2N去。每个人的目的地都是确定的，人和目的地一一对应的。每单位时间内，还没到目的地的人会向后走一步，前提是后面的位置空闲。注意即将离开位置的人所在的地方也是空闲的，也就是说可以大家一起往后走。如果一个人走到了目的地，就会在原地停留74单位时间，这段时间没有人可以通过该位置。74时间后，该人消失，位置空闲。按位置顺序告诉你N个人的目的地在哪，有些人的目的地是-1，表示不知道，可能是任何一个已知没出现过的目的地。现在已知所有人在T时间之内全部消失，求有多少种可能的目的地匹配方式。[范围]1≤N≤181≤T≤222[分析]状态压缩动态规划数字范围告诉我们本题很可能是搜索或者状态压缩动态规划。然而我们尝试设状态发现都不能完整表示。这时应该注意到奇特的数字大小。74和222我们知道一个人在毫无阻拦的情况下至少需要74+1时间才会消失。被阻拦一次(有人停留挡路)，就会额外加上74的时间，此时为149.这时如果再被阻拦一次，就至少需要223点时间，已经大于T的范围。也就是说，一个合法的状态中，每个人最多被阻拦一次。可以说，如果P[1..N]是表示N个人的目标位置的排列，那么这个排列不会出现长度为3的连续递减子序列P[i]>P[j]>P[k]ANDi<j<k如此一来DP就比较好表示状态了。F[mask][j]表示已经安排好靠后的mask这些元素(状态压缩)，此时P值最小的人导致的阻拦现象(只能被最小的人阻拦，否则一定>T)会把现在新加的人卡在j位置上。那么转移的时候注意不能出现长度>2的递减子序列，每次比较新加的P[x]和j即可。[复杂度]时间O(N22N)空间O(N2N)480AC★★★★★[题意]StringDecryption一个数字串可以通过如下方法编码：从前往后用1个十进制数和1个数字代替一段极长的同字子串。例如”1122”变成”2122”(2个1+2个2)这种编码是唯一的，但是这种编码的解码是可能不唯一的。比如”2122”可以被理解为”1122”或者”22222…2”(212个2)现在输入字符串S[0..L-1]输出所有通过两次编码以后变成S的不同字符串个数。输出答案对1,000,000,009取余[范围]1≤L≤500[分析]动态规划如果题目是输出一次反编码的方案数，那么很简单，我们可以用DP:F[i]表示前i位被翻译为原串的方案数。F[i]=ΣF[j]S[j]≠S[i]且S[j+1..i-1]是合法数字对于2次反编码，我们发现会出现大量同样数字的情况。这样事实上被反编码1次出来的很长一段相同数字，再反编码的情况会相对比较简单。动态规划：F[i][j][k]表示第一次解码完成了原串前i位，第二次解码的末尾数字是j。如果k=1表示第二次解码把前i位恰好用完，如果k=0表示前i位的第一次解码后还有剩余数字(开头不允许为0)这个DP的原理在于，同一段长数字，是不能被译成多个最终段的。因为他们数字都是一样的。转移的时候有很多情况需要注意。第一层转移必须满足表示数字的那段头元素不为’0’不能从同样的数字结尾转移DP的初值特殊处理，可以采用一个额外的符号’@’如果是从第二层解码用完前i符号的状态转移而来，那么一段长度为X的数字拆开有X-2种可能。如果是从有剩余的状态转移而来，那么有X-1种可能。第二层转移的数字,不允许从’0’开始[复杂度]时间O(K2N2)//K为进制常数10空间O(KN)481AC★★[题意]TicketPrinter直线上有N个打印机，位置为A[1..N]，你需要打印N个数字，大小分别为B[1..N]。打印机内部的初始数字依次为C[1..N]。你最开始在S号打印机上。移动1距离需要耗费1时间。每个打印机只能打印1次。打印一个数字需要花费1时间。更多的，你需要花费|C[i]-B[j]|的时间来把打印机调整成需要的数字。打印数字任务只要人经过对应的打印机就可以设定。调整和打印都是自动完成的不需要守候。你需要决定如何分配打印机，以及人如何行动。使得完成所有打印的时间最短。[范围]1≤N≤16[分析]状态压缩动态规划范围非常具有启发性。本题无疑是一道状态压缩的动态规划试题。容易分析出的结论是：人一旦经过某打印机，就一定会让它打印。那么在一个时间人所安排了任务的打印机必然是一个包括S的连续区间。我们用F[L][R][mask][side]表示人安排完了L到R的打印机，还剩mask集合的数字未被安排，现在在side位置(side必须为L或者R，我们可以规定side=0表示L，side=1表示R)此后还需要的最长时间。最后求F[S][S][2N-1][0]转移时考虑向左/向右扩充区间，以及新数字的选择。唯一要注意的是216*16*16*2可能超过空间限制，我们对L,R稍作压缩，由于必须满足1<=L<=S<=R<=16，所以[L][R]最多只有不到100种可能。216*100*2就不会超过限制了。[复杂度]时间O(2NN3)空间O(2NN2)482AC★★★★★[题意]BalancingAct有N个已知重量砝码，M个未知重量砝码。现告诉你M个未知砝码的大小，问其他人可不可以在不知道的情况下通过天平确定出这M个砝码分别的重量。砝码重量都是1到100,000,000的整数。[范围]1≤N≤201≤M≤4[分析]折半，枚举由于每个砝码可以选择不放，放左盘，放右盘。天平的称法有3^(N+M)种，不能直接枚举。我们注意到未知砝码不多，于是我们想，先放未知砝码，然后用已知砝码来确定两边未知砝码的总和的差的范围。我们可以把20个已知砝码分为2组。把组内可称出的重量全部求出来排序。(最多310=59049种)对于一个34之一的未知砝码的放法X，我们都可以通过枚举，求出最逼近X真实偏差的已知砝码重量组合。也就是说，我们对于每个未知砝码的方法，都能确定一个最贴近的称量法。如何确定砝码重量呢。一个思路是，如果这个未知砝码的值并非真实值时，我们得到的所有称量结果仍然不变，那么我们就无法确定砝码的值了。于是我们枚举4个未知砝码的偏差。看范围是不是会发生改变。最终可以得出这个砝码能否被确定。经尝试，只需要枚举±4的误差即可。(9M)即最坏情况：未知砝码{a,b,c,d}a=2b=4c=4d此时{a,b,c,d}和{a+4,b+2,c+1,d+1}可能测量结果相同。[复杂度]时间O(3N/2N+2M*M)//均已忽略常数空间O(3N/2+3M)483AC★★[题意]SheepN只羊过河，羊有重量W[0..N-1]。过河只有一条船，船会有一个容量。每次摆渡，羊群用如下策略：一直往船上送最重的可以上船的羊，直到上不了。然后把这批羊运到河对岸去。(船不需要羊划回来)现在羊群想在L次以内完成摆渡，问船的容量至少应该为多少。[范围]1≤N，L，W[i]≤2000[分析]枚举，贪心此题初看不难，很容易想到从小到大枚举答案+贪心模拟，但是答案可能会很大：数据：2000*2000,限制1次此时答案达到最大4000000,是O(N²)的。时间复杂度：O(N4)在已知容量的情况下优化模拟，我们先对羊群排序，加入使用跳转标记，每次用二分找剩余容量内的羊，如果不行就一直走跳转边。跳转边在走的时候应该及时更新。这样时间复杂度相当于并查集的路径压缩。我们简记为线性的。枚举答案从1开始是很划不来的。我们可以算出一个下界：总重量/次数显然答案不会小于这个值。所以我们从这个值开始枚举即可。事实证明效果极好。需要注意的是，此题不能直接二分答案!因为容量变大以后羊渡河的方案可能会改变。换言之，该题的解不满足可二分性。用二分求一个大概的答案范围，再往小的方向找也是一种成功的解题思路。[复杂度]时间O(N3logN)空间O(N3)484AC★★★★[题意]NumberMagic魔术师要做一些卡片，每个卡片上写恰好M个1到N的整数。魔术师会让小孩从1到N中任想一个整数，然后依次询问这个数是否在卡片上。小孩如实回答。问魔术师最少需要做多少卡片，可以保证根据回答猜出原数字。[范围]1≤M＜N≤109[分析]数学，数论从魔术师如何区分数字的观点来考虑。不妨给卡片编号，那么每个数字在卡片上的出现情况可以看出一个二进制数。由于我们要卡片尽量少，同时能够区分出数字来，所以我们应该选二进制数中1尽量少的N个不同的数。二分答案：x为卡片的张数那么分配的二进制数从0开始(不在任何卡片上出现)可以分配C(x,0)个然后是1个1的二进制数，分配C(x,1)个然后是2个1的..分配C(x,2)个...这样一定可以安排成出现的总数字最少。可是问题是这样一定能排恰好每张M个吗。我们注意到这种二进制编号法的可调整空间是很大的，事实上可以证明，所有的数字只要总共出现X*M次，那么一定可以调整成每张卡片都M个，而且仍然满足要求。注意最开始需要M=min(M,N-M)以保证解的最优性[复杂度]时间O(log3N)空间O(log3N)485AC★★★[题意]Deposit有两个严格凸多边形A和B，顶点数分别为N和M。A多边形严格包含B。现有如下操作:在A的边上任选一点，往A边界最远点沿直线前进。如果中途进入B那么这个点可行。如果没进入B那么这个点不可行。选点完全随机。问选到可行点的概率。精确到1E-9[范围]1≤N,M≤50[分析]计算几何这题的选点有2条限制：1.到A的边界最远;(可证明最远点一定是某个顶点)2.路线与B相交。我们不难想到分离事件线段的方法。对于条件1.我们可以求出A任意两顶点连线的中垂线，中垂线与A的交点作为事件点。O(N3)对于条件2.我们可以求A上所有点和B上所有点之间连线。同样在A的边界上留下事件点。O(N3)以上两个操作之后，A的边界被分成了O(N2)个事件段。显然每个事件段要么是全可行，要么是全不。那么我们取每个事件段的中点，用O(N)的时间寻找最远点，再O(N)的时间做一次相交检查，就能得出每个事件段的答案。累加即是总答案。本题需要用到很多计算几何的方法，程序实现比较麻烦。建议作为几何的练习题。[复杂度]时间O(N3)空间O(N2)486AC★[题意]BatmanAndRobin给出平面上N个整点，现在需要用2个不相交的凸多边形盖住所有的点。求较大凸多边形的面积的最小值。允许凸多边形退化成线段或点。[范围]0≤N≤50坐标绝对值1000以内[分析]凸包，枚举两个凸包中，总有一条凸包上的边所在直线把它们分开。我们枚举2个点的连线，再枚举这条分割线的微调，然后分开做凸包就可以了。微调只有2种：，实现时我们可以枚举点p,q。在向量p,q右手边的点全部纳入集合1，其余的纳入另一个集合。这样由于p,q和q,p都会被枚举到，所以可以考虑上图的2个情况。注意凸包退化的情况，需要输出0[复杂度]时间O(N3logN)空间O(N3)487AC★★[题意]BunnySequence给定整数m。现在对于任意的整数x都有如下变换：如果x是m的倍数，那么x=x/m如果不是，那么x=x+1求恰好最少需要n次变换才到1的这样的x的总数。答案对1,000,000,009取模[范围]2≤m≤1060≤n≤106[分析]数学，动态规划首先容易想到转换问题：我们可以从1往x倒过来变换，每次可能有多种选择。我们发现这个转移图像是不存在环的，也就是说可以直接第推不会有后效性。那么可以想出二维dp：F[i][j]表示第i次，现在对m取模是j，有多少到法。经观察，我们发现可以用部分和来优化这个DP。实际上最终的递推式就是S[i]=ΣS[i-k]1≤k≤m通过维护一个sum变量并动态对其进行更新，我们得出了一个O(N)的算法。注意最后输出需要减去一个S[n-m]。转移不能回到原点。特判n=0的情况[复杂度]时间O(N)空间O(N)488AC★★★[题意]TheBoringGameDivOne3个人玩游戏：A和B一队，C一个人一队。每轮游戏中，玩家可以任意射击其它玩家。射死队友-1分，射死敌人+1分。一旦被射死了玩家就不能再射击。当某个队全军覆没时，一轮游戏结束。然后大家复活重新开始。现在告诉你x轮游戏后最终统计的分数ScoreA,ScoreB,ScoreC以及三个人被射的总次数KilledA,KilledB,KilledC.求最小可能的游戏轮数xMin和最大可能的游戏轮数xMax[范围]输入绝对值均在1000以内[分析]数学，数论经过研究发现，一轮游戏总共有9种可能结局。我们设这9种情况分别发生的次数为a[1]..a[9]那么根据已知的6个常数，我们可以列出6个方程。注意6个方程9个未知数是无法直接解的。(事实上只有5个线性无关)经过深入研究我们发现枚举其中2个情况发生次数以后，原问题变得足够简单，以至于我们可以求出总场数，同时根据不等式判断是否存在合法解。那么就可以求最值了。[复杂度]时间O(N2)空间O(1)489AC★★★★[题意]AppleTrees直线上有D个空位，相邻空位距离为1。现在要种N棵苹果树。要求第i棵苹果树不能与其它树距离小于R[i]。问总共有多少种不同的种法。输出答案对1,000,000,007取模。[范围]1≤D≤1051≤N,R[i]≤40[分析]动态规划本题很像动态规划。但初看之下很难设计出一个计算方案的高效算法。但如果我们换一种角度思考：如果首先把树的左到右顺序排好，并且把树之间的间距缩到尽可能小，此时我们计算D-1中还有多少个剩余间距，那么可以插入到N+1个空隙中并且都是不同的合法方案。注意到R[i]也都比较小，也就是说，最坏情况下，所有树缩小间距以后占的总距离不会很大。那么我们用另一种动态规划：首先把树按R从小到大排序F[i][j][k]表示前i棵树，目前形成了j个紧缩块，所有紧缩快已经占用的距离长度和是k，的总方案数。最后我们求ΣF[N][1][x]*C[D–x+N-1][N](0≤x＜D)[复杂度]时间O(ND+N2R)空间O(N2R)490AC★★[题意]InfiniteLab有一个无限多行，M列的网格地图A。每连续的N行是一个循环节，也就是说A[i+N][j]==A[i][j]。网格上有空地、障碍物。空地上可能会有传送机。每一行只会有0或2个传送机，用于同行内的传送。也可以选择不用传送机。移动到相邻格子(公共边相邻)或者使用传送机都要1单位时间。求从(r1,c1)到(r2,c2)的最短时间[范围]1≤N,M≤20r1,r2的绝对值≤10150≤c1,c2＜M[分析]BFS，动态规划本题难在输入的行号比较大，首先我们可以把循环节旋转到以r1为起始行，那么r2=r2–r1,r1=0;方便处理接下来，我们可以求出从第一行走到下一个循环节的第一行，这M2个起止点对的最短路。同时求出(r2,c2)到所在循环节第一行各列的距离。这里可以用BFS,但是注意要多算几层循环节，因为最优解可能走出循环节再走回来。事实证明在80个连续循环节上做BFS可以取得正确答案。接下来F[k][i][j]表示从(0,i)走到(N*2k,j)的最短距离可以用类似矩阵快速乘法的方法来第推和计算答案。[复杂度]时间O(M3logN)空间O(M2logN)491AC★★[题意]FoxCardGame有2组实数A[],B[]，每组都是N个，大小为1.0到100.0。每次在两组中各取一个没选过的数a=A[i],b=B[j]分子+=max(a*b,a+b)分母+=min(a*b,a+b)问执行K次时(分子/分母)的最大可能值是多少。精确到1E-9[范围]1≤N≤50[分析]分数规划，网络流/贪心此题不难想出一个匹配的模型，首先二分答案Ans，然后对每一个配对计算对答案的影响值max(a*b,a+b)–Ans*min(a*b,a+b)以这个值为匹配费用，求流量限制为K的最小费用最大流并不断调整答案直到满足精度要求。这是一个正确的解答。然而这题的特殊性太多，例如我们会发现如果数字都≥2，那么必然匹配a*b>=a+b，可以证明此时选数不会发生大小交叉情况。也就是说，小的配小的，大的配大的。相反，如果a*b<a+b,那么必然是大的配小的，小的配大的那么另一种方法就是，首先对两列数排序枚举有多少对匹配是小-大大-小这样的(从小数字开始)再对剩下要选的数做动态规划，便可求出最大答案。事实上剩下的数也可以不做动态规划，直接枚举2列数从小的一端选多少个，剩下的全都从大的一端选。显然不这样取的方案一定可以通过调整变成这样以后答案不减小。[复杂度]时间O(N4)空间O(N)492AC★★★★[题意]TimeTravellingGogoN个点，M条无向边。你要从0走到N-1。有S段时间是不下雨的，只有当不下雨时你才能够在路上移动，下雨时你必须躲在点里。你有一个时间机器，当你逗留在某个点的时候你可以花StartTime+x的时间把天气变到x时间之前的状态。也就是说，你可以倒退到不下雨的时间，但是你不会改变位置，你已经花费的时间也不会被扣除。求最短需要花费的时间[范围]1≤N≤201≤S≤200≤所有输入的时间≤109时间段按照从小到大，并且均是独立的时间段。1≤边权，机器启动时间≤109[分析]离散事件，最短路本题无疑是一个最短路模型，关键是如何建边。我们不能用State[v][time]表示在v点，天气运作到time时的最短路，因为time的范围太大。一个很自然的想法是，我们是否能离散出一些关键的时间点来缩小状态量呢。首先发现点数不多，我们不妨先做多源最短路把两点间距离求出来。实际上在一段不下雨的时间中，我们也只会从一个点到达另外一个点。这样为了时间最短，我们一定会尽可能在雨停的那瞬间从一点出发，或者使用时间机器时倒退到一个时间点使得出发以后刚好在要下雨的时候到达另一点。这些时间与位置就是我们寻找的事件状态。我们也把时间机器是否打开看做另一维状态。这样一来，我们用State[v][time][is_open]来表示状态，对于每一个v，最多可能有N*2*S个事件时间，源点多一个事件时间0。按照事件状态间的转移来在新图里建边，这题就不难了。用Dijkstra+Heap可以达到很好的效率，用SPFA也可以通过。[复杂度]时间O(N2Slog(N2S))空间O(N2S)493AC★[题意]AmoebaDivOne有一个2N*2M的01矩阵。输入的字符串每一个字符为一个1位的16进制数，表示4个共角格子的0/1情况。比如’8’表示：0001现在要选出一块连续的”0”,使得任何一行或任何一列上选的0都是连续一段。求总共有多少种选法，输出答案对1,000,000,007取模。[范围]1≤N,M≤50[分析]动态规划此题是常见的区间动态规划模型。F[i][x][y][p=0..1][q=0..1]表示我们选的形状到第i行是x到y,左/右边线是否已经缩小过了(p/q)，这种情况下有多少种方案。注意考虑转移时边界相等的情况。我们发现这样是O(N*M5)的，需要优化。容易发现可转移状态是列号上连续的，所以我们可以使用部分和优化。G[i][x][y][p][q]表示ΣF[i][0..x][0..y][p][q]这样就可以方便的O(1)转移了[复杂度]时间O(NM2)空间O(NM2)494AC★★[题意]KnightsOut一个N*M的01矩阵，初始时全是0。选一些格子，做以下操作：例如选择了#这个位置，那么要把#和标了1的位置的格子全部取反。(类似国际象棋的马)010101000100#001000101010问有多少种选法，使得最后变成全1。输出答案对123,456,789取余[范围]1≤N,M≤150[分析]高斯消元本题模型是求模线性方程组的解的个数，(每个格子是否被选作为未知数，最后每个格子的相关点的异或值等于1作为方程)该方程组的解个数也就是2^x其中x为自由元的个数。但初始时是N*M个未知数，不能直接高斯消元。为此我们想到化简方程组。经过推算可以发现，一旦前2行以及前1列的格子对应的未知数确定，就可以直接推导出所有的未知数了。我们选这些未知数为代表来列方程组，这样一来方程组的大小缩小，可以求解了。注意使用位压缩的办法来提高效率，C++的同学可以使用bitset[复杂度]时间O(N4)空间O(N3)495AC★★★★[题意]StrangeElevator一栋大楼有H层(1到H)，有一个奇怪的电梯。电梯包含N个房间，两房间的高度差是固定的，且没有两个房间在同一层楼。电梯可以上下移动，但是不会出现某个房间高度小于1或者大于H的情况。可以限制电梯只能在哪些高度开门。求有多少种电梯的设计方案满足：每层楼都恰好只能从一个电梯房间到达[范围]1≤N≤H≤109[分析]动态规划此题数学味很浓。首先我们发现电梯一定会停靠H/N次，如果H不是N的倍数那么就无解。对于每一次停靠，电梯的每个房间都会对上一层楼。如果我们给楼层标上数字，就会发现每个数字的出现区域是全等的形状。电梯1.1.....1.1......2.2.....2.2........3.3.....3.3......4.4.....4.41212343412123434一个关键的思路是，一个电梯方案如果可行，那么以其中某个房间到达的位置为新电梯位置的另一个新方案也可行。比如对应上图。(四个”1234”的位置)11..11............22..22................33..33............44..441122112233443344也就是说，一个(H,N)的问题是和(H,H/N)的问题完全等价的。我们把这种变换叫做变换1进一步分析，一旦有K个电梯房间是连续的，那么H还必须是K*N的倍数。在这个情况下，一定会把楼层每连续K个分成一段来算。然后缩小成(H/K,N/K)的新问题。为了避免重复统计，我们设计状态：F[i][j]表示i层楼，j个电梯，而且不存在相邻房间的方案总数。我们发现在变换1之后，一个不连续的电梯方案会变成有连续的；一个有连续的方案一定会变成不连续的。那么可以设计转移：F[i][j]=ΣF[x][i/j]//x为i的非1约数。转移的意思是说，求一个不存在相邻房间的方案总数，通过一次变换1以后相当于求所有存在相邻房间的方案数。然而有相邻的情况下就可以缩小问题规模，当然必须满足段的数目是层数的约数。(从F[i][j]=F[x][x/(j/x)]