集训队作业表格

1、byWuSenfrom N2MiddleschoolofIOI2009 中国国家集训队第一次作byWuSenfrom N2MiddleschoolofIOI2009 中国国家集训队第一次作要求完成下表中所有场次比赛的题目(并在表格中填写相应内交带注释的程序(CommentedProgram：唐文斌胡伟提交: evichs1 / Andrew evichsContest题题目名题目大算给定一个自 ，自 在读行(若出现环则无法转换)。求自 处理的长N字符通过转移可以得到的字符j，然后dp(i,j)为状态， i-1,j.i fj,kj 通过 转换为 字符 byWuSenfrom N2Middlesc

2、hoolof2 / 度The Towers of byWuSenfrom N2Middleschoolof2 / 度The Towers of N盘子M柱子的 2+dpi-1,j-k)。i表示柱子数jHuffman码后的长度序了，所以可以O(n)的算法解决Little 有一只青蛙，要跳过两堵墙，边缘高度分别是t1、b1t2、 b2。两堵墙之间的距离是 l；青蛙从距离左边一堵墙 ds墙df位置要求出青蛙需要至少能提供多大的起跳速题分解为两只青蛙分别从S点与E点向中间跳,跳到中间的一个点，最大速度V，,然后求出来第一只青蛙从S点以这个速度，则此速度V可以，改进速度V，直至找到速度V越大，可达区间越

3、大。给出一列数Si一个m*s矩阵A(ms128m,s均为2的整数次方)。求一列数 Ki，K0=0Sum|AK(i-1) mod M, Ki-Si|最小。mod m,j-xi);算法复杂度 O(mns一个无向图中有 N 个点，M 个边和N个点一起树。每个边有一个权值Ci。先Di，保证以为权值，1.N-1的边和N个点一起一棵最小生成树，且使得|c1- d1|c2-d2|cm-算法ai, bj。的权值应当大于环上所有边的权将所有在生成树中的边抽象成匹byWuSenfrom N2Middleschoolof3 / |最小byWuSenfrom N2Middleschoolof3 / |最小树中的边抽象

4、成匹配图中右边的max(ci-cj,0lx 为左边边权变小量，ly 为右边注意把二分图的xy轴定点有N个强盗到了M枚金币，i个强盗要Ki枚金币，使得sum(|Xi/Y - Ki/M|)的值首先按 ki=m*xi/y 取下整,然后按照误差进行排序,将误差大的优先进行增加 ki。运用heap 进行优化。可以O(nlogn)解决。一个 M*N的格纸，黑白相间染个 1、按向量（x，y）“平移”，使（i，j）变换到（i+x）mod（j+y）modm）上2格纸旋转180（M=N时，可以转90）（若两种染色方案置换后相同，认为是本质相同）用 Polya 定Andrew evichsContest题题目名题目

5、大算平面被数条直线分成若份，求所有封份的面求出所有交点，以及那些交点有边相连，随便找一条边，然后每次从新到的顶点找一条和入边逆时针夹角最小的出边。Beloved一个二分图左右都有 N个点，左边的每一个点i有Ai，要求找出一个匹配使得sum(Ak2)Ak配中算法：匈牙利算法先将所有左节点按Ai排序好序后依次有一种新的表示数的方算法：构造使得这列数中相邻的两个 2 之间有一个 byWuSenfrom N2Middleschoolof4 / pnp（n-1）.p1， +pn*2nbyWuSenfrom N2Middleschoolof4 / pnp（n-1）.p1， +pn*2npi 为 0,1,2

6、, 要求每次加上最多可以改变4。即可满足每加一个数，最多改变 4 位。上的 2向前进位构造出一个 0，满题意将一个图的顶点分成 L算法：贪流+dinic由于图中的点已经分成了 L 层，不妨使用 hlpp，dinic分层 的高效网络流算法，但是均 TLE,于是进行优化，加入了贪心初始流的优化再用dinic进行网络流，结果ac。给定一个无向连通图，求出尽可能的独立割算法：构造，SPFA独立割集的数量一定小于等于起点到终点的长度，然后把边按到起点的长度分类，既是独立割集。找等长的串A 与B，使S是A的子序列，TB子序列，且 AB的差算法:经典的 lcs1当前的AB 。2.A其差异最小的字符匹配。3.

7、B其有一个表达式， 两种操作，第一种是计算一个表达式的值，第二种是可以对任何一个变量与常数将值替换成另对以改变值给定一个无向连通图，将其分成若干个部分，每一部分有一个中心，中心可以不在这个部分，但这部分上的任意点到中心的连线上的点必须属于这一部分使得， 并且这个部分有 算法：构造找到一个点当做根，以此点开始深搜，将其子树划分成若干个节点数为,b中心为此点节点数b个，回溯，将此节点的孩子数变为剩余节点数，将划分好的部分从此树中删去直至原树中b个节点。将剩余节点划分给最后一个区域，这样既可满足要求。求两个轴心垂直的两个圆柱体的公共部分的体数学公式Ans 8 A*A x*x* B*B0Andrew

8、evichsContestbyWuSenfrom N2Middleschoolof5 / 题题目名题目大算byWuSenfrom N2Middleschoolof5 / 题题目名题目大算点为圆心的不 圆的面直接计算。三个圆相切既是面积最大I Just superregion ， 每 个 superregion又分为了许多region，还知道一共有 16种不同的打算法：模拟给出N个按顺序排好的单More定理：设a2t1*3t2p*tk（其中p是第k大的质数）是反质数，则必有：t1t2t3tk = M*N矩阵中摆放 1*3算法复杂度O(n*3m).一个 上有三排数量相算法：模拟首先要把这些点的角度

9、变换为0， 2p，根据已知肯定有交叉是不会后最有优解的。所以可以用O2Cracking找出序列 p1p2pl，使 1pi|)最 i表示第ij表示这一位上是字母j， k示这一位上是字母 k。byWuSenfrom N2Middleschoolof6 / byWuSenfrom N2Middleschoolof6 / 算法：枚举枚举出所有可能移动的向量,判断是否个点的入度仍然不小于 算法：网络流流量-2，如果有点的容量2则无解然后进行最大流即可流过的边即为已知平面上有 N个点，没算法：凸包+动态规划形的任意三角形剖分数(dpi,j,k表示三角ijk 的剖分数），然后用动Unfair给出 M题的相关

10、参量 Ii,Ai,Li,Oi伍的相关参量Tj,Zj,VjCj，在 M N使队一尽量高算法：模枚举c(M,N)种可能性，再根据题目要Andrew evichsContest题题目名题目大算Unique 判断一个无向图的割算法首先用dinic出最大流，然后分别从头尾两边bfs（条件边还有剩余流量），算法给定 N 个圆的 X,Y求这些圆将平面分成算法：平面图欧拉定理首先求出圆的交点 P，和这些有这些点所连成的边数 L，和着图中的连通分量的个数Q，ans=l-p+q+1.要求按照题目中的要算法：模拟有制作日期和所属地域，看不同地域的 DVD一台DVD求最算法：动态规i，转化了 j模式，注意每次的话中间

11、可能要调整模式看尽可能多的byWuSenfrom N2Middleschoolof7 / 不可以调整5次模式，按日期先后看尽byWuSenfrom N2Middleschoolof7 / 不可以调整5次模式，按日期先后看尽可能多的DVD（相同日期可VD,这时要用贪心策略进数中以i开头，满足所有Sij0 的数的总和算法算出以 i 为开头的最小的Sj（首先求出1后倒序完成从 N-12 ci:=min(ai,ai+c(i+1) mod n)）然后O(N)扫描一遍即可。给出此次比赛的一些算法：模拟根据题目描述模拟出从(1,1) 到(m,n) 的算法：BFSAndrew evichs Contest 题

12、题目名题目大算求出A(n,mmodA(1m)可以直接求A(2m2 m，也可以直接得到答A(n,1)=A(n,2)=A(3m222 2mA(4,3)=A(3,4)= 由于收敛的性质m = 4A(4m) = A(44A(365536)。A(4, m) mod t已经收敛了。所以这里只A(3, 99) mod t可。定角度使得向量的矢量和为 0。然后根据移动角度算出，移动后注意精度求精度 1e-10 以上才可通Yellow给定一个数 n，求一个序列从 02n-1 使得这个序列的进制表示形式的不同数位有n div 2以上。算法：枚举满足条件即可为下一个数，直至最后byWuSenfrom N2Middl

13、eschoolof8 / Yet Another byWuSenfrom N2Middleschoolof8 / Yet Another pnp （ n-1 ） .p1 ， m=p0*20+p1*21+ +pn*2n,其中 pi0,1,2。问一个数n 的表示形式有多算法：动态规划到最低位进行动态规划。如果第 位是0： dpi,1:=dpi+1,1 i位是 则dpi,0示不向下一位1， dpi,1表示向下一位进1。注意要用到高精度calOrdering给定一种排序方法数字和小的放满足 1序小的放 面，字母序1n序后，k 在第几个以及第k是几。算法第一问可以转化成第二问给出一个六边形的边长和一个圆

14、的半径， 两图形同个货物可以往哪个货场中好的货物移动的话要付一算法：费用流些小的优化初始时放好的货物的流先流完进行费用流就不会超时了 有一个图灵有u 个状态和含有s个元素的的字符集，以可能有一个单词，其余为次根据转化原则把当前状态对应字符转移（包括状机是否可以对任何单词都不存在运行中出现指针左算法：bfsdpi,j,k,i 表示当前状态，j 表示对应的字符，k示 指针是否已经移byWuSenfrom N2Middleschoolof9 / 移的情况byWuSenfrom N2Middleschoolof9 / 移的情况算法：快排的 过第二个死角再把这两段各分成两Andrew evichs Co

15、ntest题题目名题目大算给定两排点，要求按照给定顺序使得让上边的点和下边的点连接，要求不能相交。求出连接算法：模拟首先 在两排点之间假设有一个隔板，给定一个有向无环图，并且知道其中哪些边需要反向，要求终止状态也是有向无环图。要求安排一个边的反向顺序的方案，使得在变化的过程中整个图一直都是From给一篇英文文章要求把其中的英文数字变成阿拉伯数字，其余不变，（如果有多个数字并列，这要求前面的数字尽可能的大。有一个国家有N个城市M条有向道路，要求选出其中的 K个城市建立警察局，使得任何城市可局并且所有警察局可以到任意城市，个点，其他的任意。然后用动态规划解决， fi,j表示到进行到第i块时建j警n

16、um ( i dp i, j dp i 1, j k C num ( i k A(t)，B(t)和 C(t)，求出多项式 x(t)（512），算法：高斯消元对于x(t)的平方中，只用考虑每一项的平byWuSenfrom N2Middleschoolof10/ byWuSenfrom N2Middleschoolof10/ C(t)的每一项的系数都为偶。（多项式的系数01）程组即可给定一棵树N叶子之间的距离，让你还原具体参见杨沐给一个长度为 n的数列，将其分成尽可能多的段数，使的每一段中含有 AABBABAB “ABBA”或“AAAA的一种数字组合。求方算法：动态规划由于每个组合可以看成是两对数

17、字的组合，所以可以用动态规划来进行求解， dpi表示到位置i多能分多少段。状态转移1.由 i-1位转移，忽略当前数字2.1 至 min(prei,prej)-1 转移,(pre 和当前数字一样的前一个的给定一些人被分成若干组，要把他们分成 9团队，每团最多 4使得总满意度最大（满意度为每组的满意系数*人数*（人数-1）算法：动态规划dpi,j,k,i示当前分到了第 i组j表示前i组中被分成一组中被分成了3 或4人一组的组数，k 表示前 i 组中被分成一组中被分成了2一组的组数。状态转移dpi-1,j-1,k+sum1i组人数超2dpi-1,j,k-1+sum2(第 i 组人数byWuSenfr

18、om N2Middleschoolof(2)MITRelatedProgramming/)11byWuSenfrom N2Middleschoolof(2)MITRelatedProgramming/)11/ MIT Programming Contest 题题目名题目大算通过二进解决详见本有 N个城市分别用各自的长度为l路的时间。询问1：二分有多少城市已经造完路询问2：只要二分询问1。A City of 有一个MN的城市，已少c人，最多C人，求出这个城市拥有的人数范每行高度为Ak ，每列高度为最小值问 max( Ak , Bk M N 栋楼在已知每表示东西两栋之间可达，起点，每栋楼只走一遍，

19、最后走完M N 栋楼，算法：动态规划设dpi,j,k为走完矩阵的 i，j的最大值，k 为在矩阵的那个位置，2表示左下角，3表示右上角，1表示右23可以转化到byWuSenfrom N2Middleschoolof12/ DialingbyWuSenfrom N2Middleschoolof12/ Dialing给定一个 号码，和一个 ，每拨一个号码就转动一下 ，并把底面的数字 下来，让你设计这个 使得差异值最算法：动态规划如果把问题 成给定一个 求出每次拨打的号码与转动 差异值最面即可（尽要从号中有的数选，有肯能出现数字很少的情况60序现有4 个柱子，每个柱子出两组3个柱子，问是否加入第一组中

20、白方必胜，对于每根柱子的状态，给其一估价，局面的估价不小于第二个的， 为 出哪些圆不被任何圆包算法：线性扫描法首先离散化，圆的纵坐标，按照X轴可以用树状数组减的，且长度大1。分算法：dfs+剪先贪心求了个 的上限。贪心就是找一个全是非递减的序列，或全是非递增的序列。每一步要么跟随一个非递减（或非上限则跳出。如果要跟随非递增（或byWuSenfrom N2Middleschoolof13/ 非递减）序列，尽量跟末尾大（小）byWuSenfrom N2Middleschoolof13/ 非递减）序列，尽量跟末尾大（小）MITmContest题题目名题目大算给你N个单词，可以通过将单词进行为L 的串

21、可能在长串中出现。首先确定哪些单词可能在出单词中出现的长度为LK位二进制数1，把它们连续地分成M份，使得二进制下1的个数最多的那一份的1 的个数最少。算法二分 。对于的每一个答案用贪心法判断 是否可给出Nd的点，求出它们之间的有N 条水平线段（两端不可取），画任意多条竖直的线使得每条线至少算法：差分约束用差分约束系统判断该是否可行Tree给定一棵高为 h的满二叉树，叶子节点 是 01，其与节点根据其子 1，此节点的 0，否则是1。现在询问一些叶子节点的 （共2h前，不会出现可以断定没有询问过的叶子的 。兄弟的两个点中不能出现一号确定后和它相关的只是他祖先的 。所以保证每次能推出来的最高的祖先节点是一定角度），并且在N 个位置测出来了北极点的方向但是方向所延长出算法：枚举每次枚举一个非常小的角度是每个点测量的方向移动这注意精度经典的mario ，在一个N*M算法用 化搜索fi,j,k为状态表示他在第i 行第j列，此时拥有k命的 。String 已知现在有两个字符串，并且有算法：动态规byWuSenfrom N2Middleschoolof14/ byWuSenfrom N2Middles