付费下载
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
IOI2008中国国家集训队第二轮作(截止时间:200853日:明(包括是否已通过数据50个通过测试数据的程作为参考的,所以相信大家会自觉的做好榜样大家去年YY和QRQ的表格,另:(同时也是准备CTSCreadme.txt。。ACM/ICPC欧洲赛部分题目提交:(提示:由于上次已经过CERC2004~2006,这次没有写在里面。如果准备填写,请NEERCNEERC题目和测试数据、参考程序:给n个白点和n个黑要求每个白点恰好个黑点恰好连接一个白点。BuildingforH层楼,每楼是W*L网格的,每格恰好属于一个不同国家都有一对同层中有公共边的设计的最多不1,000,000Cactus给一个n个点的即两点距离的最大到为u的结点,u的儿子结点的为v定义变量len[u],len[u]’(len[u]>=len[u]’),表示当前从u到DFS树中以u为根的的所有结点的最短路径的最大值以及次大(len[u]与len[u]’不能来自u的同一个儿子;ansu、v:low[v]>dfn[u]len[v]+1len[u]与len[u]len[u]’。当对u所有的儿子都遍历完之后,再尝试当整个图都遍历完之后,ans潜水员需要从深度为d的水里顺着绳vs的速度作从绳子一条鲨鱼的距离不vd的速度沿着绳子上移或xy轴,平面上的点表示圆的切线非常麻烦,因我可以将x轴vs倍,这样所有的椭圆都变成了圆,人移动的斜率要求变成[-vd/vs,vd/vs]。x2*w出现一次。可以证明这样一个定理:若从一个圆经过次循环(2*w的圆)可以到达另一个圆(无论f(x)=0,其中示,包含四则运算x最多出现一次。保证不会出现除以0x,使得ax cxFund你有c但没有m间和n支供nkkilot数都过k,且最后一天结束时第i只的一个lot是si股,且每天持有的lot数过ki已知每个能买一只或卖一只的一lot,最后最多能剩多少 ki<=k,1万多。开始第k个人手上人随机往左或往右pi所有人至少拿过一后一个拿到球的人N个人pl[i,j,0]ij个人都拿过球且当前i个人手里,下一个拿到球且之前没拿过球i-1的概率;pl[i,j,1]ij个人都拿过球且当前i个人手里,下一个拿到球且之前没拿过球j+1的概率;pr[i,j,0与pr[i,j,1]的定义类似与pl[i,j,0pl[i,j,1]jd[i,j,0]表示第i到第j个人都拿过球下一个拿到i-1的概率;HanoiHanoi塔问题的构造解法:把六种移动(A,CB)排序后选择另外不能连续移动n求解Hanoi问题的步以都在B也可以都C不妨定义f(n),表示对于当前的移动序列,f(n)=a*f(n-1)+ba、b均为常数且a>b。因此可以先通过模拟求出f(2)与f(3)a和b的I18nIn18后的文章,进行展词必须是以前出现Japanese给一个字的正确写,判断某个写法是否正使得后所有笔且任何两个端点的相对位置(向)mi块不相交的凸多边都至少得到了它期n<=30,mi<=30定义recx1,x2表示矩形((x1,inf),(x1,-inf),人所选的区域都是一个类似于recx1,x2的矩形。然后我示第i个人得到的凸多边形土地。每一次,通过S(areairecinf,x2 ,这里inf可S(areai 土地的右边界。容易证明,ans是满足条件的。给一个n个字符串个DNA例如{fix,foo,ox}。n<=5000,串长均不于每一个结点计算出Trie中以它为根的的hashNWERCbn个配件的种类、质类型的配件各买一且质量的最小值尽 n片荷叶,坐标为(xi,yi),上面ni有mi只企鹅能从上鹅在同一片荷叶上点?一只企鹅每次D给出一个最大面积8*8在房间的开一子对应一个空位或可以到达周围4个最多可以到达多少8*8,所以可以使用基于连通性状态2万多个。当前要放的格子只有两种情况,因此每个O(Tn2),T是状态总数,不过系数很大。本题还可以通过构造AC(除非写一个dpcheck),因此如果不是比赛时, Enemy在一幅左下角坐标为(X,Y)且所有点均标位置以及敌军基求出一条离最近的敌军最远前可以先通过一次多源BFS,求出地图中每一个点离它最近的敌军的距离,不妨设为dis[x,y],dis[x,y]离敌军的最远距离就是dis[x’,y’],最后再通过一BFS即可求出最短路径的长度。算法的时间复杂度O(XY)。Flight(3≤M≤30条线段构成的折线大陆的最近距离的先二分答案,然后将每一个简单多边形都扩展为由原简单多边形、圆、矩形组成的图形,那么的任务就转化为判断航线是否被扩展后的图形完全覆盖。对于航线中的每一条线段,先求出没有被扩展后的多边形中的圆与矩形覆盖的小线段,然后由于如果当前的答案是可行的,它只可能被某一个原简单多边形完。所以只需判断是否每一条小线段都会被一个原简单多边形完即可判断出当前对于一个高度为h度小于等于h-d的点就不能到达一个比summit。给出中每个点的高度以summit。分量中的最大高度。不妨假设当前从点v开始遍历,并且它的高度为h’。利用BFS,对那些还没并且它们相互之间的连通性以及最大高度。若当前遍历到一个之前已经遍历过的点,不妨设为u,那u在之前已经被某个高度大于等于h’的点遍历过,因此只需找出u所在连通分量的最大高度,并且判断该高度与h’的关系,即可知道v是否是给出n条互不相交,形状为简单多边形理想的情况下从点 (100000,0),最小的海拔上升总高度与不妨设点(0,0)为点A,点(100000,0)为点B。对于A、B均在它的里面或者均在它的外面那么总是存在一个办法使得从A可以到达B并AB的x测试数据、参考程序:给出一个已经填完的数独与一个未填18027090。。未填完得数独能否成为已经填完的数3columnsegment3row个rowsegment里的row的变换方案以及每个column STLTicketto给出一个无向边带n<=30,边数出的4对点要在该动态规划解决该问题。可以用f[i,st]表示以i为根,给定的8个点的连通状况是一个2进的st。转移O(38n+28n3)。Then<=70本书放到书厚度不超过30,高度不超过300。要层的宽度的最大值*这是一道背包类型的动态规划题目不妨将n-1本书放好。定义f[i][L1][L2]表示将第1到第i本书放好,且第一层书架的长度为L1,第二层书架的长度为L2同时为了避免后效性,要先将剩下n-1个人按宽度从大到小排好序之后(W[2..n])DP。最后的答案就是时间复杂度OnTi2。如果本题就这么结束5f[i][L1][L2]f[i+1][L1][L2]if[i][0][L2]+Wif[i+1][Ti][L2]if[i][L1][0]+Wif[i+1][L1][Ti]if[i][L1][L2]f[i+1][L1+Ti][L2]if[i][L1][L2]f[i+1][L1][L2+Ti]if[i][L1][L2]f[i+1][L1][L2]都是向f[i][≥L1][≥L2]的转移,因此适当的顺序可以让3.如果sigma(L2..Ti)=sum,那么4.状态的定义是f[2100][2100],但是3个特点:Ti比较小(Ti<=30)且比较接近,且Wi在 况下,分别解得最大长度为总长的和( 举的是较小的两个,故不超过和 2Ti30,因为根据性质 总可以使每个5PrinterPrime给出许多座连续的的数目n<=要求在群山上建一个长度L上的[l,r]时,且结束位置都在同一条线段上,那么可存在置换F满足考虑G那么总可以构造出一个同样长度的循环节F,使得F2=G2nF,F22个长nn为奇数的情况,只需n为偶数的情况。显然,如果循环节的长度是偶G中长度为偶数的循环节的个数,如果存在奇NWERC测试数据、参考程序:n<=5在1~10之间。设能够组成糖果盒质量为k的方案数k 给出若干件产品及知道其中一小部分于某种材料它在那间产品中使用的百最小和超过100%或者最大和小于100%则是的,Pesky n(n<=500)个人的及一些资料,并且给出了要符合多可以选出多少个malefemale中的人作为二部图的XYUptheACM/ICPC亚洲赛部分题目提交:(提示:有很多题目无法提交。这些题目只需要读题(对于我已经给出题目大意的题目最好也重新读题以了解细节)Japan ThereWasOne几乎就是Joseph问题,第mkPrime素数和前一个素数的差(输入是素数时输出0)N<=1299709(100000个素数N1D棋盘上玩一个色子(掷几点就走几步T轮成功(Goal)的概的格子。N<=100,之前所有六个顶点的坐都要为整Geometric锐角的一侧驶过Slim给一个n结点的图,求的值) w*h网格上有一些(最3种)小写字母(鬼别移动它们对应的大写以直接广搜不过内存承受不了界上都是,所以可以把网格开少任何一个2*2子网格至有一个格。w,h<=16格Bug界MostDistantPointfromthe给一个凸n找一个点界尽量远原题并不是很枚举三条边再判(n2(kn),k是二分次数。顺便思考的问题有点像01年ldfinal的Helicopt3(点或线段,然后判断,复杂度(n)。思q的。我现在的想法是使用模拟退火算用模拟退火的条件想法是先进行三然后对n-2个三角形分别进行模间复杂度就保证不了了想法是随机没有计算的必要摊时间复杂下降一维TheTeacher’sSideofMath给一个数tmanb,求一个次数尽量小的多项FF(t)=0,要F数。本题中ab是不同的素数,且m,n>1。可以证明最小次数为mn,最高次项系数ad=1。输保证t<=4mn<=20,答案的各项绝对值不超过231.JapanHowIWonderWhatYouAre!判断(0,0,0)-(x,y,z角度为的无线大圆锥里有多少个 YouAre!判断一个简单n边形是否8数码问题每个立的滚动使得上表面是一个给定的颜案有多少种方法可以把n写成k个不同素数之和?n<=1120,n*m网格有一些,要求把两个2和两个3分别用折线连起来,总长度尽量状态压缩dp好像有点大材小用。可以好像这题的状态dp很简单,怎么确定任何一条路径呢?这个问题比较难以克服已知x,允许乘法和除法,最少通过几次运算能得到本题的主要思路是迭代加深搜索+剪枝,具体的剪枝有:1、设当前枚举到的答案为ans’,当前的深度为dep,当前状态中最大2、若当前的maxv>2*n,则剪枝3、为了避免重复搜索,对于每次的maxv参与否则可以当这个通过上面的剪枝已经可以通过本给n条线段的长在网线段最多有36种方法,那么总的放置366×61.第一条线段可以不用枚举,the上连接成面积最大的多形。相邻边可以共线。每线段恰好用一次。且可以规定方向在某个象限90o,时方案数为9*365×5方案数为9*364×5使用的角度一定要比上一条边大,比(-x,-y)小,这样发案数进一步缩小到9*184×5如果当前到达距离比剩余的过和优化3有较大,效果按边长从大到小排序此时程序仍然会TLE,我另外加这时程序运行的速度就相当快了 NameforYour给一个包含n条规则的上出该文法能接受的长度恰L的字典序最小串。n<=50,L<=20义状态f[i][j][k]表示第i个转移方法的前(后)j个字母能表示的长度为k的处于不可转移的状态的最小的字符串长j的处于不可转移的状态的最小的字符串是什么。那么可以通过f[i][j和s[str[i][j+1来转移得f[i][str[i][j+1]][]。但是注意这样的情“A=’’B=’AB’的时候需要知道s[‘B’][x],但只有计算得到了f[2][2][x]后才能得到s[‘B’][x]这情况,也很难理解,复杂度可以做到当作点、转移看成边做spfanl2这样复杂度要多乘一个spfa的数,根据实践这个常数大概为7~8。者都能通过测不过使用spfa更容易n结点有向简单图中的简单k(结点不能重复经n<=50,路径的长度加上一个剩余距离的剪枝信息,这个剩余距离是dis[k][i],表示从i到终点只通过k~N的顶点的最短距离,这个东西可以通过Floyd预处理得还是不错的,当然这个k是要在搜索的过程中,我觉得我比搞的好一个的数据让这个方法TLE也是另外对于这一类问题,有一个多Japan Colored有n(可以旋转anizeYourx条铁轨y个中转线路连接。有一辆由n个车厢(用小写,目标状态。x<=4,n<=10本题如果直接从初始状态开始搜索的话,搜索量十分巨大,TLE非常严到题目给出了注明了答案不会6,因此搜索量就可以大大减少。实现给出房间的宽度r和s个挂这题由于数据规模较小,因此是一重量wi,使得一个尽量宽(但道简单的搜索题目。首先枚举能超过r)的天平,挂着所有的排列顺序,然后搜索出所有坠。平的构成方案,对于某一个方以用线性的时间递归计算出长度O(s!*(s-=O((s!)2) 有n段道路,长度分别为ai。可以不换。换轮胎的时间为b,越慢题目中给出一个分段函数)间尽量小。Network给出一个棵n叶子无权树两两给你nm*m的矩阵,同一个找一个最短的叫数的序列由于每个矩阵被bingo的方式2*m+2种(m个横行、m个竖行、两个对角线,因此i个矩阵bingo的时间不晚于第i+1个矩阵(一个矩阵bingo是指该矩阵某一横行或某一竖以先枚举出每个矩阵被bingo的方式,这样就可以知道有哪些数要被叫到,接下来只需要确行或某一对角线的数都被叫是否存在某个叫数的顺序符合矩到。2<=n<=4,3<=m<=4于判断是否存在某种叫数顺序符合题设规则,可以用位压来实现。具体来说,定义d[(state)2]表示对于当前的状态state是否合法,state表示有哪些的判断可以在预处理中进行需要加入一些优化。不妨设S为当前所叫数的集合,ans为当前1、若Sans则直接退出2、若从S中删去某个元后,依然能使全部矩阵bingo,则直接3、若对于每一个矩阵都存在一个数v,使得vv属于S顺序符合题设规Shy水平移动一个多边形A,使得它和另一个多边形B的距离不小这题和前面的FlightSafety很相像就没写代码讲一下思15,至少有一个顶点到另一个多边形的点或边的距离为(给出的定值,否则可以移动到距离为L且答案不会变差,除非两个多边形在y轴上的投影距离大于L,这种情况很判断的时候可以将某个多边边形的边边、圆边进行度是顶点的六次方级别Japan不错的一套The LoginDice把一些全等的Dice拼成3*3*3上的数字未知,用0表示,求(9之和即可Colorthe平面图。最多10个面 空间里有n个球有一条平行于z平面的扫描平面从上到下扫离散扫描行于xOz平面它和它在xOy平面内旋转90o后的棱柱的交的这个提炼后容易知道新多面体的因此可以枚举y方向的棱柱的之相交的部分在yOz截面上的面以该斜面与yOz平面的余弦值就是实际面当然当夹角为Japan 网格上有一个简单N和多边形的相交面积为正的单 你有两个房n个预定请求(i,j,w),表示ij租用一个房间,出价为w。接受一些请求使得总收益尽量大意时间有的请求不能占只有两个房间也是最小费用动态规划状态的定义是。。同一个房间。(i<=j)表示两间房间分别用了i和ji=j时,要么两间房间同时出租,要么只出租一间转移到f[i+1][t],t情况下是O(n2)。当所有转移拓扑有序且非负间房间就是找一个从时刻0到时刻使用SPFA实现的理论代价为事实证明求费用流的速度大大优于动态规划,而且易于Monster给平面上n条线段组成一个迷无(逃离迷宫4个距离线段端点放两个可以到的点之间连一条边可以假BFS就是人可以走到的点。最后要判断哪些点走到就可线段覆盖的角度然后排个序判断覆盖情况。总复杂度为O(n3logn)Bitwise比 Bitwise所有题目都有分析和参考资料,请有的同学查阅后整理在表格中请填表前先把题目大意写下来。1 CoinSafe(100)N*2M(N,要求给它铺1*2的条横线和竖线上至少被一条多米诺骨造的基础是5*66*8的情况(6*6的不能推2 开关动一下j个始开关全是1,要求1过问题的关键在于这题的未知数有800之大,Gauss-Elimination的瓶颈在于消元过程,而本题的系数非0即1,因此可以位压后,是O(n3),但是常数可以减小约30倍3 Delivery(200)一对边都有一个公本题是一个经典问题,易知对于一棵树来说,必然存在这样一个分拆,因此对图中的顶点进行拆点,使得每条边在新树中对应一条边。此时递归地求出树的分拆,问题就解决了4ADatewithScrooge一个n*n个格子都有n个候使得每个格子选出构造方法比较复杂,地址marimhtml/dinitz.tm上本题直接采用随机调整的方法就可以取得不错的效果了。5OpeningaStall3t+1pa,bSolution中给出了构造方法,比较没意思这里就不说了6TheSecretofSirRoastMcDuck(100)有一个k(k<=1600)次多项式q(x),最高次项系数=1,已知a[i]q(a[i])modp(1<=i<=k)。求常数直接套用日差值多项式即可7TheJourneyofBubbaDuck(200)有一 a[i]表示排在i前面的比i大的数有多少个。已知a[i],要求这题实际上就是一个贪心放置的过程,查询时可以使用一个类似于nnng-te的数据结构来进行优化,不过注意要写成非递归的形式,否则会超时。8 给一堆点(<=105像这种算法性非常强的题目,数据往往很不过既然是填表,那么有确定性的方法当然应该介绍一下。首先找到最低的一A,然后找一条不经过任何其他点的直线(设为直线1,并将存在某个角度上只有则记录每个角度上最邻两条直线上最高的与最低的点的连录与直线1的交点中与点A距离最近的直线,离点A最近的直线,但是却经过左边直线上的第三个点,那么左边的点与中间的直线上的下方的点一定距离点A更近9 一个棋盘上每个格操作可以对于朝上的棋子(x,y(n或者(a,y),并且b<y,这题的棋盘和向上的棋子数()有15之大,因此输出每个向上的棋子的必胜移动要做到(1的处理复杂度。SG函数值按定义求出来显然是不现实用笔列出一个小的表格,容易发现格子(x,y)SG值其实就是xXORy,这点也容易证明(可以通过下面的求解过程证明。因此可以O(n)的时间内得到当前局面SG(设为sum如果当前局面必胜的话,总共的获胜方案不超过n(x,y和(x,b,必然满足:sumXOR(xXORy)XOR(xXORb=sumXORy。当b<y时方案合法。同理可以求出另一类必胜方案(x,y)和(a,y)算法总复杂度为O(n) 循环最长递增子序列(15000能的最长递增子序列。输入为随机数本题和8有类似的地方,由于数据是随机给出的是一个O(n1.5logn)的概率算法。二分的方法做一个S(考虑反证法S必然包含最少一个链尾处的线性表中的元素。然后再用“平衡思想,分情况:若线性表中的元素小于05个,那么对于每一个元素,可以分别将该元素前后断开成链做一定包括这个元素的S,再扫描一次,求得长度不超过n的段(列)的S并更新答案。若线性表中的元素大于等于0(设为m)个,那么每个元素出现在答案中的概率就1/05正确解的概率1(m-)/))05,当=15000时,成功的概率只有70%。但是注意到线性表(不是由其他元素推出来的)不超过(2n05的Bitwise1A Mary-Jane2 有一些硬币i个不用要么至少用bi问组成S分钱少要多少硬币参考解法太慢……时间复杂度可以低一阶3Schedulingfor4 5 Vault(200)对于奇素数pordp(k)kemodp=1的最小有ordp(k)之和6 n*n01矩1(欧)。同POI的scarefrog7 给一个长度为n的小于L的连续子序有元素总和除以元解时左端点应尽量N<=231L<=n所有元素在[-100,100]间这个231中可以andm舍弃一些状态,但是读入怎么跳过呢?这么高深的方法当然要赶紧学习。谁料原来是题目的数据范围写错了,官方解答的复杂度是(nlogn的……这还不简单……二分答案然后扫用栈来,查询时使用二分。不过04年周源里那种O(n)的方法貌似8 使得它们的和恰好为S,且总价格尽量小。价格都不超过9PlayingwiththeDestinyreloaded7.这里是填写了WC后Ural比赛的所有题目USUalContestn架飞机的初始坐标以及它们的速出现两架飞机的距d的时刻以及这两架飞机的。d的时刻,然后利用这两架飞机的初始位置以及速度列一个关于t的二次方t后再更新答案即可。给出的规则将它规给出你下楼梯的速一个电梯的升降情n层大楼的顶楼到第一层所需的最短时给出一个4*4的矩1个否能在矩阵中找到使得格子上的字母对于每个单词,使用化搜索,分别记录这16个格Countryofk种限速标志,你要将这N个标志放得驶过该道路的人O(NlogN)。当然这题还可以直接O(NlogN)。Devil's已知X0=0,X1=1,计Xn的小数位中有6。X(1)j i是偶数的时候。设hi2,,1j 令Aj(4 ,SjAk,kX21S2 2 3 210a 3 ahlog52i是奇数的情况。答案为ailog2 给你N(<=50000)这道题多数人的想法是使用动态规划。首先将N个点按y坐标从大到小排序,然后定义L[i]表示端点为i且满足条件的拐弯次数最多的折线的拐弯数,并且该折线与点i相连的点在点i的右边;R[i]的定义类似容使用线,因此时间复杂度为O(NlogN)。其实这题还有一个很优美的解法。将N个点按yy且左拐与右拐交替已知两人刚开始的格高的人每次减价UralChampionshipm不妨count(i)1i中有多lucky如何计算count(i)。对于一个数m不妨定义n表示它的长度,那着重小于等于m并且长度为n的数里面有多少个luckynumbernumberdn+1-i,其中i≠n+1-LuckyTicketsd1d2…dn 到 之间b<=1018)有多少luckynumber不妨定义f[i][0]表示前i位等于d1d2…di并且符f[i][1]id1d2…dinluckynumberii<=(n+1)div2,则:i>(n+1)div2,则:若di>dn-i+1f[i][1]=f[i-1][1]*9+f[i-1][0]*(di-若di<=dn-i+1,则f[i][1]=f[i-1][1]*9+f[i-。最终长度为且小于等于m的luckynumber的个数为f[n][0]+f[n][1]。综合上述就可以在O(n)count(i)。n*m(n,1*2n
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年汽车后市场行业财务风险控制报告及发展趋势
- 2026年服装电商报告:数字化转型与消费者行为
- 2026年公寓租赁市场报告:趋势洞察与投资指南
- 2026年家居安防行业报告:疫情后时代安防产品市场需求分析
- 2026年互联网行业标准规范与市场准入研究报告
- 2026年大数据安全防护与合规建设报告
- 小学语文面试历年考题题库及参考答案
- 飞检中医病历指南2026
- 2026小学英语面试易错题全套题库解析
- 杭州西湖旅游介绍课件
- 2025年南宁铁路机考题库及答案
- 基于培养方案剖析牛津大学本科生培养模式及启示
- 统编版(2024)七年级上册语文期中复习:第1~3单元共3套单元测试卷汇编(含答案)
- 化工电仪安全培训课件
- Costco供应商行为准则审核指南-202301修订(中文)
- 文书档案数字化培训课件
- 核电厂管工基础知识培训课件
- 2025至2030中国汽车主动健康监测系统行业项目调研及市场前景预测评估报告
- 《法国电影》课件 - 欣赏法国电影艺术的魅力
- 《汽车底盘机械系统检测与修复》 学生实训工单9-制动系统结构拆装与检修实训
- 基坑松木桩加固方案
评论
0/150
提交评论