信息学-集训队作业mipt.all

MIPTSolutionByMoony本解题报告是我在参考了前几届国家集训队选手的报告后，在许多大牛的帮助下写的（在这里特别感谢刘汝佳前辈有内容可能会和他人的相似但我相信站在巨人们的肩膀上能看得更远本题解不但对很多前辈报告能让你或多或少学到一些东西。本题解中有不少不明显的link，大家。S+Sumof不需要高精度的A+B问一道有一定难度的A+B问题Autumnisa+Maxof求n大家可以研究一下求n个数的第k大值的各种算法Θ(netc.）+Set求两个集合A与B排序+扫+Contest给定一张有向图，对于两个不同结点i和j，边(i,j)和边(j,i)存在且仅存在一Hamilton链。SWC(SearchWithoutClothingcanbealsocalledNude否则必然存在一个在当前链L上的点Li，使得边(Li和(this,Li+1)+每个物品有2个值mi与si，如果有si<sj则mi<mj每个物品i，它前面物品的m的和不超过它自己的si，即∑j<imjsi，则称这给出n个物品，求最多可以取出其中几（n≤100000，mi,当年题目中的nO(n2)的动态规划算法AC，后来ELJudge改了数据，就只能用贪心了。一道类似的贪心题：CTSC2007pendant+descendingatree叶结点 W。求∑W*(1)Di， 中Di表示i的深度+Three0至n3个非负整数枚举可以AC，复杂度是O(√n3)当然，你也可以把这道题想象成求生成函数+x4+x9+x16+x25+…)3展开后x0x1,…,xn中系数为0的项的+Space求n*m*d此类矩阵问题大都需要先预处理一个sumsum[a][b][c]表示∑i≤a,j≤b,k≤cmati,j,k，这样，在后面的运算复杂度是O(n5)+栈（只用记+Fibonacci求Fibonacci数列第n项学习用矩阵乘法O(logn)求Fibonacci数列第n项的算（很多递推都可以用矩阵乘法加速）+NewYear求二分图G(X,Y,E)的最大匹配匈牙利算法直接AC学习最优匹配的KMUSACO2004MarchGreen有另一道很BTMooUniversityEmergencyPizzaOrder，直接用匈牙利算法+Brackets法，不同种括号不能交叉。栈+Correct相当于给定一个有向图G，判断是否是一个DAG。（|G|<=1000略+有n个有序三元组(xi,yi,zi)，有xi≤xi≥xj,yi≥yj,zi≥zj。求最小链覆盖这道题就是对于给定的二元组(x1y1x2y2xnM1:(x11,y11),(x12,y12),…,(x1m,M2:(x21,y21),(x22,y22),…,(x2m,…Mk:(xk1,yk1),(xk2,yk2),…,(xkm,对于任意的i,j,p(p>1)都 且yij≤yij，并且使- p- 尽量小（即最小分割O(nlogn)O(nlogn)的LIS得解。回到Boxes，却无法用O(nlogn)的方法解决。其实有一O(n2)。O(n2)更快的算法呢？刘汝佳前辈坚定地告诉有！2003TCODivisionI,LevelThreeNestable就是这个问题的加强版（题意略有改动，盒子i可以包含j当且仅当xi>xjyi>yj,zi>zj，求的直接是盒子套盒子能组成的最长链），N高达用动态规划f[j]=max{f[i]+1|i<j且box[i]可被box[j]包要取得更快的算法需要用平衡树等高级数据结构来加速。逐个按照xi递增的顺序考虑盒子，在运算过程中需要一些集合T[]T[i]这个集合内的元素都满足：以其为最下标最大的非空集合T[i]，那么i就是所求答案。当考虑到某个盒子B的时候，可以使用二分查找，找出存在可被k包含盒子的所有集合（一定是从开头开始连续的）的最后一个集合T[i]，并在T[i+1]中B。但是有一个很严重的问题——如何快速判断一个集合中是否存在可以被B包含的盒由于一个集合中的所有盒子都不互相包含，所以当它们按照优先yzyz是不增的。那么在这样的集合中，只用在O(lon的时间内找到第一个z小于Bzy是由也小于By就可以知道是否存在了。当然，这一切顺序都要在的时候。分析到这里，得到了理论复杂度很好的算法2能取得很好的效果。+给定K求一个长度为N的句子，使其包含的所大小为M。最后的答案可以通过DP得出：以串的长度为阶段，为了保证表示长为Ns结尾的所有满足要求的字符串中最大值得注意的是s的取值，如果以一切字符串为取值范围，显然复杂度太高了。但可以只动态规划中的“当前串”中的于是s的取值范围即为所有模式串的所有前缀组成的集合。，，，，枚举一个字符集中的字符c加在ss’s+c，并求出新的s”s”s’s”s”c]完成。然后就可以得到通过opt(N,s)扩展到opt(N+1,s”)的恐惧值：为opt(N,s)+weight(s”)weight(s”)表示所有是s”后缀的模式串的恐惧值总和。weight(s”)数组也可以总数*字符集总数=N*K*模式串长*M可以将将长度超过N的单词在一开始就删除，于是模式串最长为N，所以动态规划的时间复杂度是O(N2MK)的。但仍一个问题是如何高效的求出next数组和weight和O(N2K2)的（不考虑字符串比较时间，否则还要乘一个N因度。更高效的算法是建立一个自（可以参见Maigo2006集训队《Trie图的构建、活用与改进》），在O(NMK)的时间内得到next和weight数组；或用KMP算法在O(NK2)+One在[0100]*[0,100]的矩形内找一个n个给定点都不在矩形内（可以在边WC2002奶牛浴场也和此题一样，是求最大空心子矩形。做这类问题有两种不同的方法，它们的复杂度分别是O(LW)和O(n2)O(LW)USACOARectangularBarn的解题报告。根据这道题的数据规模，显然O(n2)的方法更优它的四边都不能再扩展。将所有的点按照x坐标从左到右排序，对于每个点ii，而右边紧贴某个在i右侧的点j的极大矩形（设updown记录矩形的上下边，在枚举j的时候可以up和down），更新最优解。另外+Two在[0,Mx]*[0,My]的矩形内找二个面积和最大的平行坐标轴的矩形，使得n（n≤100，Mx,015Onerectangle所解决的问题。总时间复杂度为O(n3)解法二：（周源前辈的题解若要求一个指定的有点的矩形中的最大空矩形。首先枚N加入点，相当于在一个垂直的区间中加入一个点，但顺序这些区间，即使采用线段树，每次复杂度也O(log2N)的，而且算法可能至每次操作O(N)。但反向作就不存在这些问题了：先将所有点从上到下建一双链，然后从右到左依次删去点并双链，而每次只得到一个新的更大的区间，因此只需要一个最大值即可这样用O(N2)的时间算出了任意从左到右某个区间中最后，最朴素的方法也能在O(N)的时间内得到最优解同理水平分界线的情况最后算法的时间复杂度为O(N2)，空间上稍微大一些，也需O(N2)，但应该可以用一些数据结构降低这个级别给出N行command这是MIPT多道表达式处理题中的一道，如果你将所有这些definition或者identifier，下面做完了，那么在表达式处理方面你就成仙得道了Alpha::=a-zA-如果得到的command是definition，那么将其identifiernumeric::=0-expression剥离并记录。如果command是identifiercommand::=identifier|definit计算其记录expression的值并输出，同时判断是否errordefinition::=identifier':='+Arithmeticaidentifier::=alpha最关键的部分是需要多次调用的计算expression的值。当expression::='('expresson')'偷懒的方法是O(n2)的递归，每次找出优先级最低的运算符integer_number|identifier|expression('+'表达式分离成两部分然后递归计算O(n)的表达式处理'*'|'-')一次处理expression每个元素，如果是数值（或已知数值integer_number::='-'?符号）如果一行command是identifier，栈的尾元素计算（将数值栈尾两个数和为一个），处理，括号的优先级也要设定，具体的实现可以参（N<100，command都不超过个字符有的同学可以去看看表达式树的理论+Whatisthe0小于1，你可以询问“这个数是否小于r”。给出N，问情况下，最少要问2~N数的个数你可以枚举+来求，最好的方法是2~N每个数的欧拉函数的和（不懂欧拉函数？请用Baidu和思093Whatisthenumber(Part+给出一个N*N的棋盘（N为奇数），以获胜则输出1；如果当前一方无论如+Islandofstraight在平面上，给定n树，树边一定是直线段，且不能穿过给定的m条线段。（n,爱的voronoi和DT~~+（+expressionI给定一个文本串A，一个含*的（但不中*，使得A=B。（|A||B|1000，答案保证不超过用F[i,j]表示A[1..i]匹配B[1..j]的方案数，下面是递推F[i-1,j]+F[i,j-1]F[i,j]{F[i-1,j-1]0+Wayamong给出一些线段和两个点AB，判断是“房间”，如果两个房间不同，则输出NO，否则输出YES，判判断A是否能到B。苦思冥想出来的错算法（截至200712月尚可以AC），请在RP充足的情况下使用：建立这样一张图——顶点是A和B以及各线段顶点，边是图上能从AB的路径那么曲线存在。很明显此算法本题与Sgu的一道GtOut很相似，可以首先将所有的交点和顶点列出来，接着将直接有边相连的点之间连一条边，在这（fstree上添加边的办法，依次检查ABYES。此算法可能是最好实现的正确算法，只4)。1.枚举图中所有圈是的复杂度是阶乘级别的（情况是完全图——圈数是N!）。利用DFSTree得到的圈是DFSTree（u是v的祖先v是w的祖先Root…-u-a-v-b-(v,bwv)，(uav,bwu)。少了一个圈：(u,a,v,w,u)，发现是上面两个圈的一个/---\/---|A|B\---/\---点即不在A,也不在B，必然就不在A,B的内。所以DFSTree。。如何快速判断点是否在多边形内(上)。判断Q是否在多边对于满足Min(Pi.x,P(i+1).x)≤Q.x<Max(Pi.x,P(i+1).x)的边(Pi,P(i1))。若Det(Pi,P(i+1),Q)>0Count++;若Det(Pi,P(i+1),Q)<0Count--。若|Count|=2，则Q在多边形内；若|Count|0，则Q即以Q做x垂线它与多边形的所有交点所在的边，相临交点所对应的边的方向一定不同。利用边方向交错的性质，就可以找到Q判断，所以在DFSTee中可以用部分和的方法，存下当前点到根的路径上的统计信息。找到圈就可以O(判断了。+Arithmetica对于含+-*()的运算表达式求值又是一道表达式处理017+Theoptimal在平面上在给定线段PQ上行走的速5求从A到终点B用的最少时应用Fermat光行最速原理，路就可以了。有两种走法直接从A到B从A到达PQ，然后在上PQB两侧；入射角的正弦和折射角的正弦成正比n。而n又等于入射光线所在介质的光速v1除以折射光线所在介质的光速v2目中已给出速度，可以看作光路从某垂直于PQ的垂足处+i=i-若i是偶数用最少的步数使得i=0。开始时，i=可以递推，或者贪心：i2，当imod4=1i3时减1，剩下的加1将i01的串相间。来看末尾的一块，若这块为02串长度减少1，而对0串的加减操作对前面的1串不会有正面影当末尾为1串时， 1。。(1串长+1)位）；若此时选择减1操作更优，那么会一1行一次减操作，总次数为(2*串长-1)，再考虑较之加1操作略。当然了特殊情况3，此时要减1，因为加1并没有1多消除一位。+Odd有n的正整数，其中只有一个值重复 将所有数XOR起来，就得到了答案。+Circle给定K，有2K个人围成圈，从1号开始每次杀掉第M个人使得杀掉的前K3const+Stormina给定一个国家的N*M的矩形地图，其2*2的格子不可能属于4个省份任意一个“田”中4个格子不能分属4个省份。初看似乎没什么因此可以把这些省份缩成一个点S，添加一个源点T与所有的边界省份相连，问题转化为求S到T的最短路。答案即为最短+Disclosingof024+Minimalsumof因为所有点的坐标在-15到15并且所求的解要求保留小数0.130020.001求使得z=∑nfi*d(x,y,xi,y达到最小的点(x,y) ））d(x,y,ab)表示在平面上(x,y)到(a,b)0观察zz的形状总是向最低点塌陷的。于是可以设当前解为P(x,y)，以一个步长len，走到一个随机点Q（满足|PQ|=len）。若Q的值比PQ取代P若干次在该步长下都没有较优解，则len=len/2len小+StarWar(epizode给定平面上N个圆，求一条直线最多穿因此可以穷举任意两个圆，对其公切线进行检查（只用检查外公切线，因为假设可以通过某两个圆的内公切线得到毁。此算法时间复杂度为O(n3)，空间复杂度为O(n)至于求公切线的方法多种多样，用计算几何的方法+次相连可以组成N2个角形。在任意一对角形之间存在已知的不等根据已知的大小关系建立一个有向图A<B则连一条有向1至N2，由于这题中，边的个数是O(N2)级的，因此拓扑排序的时间杂度可以优化至O(N2)+给出底部），告诉你下雨的雨量H 中的O(N)算法：，，，，求积水的深度最大可能值10000）解法三：（郭华阳对于每个点p，向左找出第一个比它高的点L[p]以及右边第一个比它高的点R[p]；记录显然L[p]~R[p]可能形成一个pond，记录这pond为容易证明，extended[p]和所有可能的pond是一一对应记录LT[p]为(L[pp)中最高的点，显然，(L[pp)是一个可能的pond，并且等于extended(LT[p])；同样的有结构完美的反应了所有pond之间的关系；接下来，……我用的是最后法。得到二叉树结构后，从上往下递具体实现的时候有很多trick（可以参见程序），写得好的O(N)。+经典的Camelot问题：有一个国王和M个骑士被放置在一个N*N的棋盘上USACOTrainingGate也有这道题，不过数据没这道题大。优化，网上有很多题解，USACO上也有，如果实现不好的同+Two完全就是体力活24种旋转，或者Const出来旋+um给出N种物品(PiMiQi)，PM是质量，Q是物品最多可取个数直接背包的复杂度是O(NBQ)的，可以通过此题。此题还可，，的质量总和在[A,B]内且利润最大，如果无法取出[A,B]内的质量，输出-1设状态是opt[i][j]表示前i种物品质量总和为j时的最大opt[i]jmodMi分类的和opt[i][jb]，若有opt[i][ja]+(jb-ja)/Mi*Pi≤opt[i][jb]（ja<jb），那么明显ja是不会对jb之后的状态作出贡献的，因而可以将之从队列中删除。在j增大的同时根据Qi删除队首元O(NB)+Rootsof1。（设方程为f(x)=0，其中f(x)=aNxN+aN-1xN-1+…+a1x+a0。那么可以设aN=1（简单的变换可以得到）。新构造一个矩阵Aij（1≤ij≤N），1(i-Aij{-ai(j=N)那么显然方程f(x)=0的根就是A矩阵的特征值，于是问题可以转化为问A1。这也就等价于问AN0+CalculatingXORviaAND位数后存在AND操作（返回n位数）设该操作为ANDn(A)，同理可定义给定n，求满足m<n的条件下，最大的m值，并满足：存在一个g1，将2m位数为m位数，并且对于XORm(A)操作，有2m个不同返回值，每个返回值有个与之对应的自变量A。对于ANDn(A)操作，虽然有2n个nnin），求一个m（m<n）2mm设k3k≥2m那么有Ck+Ck+1+⋯ ≥ +Murderofmister图），Mr.S在其中的一个点上（Mr.B位移动到相邻的点。Mr.B每个时间单位轰炸一个顶点，问Mr.B能不能确保存在一个一定将Mr.S炸死的方案。（么每次你能消除一个1，而下次只要与1相邻（本身不算），目 打掉一个点 ，， 1的数目无限扩充，10|0-0-0-0-0-0-0-2的分叉：1-0-1-1-（消除0-1-1-1-（消除1-0-1-1-0-1-0-1-如果多个分叉，那么如法制，把所有的分叉奇偶分家3，无法做到了。如果一块相连区域没有奇数偶分家，那么这区域只有一次的空闲，如果两次空闲，那么1又会两块没有奇偶分家的块，除非像长度小于2的分叉，通过一步之相连时，Mr.S可以ESC。Rubik'sCube2××2*2*2啊哈，近段时间看了哈玩Cube的专业选手，居然蒙着眼睛都orz，简直就是个计算机。+LCS（经典DP有的同学可以想想当序列只有0和1的时候怎么优化+将区间按照左端点排序后DP，复杂度为O(NlogN)此类问题在区间范围较小时直接以坐标为下标DP编写起来方+Frame给出X*YX*Y的矩形架。给出N个询问：是否可以用A*1（3≤X,Y,+Picture给定一个X*Y的BMP格式的文件，（X,Y<1025很好玩的题，可以学习BMP直接将给出的BMPfloodfillOKBest个集合，对集合S，若|S|=k，那么定义这个集合的D距离的平方和除以k。进行恰当的分组使得D值总和尽可能OAC……偶菜飘过。题目描述和评测标准……NP问3（否则可以分成两部分而D值和更小），还有点在一条直线+12233444555开头的数列f(i)，其中每个数字x重复f(x)次。已知n，求f(n)。答案和√n同阶，可以先求出i=1到106（其实只用到673365）的f(i)值，得出每个数出现的次数，然后在O(√n)的时间内判断第n个数f(n)是多少——相当于求最小的i使得f(1)+f(2)+f(i)≥N，当然，这一步还可以改进成求最小i1*f(1)+2*f(2)+i*f(i)≥N+Chessend-264*64王固定c3不能移动，白方会用最在得到状态后，用何顺序计算各所需状态的最长拖延值，是个很让人困扰的问题。开始的时候我曾尝试用化搜索，但是对于边界以及棋局出现环的处理我一直没有想出来好的解决方如果前继是黑方走，那么仅当该前继的所有子状态都被扩（，注意这里要处理和不算赢的情况。不少博弈问题和最大最小思想有关，如min-max过程及其alpha-beta剪枝，题目：EastCentralNorthAmerica1999ProblemA.TriangleWar。+numberofsteps币），你还可以用k*100个硬币跳过接下来的k步，但是第一步和最后一步最直接的做法是O(N2)DPopt(i,j)表示前i个手续，只办理了jopt(ij)=max(opt(i-1,j)-100,opt(i-1,j-1)+第i步硬币得失数量)，而不可能达到O(N)方法+Tworegular给定两个含"?*"的正则表达式R1和R2S能被R1、R2同时（|用opt(i,j)表示同时满足R1[1..i]与R2[1..j]的最短字符串长度。状态转移时可直接由opt(i,j-1)opt(i-1,j)得出opt(i,O(N2)+Strange +按顺势针顺序给出一个1至N的全排列直接搜索，时限对于10!=3628800来说很宽裕同学可以参见2008集训队。+Love给出有向图G，求没有弦的最长圈搜索……Searchingwithunderwear+Mine给定M个的坐标，以及点A和B。求RA到B，其上所有点离的距离均超过100000的实数可以先通过二分法枚举R，将所有距离小于等于2R的相023Wayamongsticks的算法了。但需要说明的是，本题有另外法，就是对这个图建立一个VoronoiDijkstra算法，就可以得到两个圆的最大半径了，时间复杂度约为O(Mlog2M)。一个二分或增量算法求R，等价变换后如下：求出MT（其实平面最小生成树就可以拿Voronoi搞），从小到大枚举不在树上的边(i,j)，判断这条边和T中路径(i,j)构成的通路是否分离了AB。时间复杂度：+Trip给定平面上N个点，若点距不超过R，A到点B且经2、3象限上的点的最短路长度。（3≤N≤300，0≤R≤300，坐标为(-100000,100000)内的实数分别以点A，点B2、3象限的中转点pdis(Ap)+dis(pB)更新最优值即可。+Best用opt[0..2N-1]的状态表示N个点中的将其两两配对后+Hacker's24bits的数a、b、c，设经过mod224a1、b1、c1一组满足要求的a、b、c+Aliseand一个数，Basilio来猜，Alice可以对BasilioYESNO。已知Alice1,2,…,N各ni次，根据这个Malvina写了个程序让猜测这样问题就转化为了较简单的Huffman编码问题，即对频次为ni的N个字符编码，然后程序的询问相当于在Huffman树有关Huffman以及其他各种编码译码的问题可以参见我+一些录在时间为N分钟的磁带上，制的曲目不能重复）+要写一个程序对有N簇的磁盘上的K个文件做整理，使得大小为Si（包含Si个簇）文件ii-1后的Si簇（11到S1optimizationneeded"。O(N)。+Bi表示满足i<j且Ai<Aj的j的个数。给出B，求A。直接按照i从小到大的顺序，用链表每次取出剩余元素中Bi+1大的即为Ai，复杂度为O(N2)，可以通过此题O(log2N)的时间内查询，总复杂度为O(NlogN)+过不匹配的正则表达式R，判断一个字符串SR匹配。好像Ruby，Python等语言有内置正则表达式匹配，可以直此类匹配问题大都可以在O(N2)的时间内解决，用状态g(ij)表示目标串前i位和模板前j位是否匹配或者最多匹配多少位等，转移通常是常数级别的，如此题每个状态只和g(i-1,j)、g(i,j-1)，以及当遇到’]’时找到其匹配括号’[’的位置所产生的不知道有没有O(N)的算法+给出一个长宽为偶数的棋盘，上面有n棋盘上有3类位置：1个点互相对称，2个点互相对称，4个经存在q个jewel的位置。给出一些二元组(pq)，p=1,2,4，0<=q<=p；从中选出一些二元组，使得p=N，并且q最大。先不考虑(1,q)；如果Nmod40，那么选取的(2q)必然是偶数个，也就是说，(2q)必然是成对选取的；按照这个思想，如果选两个(2,q)，必然是选q最大的两个二元组，依次类推；那么，可以把所有的(2q)转化成(4q’)，每次挑选两个q最大的二元组(2,q1)(2,q2)合并成(4,q1+q2)即可。如果Nmod42，那么先挑一个q最大的(2,q)，剩下的合如此，只需要面对的就是(4,q)，相信对于这样的贪心们是可以轻松解决的+MaxDay2的投篮（shooting），给出n个整数分成m组，使+Queuefor有Ni个人买一张票需要Ai秒，两张需要Bi秒，三张需要Ci秒。连续的几个人（最多三个）+Counting给出一张分成了*N次放上K1Li的起点不同的黑纸片询问最后白方格个数或者白连通块个数。集，当上一行存在的集合没有延伸到当前行时，累加这种复杂度，时间复杂度为O(MNlogK)。 2005WC的解题报告。RP），使用类似于C++中的bitset或者vector<bool>减少使用类型浪费的3比特这样O(MN)的空间是可以承受（MIPT64Mb），然后K条黑纸片直接在读入时存进矩阵（虽然K*max(M,N)很大……），之后用BFS实现FloodFill统计连通块数。厄……恶寒中，当年偶真是无+求所有{23n,n+1}的排列A，使得任意i都有Aimodi=0。Searchingwithunderwear搜吧，搜吧，人总要学着搜索长大+在n*n有的棋盘上覆盖最多的不的块将棋盘黑白间隔染色，以黑色为x部，白色为y部，得到一个+GraphSearchingwithunderwear+Squarerootof本问题以及置换群的各种幂运算的具体方法可参见的，，集队+求最大的正整数L，使得Sum[Floor[A[i]/L]1≤i≤n]≥K成立。（0≤A[i]≤10000000，二分查找L，当当前L值满足条件时，说明L可以取更大值，复杂度为O(NlogL)。0（好像MIPT很多题都不+Chess90度）一个面上有值的正方块，24个结点，连好边后直接dijkstra。+Enclosingpointwithpolygon给N个点和点P，选一些点组成多边形使得P在它的 （注意P不能在多边都过K，要求多边形周长尽量小4位小数的形式给出）回忆一个判断点P是否在多边形C的算法：从C向外作一条射线，若与P的交点为奇数条则C在 ，否则在外部（参见Problem023本题可以看作是要找出一条最短的闭合路线。使得被P向外的射线经过奇数次。记录（u,v,k）表示一条由uv的路线，使得Pk（k=01那么答案就是min(F(u,u,1)。F可以通过最短路算法来求解。值得一提的是，由于求的是最短路，求出的多边形一定是简单多边形，不会有边自交的情况，如下图所示：DA 此题最容易错的地方是判断线段是否和P引出的射线相交，如判断nPOI05SpecialForcesManoeuvres一题是此题二维版本：要求一个平面上n个圆是否有交集。首先，若干个圆的交中横，。，。小的。设n个圆为C1C2CnPxmax(P)，相应地定义xmin，上面的结论写成公式就xmax(⋂nCi)=xmin{xmax(Ci∩Cj)}推广到三维球的情况，只用求出每三个球的交集的z坐标+Rootofthe解方程x^(x^(x^(x^(个A，其中x1此题相当于求xA=A的解，于是x=AA，注意A>e或+Bracketstructure（如”)))…)(…(((”O(N)。如果LRmdiv2+ndiv2+mmod2+nmod2。+N皇后问题Searchingwithunderwearor强烈一道有位置的N皇后问题：。这道题需+Next给出一个长为L的单词，求所含字符相可以直接调用STL中的next_permutation算法next_permutationstr，求字符序与其相邻的较大一个，可以找到str从右往左第一个满足str[i]<str[i+1]的i，将str[i]和str[i+1]交换，然后将+(00)，求光源对多边形的照度。知的常数，r是光源到点的距离。对于高度为hdl的垂直元线段（可以dI=I0·|cosA|·dl·hA对于照度可以这样理解：I0·|cosA|·dl·h=k·(|cos=圆上的一段弧长（物理竞赛中常用的微元法@_@），ds/r就是圆心角。于是问题就转化为求k*h*[从光源看全多边形的圆。。来减少误差。这道题是NEERC98的，数据和标程都很好找^_^+给出一个M*N的字谜，每个（20*20很明显的搜索题，VIJOS上也有一道同样的题，但是好像难过好像不少的小都被搞成了ACM题@_@Swimming在一个MX*MY的矩形房间中有N个圆形，求一个能放在房间中的最大的由于所有半径相同，于是可以对所有的圆心O(N2)地构造DT（转化为求Voronoi图），然后对于DT中的每个三角形，求出和三个顶点上的外切的最大圆，只有O(N)个。（没写过Voronoi，是洪骥同学告诉-_-Clusterizationofbinarywords两个串的hammingdistanceD+2-SAT问题：问n个变元是否存在一个解满足m个最多只有两个变经典算法，可参见2003集训队：伍昱的《由对称性2-SAT问题》。这篇文章也有详细的讲解+Farthest（点数个指针i和j扫描一圈即可，j表示离i最远的对踵点，j一定沿i扫描方向前进。+一个等边三角形A'B'C'使得r=max(|A'A|,|B'B|,|C'C|)假想已知r的上限。这样A’,B’,C’的范围就是3个半径为r的圆。那么首先令A’=A,B’=B，那么可以求出一个C’（不妨设这个C’初始位置为D）。C’也在相应的半径为r圆心为DA’，移动B’C’继续移动了至多rC’C为圆心rDC的距离≤3r。所以可以知道r=(以A,B为顶点的等边三角形第三点和的距离的最小值)/3Cr 那么根据前面的结论。所求的C’在此时仅有唯一确定的点，也就是CD的三等分点中比较靠近C的点。同理可以求出A’，B’。很巧妙的是这样求出的∆A’B’C’恰好是一个等边三+给出n!的值，求n直接高精度乘上去的时候判断，如果想偷懒就用Java，直接乘，较大时看log10(乘出来的数)是否和log10(读入的double值)的差在较小范围内（如1），是则输出答案+判断一个含"&|!"与最多n个变元的布Problem030p-adic数(a0a1p代表a0p0a1p1+...，其中ai为[0,p-1]的整数且p为素数。那么可以定义p-adic设A和B分别是自然数a和b的p-adic数形式，那么设p-adic数X=a/b，则有B*X=Aa，b和pa/b得p-adic表达，输出最短非循环部分pB*X=A可以看作将b乘到X的每一位上最后得到了可以从xo开始逐个求出X先预处理一个数组inv[]，其中inv[i]满足p)+p-adic计算时当前计算的X位Xiinv[amodp]，然后将a(a-b*Xi)/p。如此循环计算直到a为非正数，这时已计算出位就是X的开头的非循环部分。若此时a0+8-8公司的Astar某次总决赛就是比谁的8数码算得快-_-|||。8数码搜法A*之类的个人认为最好写的是直接广搜，80~8的全排列，总状态数不多，具GraphO(n2)的DMP算法能过，还有Hopcroft-Tarjan平面判定法……有的同学可以去查看资料151000没时间做-_-|||。和8数码不一样的是空间和时间都不允许））剪枝，以及将最后几步const出来等来优+给出一张有向图G(V,E)，在其中选最0O(E)+Whatisthenumber(PartII)?答案对应的N的区间const下来（答案范围很小），N后+PS表示法表示的图只能有并联串联两种形式。求一个用PS表示法表示的电（电阻值在[0,100000]内，输入长纯粹的物理题，用递归（或模拟递归）+PS-graph。即可以从一条边经过若干次double和split操作得到。（如果有两条重复边，那么肯定是由一次duplicate操作得如果有一个点出度入度均为1，那么肯定是有一次split操PS图以通过事实——操作12不会将一个PS-graph变为非+PS-graph。即可以从一条边经过若干次double和split操作得到。（如果有两条重复边，那么肯定是由一次duplicate操作得2，且两边不重复，那么肯定是有一次split操作得到，合并为一条。PS图样用C++中的STL实现会很方便Cutted把n个矩形拼成一个大矩形，要求用一直接搜0+Upgradingto0的点u0的点v，那么连(v,u)如果存在不能到达的点v，那么连(v,u)0的点v，那么连(v,u)否则乱连一个(v,u)0PS-scheme,给出有理电阻值R=M/NM和N最少的电阻值为1的单位电阻，且能用PS表示法表示这个电阻网路。（1≤M,本题是094错误贪心是这样的：对于M=N直接一个电阻，M>N则用一个单位电阻和剩余的串联，M<N则并联尽量多的单位电阻和N/(MmodN)的电阻。2007长春赛区ProblemG 和N都不超过512，下面解题报告：点就是要注意到，m/n和n/m的组成是正好对称的）。m/n，428/22615214/11316。这就是题目描述最后一段的用意，根据这个限制，m/n只需要计算到512就可以了。+NimGame--Whoisthewinner?有k堆石子，每次可以从任意一堆里拿人获胜。已知k和石子的分配情况，求（k<50，每堆石子数经典的Nim问题，直接将k个数xor起来，得到当前局面xor值，如果xor0可以简单地发现，xor0的局面无论怎么操作都会得到非0局面，而可以使得一个非0局面的后继是0局关于博弈问题，如SG函数等，可以参见张一飞的《由感还有很多有关gametheory的外文书籍，有的同学可以去网上搜索。+StoneGame--有k将所有的石子个数mod30、1、2进行xoristhe出2的幂个石子，拿走最后一颗石子的人获胜。已知k和石子的分配情况，求（k<50，每堆石子数0与Problem10020mod31,21mod32，因此必胜者可以不断进行使得对手得到的局面的xor值总0。+StoneGameII--whoisthewinner?有k堆石子，每次可以从任意一堆里拿k和石子的分配情况（k<50，每堆石子数此题要用到著名的Sprague-Grundy而多个并行的博弈的总SG值就是他们各自的SG值得xor值——P100和P101也都用到了SG函数。当一个局面的SG0时，就是必败态，否则为必胜态。而此题的每堆石子的SG值再简单的列举后可以发现就是f(x)={xdivf(xdiv这样只要计算初始状态的f+NimGame--Give有k堆石子，每次可以从任意一堆里拿人输。已知k和石子的分配情况，求先（k=4，每堆石子数这就是是大名鼎鼎的MisèreNim。其实本题的算法和Problem100是一样的，只是当所有的石子数都≤1时，将同样可以一个xor计算后的序列，使其始终全0。但就要使xor1+CamoGame--whoisthe输。告诉你M和石子分配情况，求先手得出SG函数：SG(x)=min{n|n!=SG(L)xorSG(R)}。最后将所有m列的SG值xor起来得到最终的SG值。当然你也可以找找SG值的规律。Problem100-104是优秀的博弈问题，特别是SG这方面的入门题目，当年曾让我获益匪浅。除了P048中提到的极大极小思想外，SG也是博弈方面很重要的内容大家去看看胡伯涛PT07比赛的ProblemA:PlaywithaTree。+MRQ经典RMQ问题：在给定n个元素的序列上询问一段区间中的最小值m个询问。采用SparseTable，O(NlogN)–O(1)：F[i,j]表示区间[i,i+2j-1]内的最小值，然后按照j从小到大计算值，求区间最小值时将区间分为中间可能部分的2?的两个区间查询。此题很容易MLE，其实只要不使用double类型，使用Pascal中的real或者C中的float就可以了。还有法也可以节23——F[i,j]表示区间[i,i+3j-1]内的最小+给出一张有M，，，，+Infixtopostfix（递归着做写起来可能容易些，关于表达式处理可参见P087分+GrammarofaGreatMachine(Correctwords1)3SSS||7SSSSSSS)，给出串一个（输入为一行由0-7组成的长度不超0串（用栈实现，从前往后贪心的扫描）0串Half-planes+Graph（1000个用类似于Kruskal最小生成树的方法判断哪些是边，然后重Reductionto给出一个多项式SS::=|R(('+'|'-')NUMBER:=<integernumberlessthan10000inmoduli>PNUMBER:=<postiveintegernumberlessthan1000>R::=A('/'A)?A::=|'x'('^'|'('NUMBER|'('C(('+'|'-')C)*C::=(NUMBER'*')?'x'('^'或者”0”的形式，要求(p(x),低。’*’的结合性是从左到右，即a-b-c是((a-b)-c)。（10002000000000+一个n*m迷宫有K个出口，有些格子由于是网格，边比较少，直接SPFA可以通过。Plane（0<N≤1000，坐标为绝对值不超100000的整数直接建图然后DFS（对每个点按照边的极角序拓展+Unique给N个形如X*Y=Z或X+Y=Z的等11的串，如果进制可以唯一确定那么X，Y，Z不会超过264-1226The给一个由dot,hyphen0组成的表可能是hyphen）0使得所有连续hyphen的长度为给定值。0一定是-，“000”连续的“-”长度为2，则只能确定中间那个0为-，原串二维DP可以求出可行性问题，计算唯一性实际上可以看作是一个。以f[i][j]表示第一个串的前N个匹配到第二个串的前J可能。那么f[n][m]表示整个输入数据是否可能。注意到，题目就是要求一个f[n][m]到f[0][0]的必经点集（如HardNEERC可参见胡伯涛07年和作给P和A0,…,Ap-1，求次数不超过P-的多项式Q(x)使得Q(x)=Axmod所有系数均在{0,1,…,P-1}中+Universalparser达式的+RangeADDxy—在平面上添加一个者"ALREADYEXISTS