信息学-集训队作业contests

IOI2007中国国家集训队第二次作业 PartI-UVa Abednego'sGraphLovers'Contest,2006 ProblemA-Troublemakers【10982 ProblemB-Buyone,gettherestfree【10983 ProblemC-DoubleNP-hard【10984 ProblemD-Rings'n'Ropes【10985 ProblemE-Sending【10986 ProblemF-Antifloyd【10987 ProblemG-FromGtoHandback【10988 ProblemH-Bomb,DivideandConquer【10989 TheRealProgramers'Contest-2 ProblemA-MakePalindrome【10453 ProblemB-Trexpression【10454 ProblemC-GrayCode【10455 ProblemD-InligentCats【10456 ProblemE-MagicCar【10457 ProblemF-CricketRanking【10458 ProblemG-TheTreeRoot【10459 ProblemH-FindthePermutedString【10460 ProblemI-Difference【10461 ProblemJ-IsThereASecondWayLeft?【10462 ACMICPC2007WorldFinalsWarmup3 ProblemA-CircumTriangle【11186 ProblemB-WaterCrisis【11187 ProblemC-AStrangeOperaHouse【11188 ProblemD-ASimplePendulum【11189 ProblemE-SeriesofPowers【11190 ProblemF-Square【11191 ProblemG-GroupReverse【11192 ProblemH-Infinix【11193 ProblemI-StoneGrid【11194 PartII-Ural USUChampionship ProblemA-Coupons【1480 ProblemB-Winningchances【1481 ProblemC-Trianglegame【1482 ProblemD-Tablefootball【1483 ProblemE-Filmrating【1484 ProblemF-Footballandlie【1485 ProblemG-Equalsquares【1486 ProblemH-Chinesefootball【1487 ProblemI-ACMPoker【1488 USUJuniorContest ProblemA-Pointsonaparallelepiped【1489 ProblemB-FireCircle【1490 ProblemC-UnrealStory【1491 ProblemD-Vasya'sdad2【1492 ProblemE-OneStepfromHappiness【1493 ProblemF-Monobiliards【1494 ProblemG-One-two,one-two2【1495 ProblemH-Spammer【1496 ProblemI-Cuttingasquare【1497 ProblemJ-StrokeatFullSpeed【1498 ProblemK-Kerchiefs【1499 TimusTopCoders-Third ProblemA-FiscalOperations【1511 ProblemB-Zinium【1512 ProblemC-Lemontale【1513 ProblemD-Nationalpark【1514 ProblemE-Cashmaster【1515 ProblemF-Nostalgia【1516 ProblemG-Freedomofchoice【1517 ProblemH-Jediriddle3【1518 ProblemI-Formula1【1519 ProblemJ-Empirestrikesback【1520 ProblemK-Wargames2【1521 USU alContest ProblemA-LostinTranslation【1532 ProblemB-FatHobbits【1533 ProblemC-FootballinGondor【1534 ProblemD-TheHobbitorThereandBackAgain【1535 ProblemE-DelightsofPipe-weed【1536 ProblemF- 【1537 ProblemG-TowersofGuard【1538 ProblemH-InligenceData【1539 ProblemI-BatllefortheRing【1540 ProblemJ-Chase【1541 UralChampion ProblemA pletion【1542 ProblemB-DanceRevolution【1543 ProblemC-Classmates3【1544 ProblemD-Hieroglyphs【1545 ProblemE-JapaneseSorting【1546 ProblemF-PasswordSearch【1547 ProblemG-SakuraandStatistics【1548 ProblemH-AnotherJapanesePuzzle【1549 ProblemI-Dean'sPyramid3【1550 ProblemJ-SumoTournament【1551 PartIII-OI CroatiaOlympiadin Elite2007USOpenCompetition PartI-UVaAbednego'sGraphLovers'Contest,2006ProblemATroublemakers【109820.5，所以只要很少的次数就能得到合法解。ProblemBBuyonegettherestfree【10983有N个城市，每个城市都有一些选手要到城市N比赛。比赛的组织者可以者希望在d天内花最少的钱把所有选手送到比赛地。解答：二元组(x,y)表示第x天和第y个城市，x和y0-based。建立网络流模型把总共d*N+1个二元组看作网络的如果有飞机在第i天晚上从城市j出发飞往城市kc则从点(i,j)向(i+1,k)练一条容量为c、费用为该S，S向(0,jj=0..N-1j0。假设租用的Limit，则求一次从源点到(d,N-1)Limit的弧的最大流，如果S相邻的弧均满载，则费用Limit是可行的。只要二分答案即可求出ProblemCDoubleNP-hard【10984求一个无向图G(VE)的一个点集SS同时是Gk>0多有k个点在独立集中，而至少有k+1个点在覆盖集中。于是，有解的图可以划分为二分图，且不存在一种划分使得X部与Y部的大小不同。否则，最大独立集大小不小于max{|X||Y|}，最小覆盖集大小不超过min{|X|,|Y|}，不可能满足要求。有解的图存在完美匹配。=最小覆SN/2（N为偶数。于是，最大匹配数=最小覆盖集大小=N/2。在满足以上条件的情况下，显然二分图的X部和Y部均满足题目要求。小结：其实b)中后半部分的结论是包含在“存在完美匹配”里面的，可以作为一个剪枝条件；我做这题的思考过程大致就是从a~dProblemDRings'nRopes【10985O(n4)。注意到对于u,v,w,如果u,v是被拉紧的两点，w是被绷紧的绳子（边）的u,w”是没有必要枚举的。在计算拉紧两点后有多少边绷紧这个过程中,这样减少枚举量：当前计算(i,j),枚举到点k,满足G[i][k]+G[k][j]=G[i][j]，还要枚举一个点l,。G[k][l]=1,G[l][j]=G[i][j]-G[i][k]–1预处理的时候把每个点到其它点按不同距离分类,记录在dist[i][s]中。当枚举l的时候只需要枚举dist[j][G[i][j]-G[i][k]-1]中的点。。ProblemE Dijkstra解答：无解的情况就是可以更新最短路：G[i][j]+G[j][k]<G[i][j]。其余为有解的情况。对于两点i，j，如果不存在第三点k满足D[i][j]==D[i][k]+D[k][j]，则加入新建一条ijD[i][j]。ProblemGFromGtoHandback【10988LineGraph解答：所谓LineGraph，就是把一个简单图的每条边分别看作顶点，对原图LineGraph。本题就是给出一个图H，问是否存在一个图G，使得H是G的Line最直观的方法莫过于尝试一步一步地重建出G，如果重建成功，回答”yes”，否则”no”。分别对于H中的每个连通分量建图：一开始G中只有两个顶点HDFSBFSH中的顶点（G是连通的HxG中可在G中两个非相邻顶点u,v之间加入一条边，满足uvxHx仅连接一个已知顶点u，情况和1)类似，此外还要在G中新建一个HK31个拓扑关系不同的G满足要求。如下图所示。K3的两种情因为保证了G的连通，所以构造的过程最多只需要一次回溯，对于本题事实上，上述性质可以严格证明，而LineGraph的判定存性算法，有兴ProblemHBomb,DivideandConquer【10989GlobalMin-解答：存在O(N3)的算法，可以参考相关D,E,F考查的都是与最短路径有关的知识，属于整个比赛中较容易的题目。B在读懂题目以后也容易看到是分层图的网络流，算法容易想，但要无错地写出高效的程序相比前三题还是要难一点。A的随机算法很简洁，但要想到并敢写需要一定勇气和经验。C是一道我很喜欢的题目，一拿到题目可能会有很多想起来是很简洁的。GHH，我更喜欢G。在做G的时候，最好先在纸上画几个图，可以大大帮助自己熟悉TheRealProgramers'Contest-2解答：简单的二维动态规划：dp[i][j]表示最少添加多少个字符才能使S[i..j]O(1)dp[1][Len(S)]等价。如表达式1+2+3*4有下列两棵等价表达式树。运算优先级相同。在这种前提下，nf[i]。可以分析表达式，把每层的同级运算数目ai求出来，由乘法原理得ansf[ai]。f[i]

f[2]

f[i] f[j]*f[ijProblemCGrayCode【10455没能看懂题意ProblemD-InligentCats【10456给出n个点的凸多边形，每次询问输入多边形边界上（边上或点）的一个坐标。输入数据全为绝对值小于100的整数，要求用精确的分数来表示答案。解答：设输入点为A。先找到输入点逆时针方向上的第一个点，沿着这个点B，且其前一个点为C可以发现所求点必段上BC此时有用的点只有ABC了，于是把多边形划分化简成三角形划分。设所求直线把三角形划分成面积为x，y的两部分（xC点的那部分q，w（其中qC点的那部分sx+y＝s且x-y＝w-qxswqhO。那么h2

|BC

，h

2x|OC所以|OC|xswq，再由定比分点公式得到C|BC ProblemEMagicCar【10457ProblemFCricketRanking【10458求x1+x2+...+xk=N的非负整数解，每个xi有限制si<=xi<=ti。k<=7,ProblemGTheTreeRoot【10459（用于求解“上方子树DFS的顺序求出每个顶点到其“上方子树”DFS中任意一点，以其为根的树的高度等于它到uv的距离的较大者。ProblemHFindthePermutedString【10460给定一种字符串排列的一一对应的方法，求第K解答：ProblemIDifference【10461，不能同时做两个或以上的工作。对于一个工作想知道它可能的最早和最迟，(a->bbaX，X该完成时间为最早相反地把能做的工作都做完再开始做X那么就得到了XX做X于是对于一个询问只需要正向和反向各遍历一次可以得到答案。ProblemJIsThereASecondWayLeft?【10462ACMICPC2007WorldFinalsWarmup3在一个圆心在原点，半径为R的圆上有N个不同的点，求任意三个点组成解答：把每个三角形的面积看作三个以圆心为顶点的三角形的有向面积之O(N2)时间内求解。耗时（以分钟计算，任意两个城市之间不超过100分钟车程）有3辆卡车停靠在供应站，已知各个接收站的需求量（以卡车计算，不超过200车，问能否在规定时间（20小时）内完成任务并且所有卡车回到供应站。总站点数不超过20。31200。要求最重用dp[i][s1][s2]表示放完前is1，第二个背包重s2，那么第三个背包的重量是可以算出来的。容易写出状态转移，虽然ProblemCAStrangeOperaHouse【11188DalarnaProblemfrom解答：求出四边形的重心G，根据公式求出单摆的摆长，以绳长减去摆长的结果为半径、G为圆心作圆，与四边形的交点个数即为所求。ProblemESeriesofPowers【11190计算：，其中(0≤l≤h |l-h| ( 15000000)ddddddedddddddddd的格式输出xk转化成题目要求的格式：tlog10(x)*kxkpow(10.0,t1)*10(longlongt11如果两个数之积为完全平方数，则称他们为doublepair；如果三个数之积为完全平方数，则称他们为triplepair。给定N(<=200000)个数，求出当中duoblepair和triplepair30，解答：由于最大质因数不超过30可以对每个数分解质因数，用二进制质因数的二进制表示的异或值是否为零具有相同质因数二进制表示的数，解答：动态规划。dp[i][j]ij个数之间组成的表达式的ProblemIStoneGrid【1119420×2010001p→1→0p122。上述方法转移1块石头称这样的对顶格子是连通的，连通的对顶格子组成一个区域，每个区域内任意两个格子之间可以实现石头的“转移，根。，要求最终石头数量是不增的。更进一步地，对于多个相邻的区域转移（奇区域间的转移用偶区域作中转。30”这个条件的暗示性很强，容易想到算法。D点。AE的优化都是常见的技巧，应该掌握并灵活运用。B一开始以为是图方法。I是很有想头的题目，关键是看到石子的转移方法（这个策略也算比较经PartII-UralUSUChampionship在一个n×n1到n×n，求使相邻格子的差的最即在满足该格子与上方格&左方格的差满足条件的前提下每次放入的数尽可能大。若能不重不漏地方满整个矩阵，则方案可行。ProblemBWinningchances【1481考虑把n个（1≤N≤50）砝码依次放入天平（开始时天平两边均空，每次放完后记录天平的平衡情况，即往哪边偏（不会出现平衡的情况。给出nm，把砝码从小到a指向数组n-m的位置；b指向数组n-m+1的位置。每次向的砝码并把a向左移一位，加入砝码时尽量往总质量轻的那边放。ProblemCTrianglegame【148211解答：枚举6中顶点对应方案进行判断。平移的情况很简单，来看旋转的情况。对对应重合顶点个数进行：2个顶点重合的，意味着肯定来看无对应顶点重合的情况。对于两个点A和A’，要从A旋转到A’，绕行的中心点必定段AA’的中垂线上，而另外两对顶点中必定存在一对的中垂线与ProblemDTablefootball【1483n该是相同的。又因为n个队总分最小值为(n-1)*n；最大值为(n-1)*n/2*3。所以第一名至少得n-1分，最后一名至多得(n-1)/2*3分。ProblemEFilmrating【1484已知n个数的平均数为x（其中每个数都是110，问至少要在这n个数中再加入多少个数才能使他们平均数不超过y。长度可能很大，要用int64。ProblemFFootballandlie【1485该场比赛中得到分；0表示他在该场比赛中没得分；－1表示他没该场比赛解答由的比赛情况可以得出之间的关系构成一个ProblemGEqualsquares【1486给一个n×m的字母矩阵（1≤N,M≤500，要求在大矩阵找到边hashhashhashhash函数时为了减小时间复杂度，要用到ProblemHChinesefootball【14871000q50000每次询问输入两个点a&b，判断是否存在点x是x同时能到达a和b。解答对有向图做一次floyd求出两两点间的连通关系后每次询问只要O(n)O(n3)floyd81个byte来做，这样相当于只有[n/8]个点，O(n3)也能接受。ProblemIACMPoker【1488给出一种3张牌比较大小的，已知两个人，其中一个有3张牌3I是道阅读题，仔细看清楚规则应该没什么问题。F2SAT，背景倒是挺有趣的。H是出得很好的一题有基于布尔压缩的算法，也可以用基于dfs的离线算法，很有启发性。B题是直接的构造，非常巧妙。G的思路比较简单，但实现起来还是需要一定的功夫。C是基本的几何题，细心分析不难出解。USUJuniorContestProblemAPointsonaparallelepiped【1489把长宽高分别为a、b、c的长方体的展开图方在平面直角坐标系中，已知求点再空间对应的坐标时只要分情况即可。ProblemBFireCircle【1490在网格状平面内一交点放置一个半径为r100000的整数，可以枚举所有行，再分别统ProblemCUnrealStory【1491有一个na个数到第b个数加分别c，完成所需要询问，可得到更简便的算法。考虑数组c[i]，设最后第i个的答案为c[i]ic[a]cc[b+1]c果第a个数到第b个数的前i项和都增加了于是只有统计更新数组c[i]，再输出每一项的前i项和即可。ProblemDVasya'sdad2【1492f(x),其中折点为在区间[−15000,15000 f1(x)和偶函 f2(x),使得对于定义域内的全体实 满f(x)f1(xf2(x解答：由于折点为整点且范围不大，可以考虑把f(x)离散化成整点个整点令

f1(x)

f(xf(x)2

f2(x)

f(x)f(x)

，可以证明f(x)

f1(x)f2(x)；f1(x)

f1(xf2(x)f2(x用int64。ProblemEOneStepfromHappiness【14936luckynumber，若一个数是luckynumber633ProblemFMonobiliards【14941,2,3,4…N。输入n桟ProblemGOne-twoone-two2【1495输入n，12nbfs1，20则输出方案。ProblemHSpammer【1496输入n1ProblemICuttingasquare【1497输入一个n×n01（3N≤10000判断0的连通能否通过平移（不与1的格子碰撞）拉出矩阵。解答：若0的连通分块从上方拉出，分别判断每个0格子能否拉出，其充要条件是格子上部不为1。同理可退出其他四边的情况，分别判断。时间复杂度ProblemJStrokeatFullSpeed【1498在n*m的棋盘内，位置(x1,y1)上有一骑士，位置(x2,y2)上有一。骑士解答：考虑骑士的路线可分为3段，先向4个方向中的任一个走一段，再走到与（或同列，最后再走到旁边，进行。于是只有枚举第一不能穿过。ProblemKKerchiefs【1499nm条边已经被切割，求当前情况下的一种合法n1向其他点各连一条线即可。a<bab边形划分的子问题，所以先处理跨度小的已切Junior的比赛，明显必其他比赛的要简单得多。BEFH都是几行就能出解的题目，相比之下，ACEGIJ虽然也思路也比较直观，但代码不如上几题那么简单。值得一提的是J，做这类的题目一定要经过充分思考再动手，否则可能因为一时疏忽，被卡，从而影响心态。C是道比较好的题目，在比赛时由于没花D是比赛AC的人。总的来说，虽然这次比赛题目较简单，但要在短时间内完成的话还TimusTopCoders-Third给出A，B，C三个数，改变一个数字的费用为原数字与新数字的绝对值之差。要求不能增减位数，也不能有前导零，问使得A+B=C或宣布无解。每个数不超过101000。解答：容易想到从低位到尝试各种数字组合，记录进位情况，用一个2*Len的数组把搜索化。本题的trick主要在于对长度不一致以及前导零的ProblemBZinium【1512要求程序给出一个N解答：NProblemCLemontale【1513给定一个有N个L(Lemon)的字符串，要求把一些L修改为BBanana)，使得不存在连续K个L。(1≤N≤10000)andK(0≤K≤N)。解答：f[i]表示已经修改好前i-1位，并且第i位改为Bf[i]

f[特别地，f[0]1,Ansf[N+1]。然后用将f[i]用s[i]替换：

jki容易写出s[i]

s[i]f[j

此外，本题还需要使用高精度计算，每个int8ProblemDNationalpark【1514在大小不超过50000的点集中求三个点，使得它们围成的三角形的周长最ProblemECashmaster【1515max若p>max+1，则答案为max+1，否则max=max+p，考虑下一个砝码。ProblemFNostalgia【1516在一个8×8的棋盘上有黑白两方跳棋棋子。跳棋的规则是这样的：跳棋的现在白方（W表示）希望通过——取走棋盘上尽量上的棋子（双方均可，然后用一步棋把黑方（B表示）在棋盘上的所有棋子。。分成4类分别尝试某类棋子，其余种类的棋子包括本类在棋盘四周的棋子都只能通过的方式拿走。容易发现，对于一个黑方棋子，只有两种被吃。，ProblemGFreedomofchoice【1517求两个串的最长公共子串（要求连续解答：方法非常多，后缀树、后缀数组、HashProblemHJediriddle3【1518计算给出一个NProblemIFormula1【1519在一个最大12×12的网格中有些格子是，有些为空地，要求设计一条想法：状态压缩dp12ProblemJEmpirestrikesback【1520给出一个大圆和多个在圆内的点，求最小的半径r使得以每个点为圆心，想法：求出每个点对应的voronoi多边形，求该点到多边形在圆分的最交以及点到圆弧的最小值这几个routineO(N3)。ProblemKWargames2【1521解答：静态BST可以直接套算法；E要做好必须跳出思维定势；F是一道很有趣的题目（读题要保持题目的趣味（8×8？）dp的程序通过的缘故吧。剩下的没有USU alContest过2次操作可以变成这n个字符串的另一个字符串，则把这两个字符串加入到AC2是退出扫描。此方法虽然系数比较大，但时间效率还是比较可观的。Way2：x2y，相ProblemBFatHobbits【1533解答：为了更直观地表示顶点的关系，先用floyd算法求出任意两个顶（点）数等于题目所求点集的大小。不可达，则需要的路径才能覆盖图中所有顶点，。2个顶点，组成的点集中顶点互不可达。方法：假设有M条路径，P1，P2，…，，每次检查一条路径的末端顶点，将它能够到达的顶点删除。这样会导致某些路径的末端顶点改变，但不会改变路径总数。重复以上过程直至没有新的顶点被删除为止。容易知道，每条路径都不会被完全删除，否则必然存在，法合并原路径集合中的两条路径，得到更少的路径覆盖数。然后，，，的结果也可以轻松得出原图的最小路径覆盖方案。有了这个方案利用引理，ProblemCFootballinGondor【1534一支足球队在nKL3011ProblemDTheHobbitorThereandBackAgain【1535从城市X到城市Y花费为X×Y1开始遍历n1（1。问最大最小花费分别是多n－i＋1n+1，且相邻两对的顺序调换。最小的方案是…7,5,3,1,2,4,6…1放在第一位。ProblemEDelightsofPipe-weed【1536立。数字和运算符总共可能有100个。ProblemFEnts【153722右儿子的权值是父节点的权值加1。输入n，问权值是n的节点共有多少个。if[i]i的节点必有一个权2i和一个权值为i＋1的节点。反过来，一个权值为i的节点，若其为奇数，他只能由i－1“演变”而得；若其为偶数，他可能由i/2或i－1“演变”而得。于是得到递推公式：f[i]=f[i-1](i为奇数)；f[i]=f[i/2]+f[i-1](i为偶数)。本题值得注意的地方是取模数p1。ProblemGTowersofGuard【1538在n（5≤N≤50005按逆时针方向顺序输出这5个点。95995ProblemH ligenceData【1539nmxxnnProblemIBatllefortheRing【1540有k（1≤K≤50）100个数。两个人轮流对这k解答：论。用g函数求出每个数列的nm_um，并记录第一步取第个数列的第j个数后的nim_umnim_um用xor函数联02步的nim_um0的走法就为答案。ProblemJChase【1541输入n、m，1≤M,N≤50M/N≤3M/NF，是一题有趣的递推，但读题也需要一定时间。C也需要一定的思考，可能对于热衷于足球的人会有某种优势吧。D的规律要一眼看出来并不容易，可能只能写个搜索找找规律了。相比之下我反而觉得H的难度更小，简单的思路和不太复至今也没什么人做。G9个点的人应该并不多，更容易想的可能是随机化，如果敢于尝试的话肯定能碰上。I题是论，写的时A，通过两种截然不同的思路均能到达目的地。B的描述和构造都并不华丽，难度却比较足，需要一定的思考和尝试。说这次比赛涉及的知识面比较广，且没什么的数据，有利于和提高选手UralChampion n(1≤N≤100000M(1≤M≤中出现次数最多的10个，若相同用字母序来比较。最后按字母序输出。trie，trie10个关键字，分别对应该节点的10个答案。建树与读入同时进行，每次读入时按顺序遍历trie，每经过一个节点就尝试把该点trie。每次询问按照所给的字符串遍历trie，并输出最后10个关键字。ProblemBDanceRevolution【1543解答：读懂题目后这题并不难。把每一个beat-period离散化，再按玩家的顺序依次统计每个beat-period的得分情况。最后进行综合。ProblemCClassmates3【1544有N1≤N≤50枚举被选中的电脑，再不断用dfs找连通块模拟其操作，直到到达终态为止。选ProblemDHieroglyphs【1545输入nProblemEJapaneseSorting【1546输入n面。若仍分不出先后，则比较数字的开头的0100KBProblemFPasswordSearch【1547为找到一个不大于n位的，准备用m台电脑同时逐一测试。26若不能平均分配，则靠前的若干电脑多分配一个。输入n，m。对于每NN解答：先算出password的总数，为26ix个字符串时，从到低位，每次尝试放入最大的不超出范围的字符串，把n位放满后便得出答案。ProblemGSakuraandStatistics【1548输入一个n×m(1≤N,M≤5001中的1元素，其中每个矩形只能覆盖1元素不能覆盖0元素。解答：称被覆盖的1格子为已盖格,其余的1格子为未盖格.称一个矩形为极大矩形当且仅当它是合法矩形（0格子）且四周不能继续向外扩，符合的定义了，需要把它们收缩——例如发现某个矩形的最左边一列盖，还要把这样的矩形剔除出集合，并修改相应的格子的度数。，虽然用以上算法编写的程序通过了的测试数据，但如何证明每步都存在一个度为1的矩形本人还不能严格的证明。欢迎有的同学与我联系。ProblemHAnotherJapanesePuzzle【1549ST（0≤ST≤1000，解答：先考虑无解的情况，显然最小的圈由4个弯的拼图构成，所以若T<4，4个弯，那么更大的是否能在此基础上进行扩展呢？答案是肯定的。每次扩展可以往4条边上组合增直拼图分别为偶数。且每次加入的组合有以下几种，意思是每次能同时加入x个直的和y个弯的使其仍保持圈的形态。直222200弯024682个弯的情况不能再继续扩展，且仅有这种情况不能得到扩展。因（0，12（0，8ProblemIDean'sPyramid3【1550的任务是求四棱锥的体积减去四棱锥与集的体积其实就是以OA为高的圆柱体的体只要通过比例求出OA，用四棱锥的体积减去OA为ProblemJSumoTournament【1551有2n支队参加淘汰赛，每个队分别来自各个城市，输入n和各个队伍来自解答：显然答案只与来自同一城市数目最多的队伍有关。因为x个来自同一x－1个来自另一城市的队伍也不相遇。设最大的来自同一城市的队伍数目为M那么M≤2。类比可得可见要使其在倒数第i轮才相遇，那么M≤2i。反过来，有M个队，那么他可以在倒数第log2M轮相遇，所以答案即为n－log2M。A题比较灵活，既可以用trie做也可以用线段树完成，相比之下trie更容易实现，线段数效率更高。B是阅读题，仔细读题后无大妨。C的思路比较巧，但若找到了突破口，程序很容易实现。D是简单题。E的排序规律并不难找，但有很多细节要照顾，这使得此题通过率非常低，比赛时也卡倒了一批人。F是比较经典的题目，此题另一个考点是用到了各种高精度运算。G需要大胆思考和严密的思维相比之下难度比较大H是一道非常有趣的题目需要观察和构造能力。I是基本的几何题，难度不大。J题另一道比较简单的题目，思路也比较显然。完成这份题目需要一定的创造能力和严谨的思维，既要谨慎又要大胆创新， PartIII-OICroatiaOlympiadinstandardstandardtimememoryN(1<=N<=500000)个人在排队等候进入音乐会现场。人们有点不耐烦，两个站在队伍中的人A和B，他们能够相互看到对方，当且仅当他们相邻或者他们之间不存在一个人比A高或比B高。人互相看到。本题的N可能高达五十万，须使用批量统计的方法。一个栈S，栈中元素是身高值，满足S1S2Stop。每次读入一个新的身高x，栈中小于x的元素出栈，显然这些元素与x都是相互可见的。然i，Si+1…Stop都与x由于每个元素入栈一次，出栈最多一次，而寻找位置i的时候借助一个辅助数组（记录栈中高度相等的元素的范围）可以做到O(1)，所以总的时间复O(N)，能够满足题目的时限要求。<1ab,cd>：删除一条边<c,d>，问a和ba,b<2ab,cc，