为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划noip引水入城解题报告NOIPXX解题报告(提高组)Translate开一个队列进行模拟就行了。PS:这题数据比较厚道，按照题目的描述来说，单词的编号是非负整数，也就是说可以是0。但是数据中并没有0，否则就要有很多人要降10分了。Tortoise动态规划。用Fi1,i2,i3,i4表示数字1的卡片取了i1张，数字2的卡片取了i2张，数字3的卡片取了i3张，数字4的卡片取了i4张，可以取得最大的分数。写起来很好写，四个for，再加上四个if。Fi1,i2,i3,i4=max(Fi1-1,i2,i3,i4,Fi1,i2-1,i3,i4,Fi1,i2,i3-1,i4,Fi1,i2,i3,i4-1)+score1+i1+i2*2+i3*3+i4*4PS:这题用120*40*40*40，350*40*40*40的算法都是可以的。Prison二分+二分图判定并查集解法1：先二分答案，然后进行二分图的判定。判定方法如下：首先取一个没有走过的结点放在了左图，然后把和这个点有边的点放在右图，然后再把和这些右图有边的点放在左图，一直下去，知道把所有点都放好，或者出现矛盾为止。解法2：把边权从大到小排一次序，依次插入。用并查集维护这些边之间有没有矛盾。详情看并查集经典例题：PKU1182食物链。Flow(floodfill动态规划各种乱搞算法)+(贪心+动态规划各种乱搞算法)最短路显然第一问一次O(NM)的floodfill就可以求出是否可以到达全部最后一层的格子。现在假设最后一行的所有格子都可以到达。定理1：从第一行的格子，可以到达的最后一行的格子必然是连续的一段。证明1：假设格子A可以到达的最后一行中间有部分格子不可到达。由题设可知，必有另一个格子B可以到达这些A不可到达的格子。但是，显然A到达下面格子的路径必然与B到达这些A不可到达的格子的路径有重合部分，所以，A也能到达下面的A到达不了的格子。矛盾，所以假设不成立，原命题成立。定理2：第一行从左到右的格子对应下面的格子区间的左边界和右边界必然是单调不递减的。证明2：假设第一行有格子A、B，并且A在B左边，最后一行有格子C、D，并且C在D左边。假设A能到达D不能到达C，B能到达C不能到达D。那么，A到D和B到C的路径必然有重合的部分，所以A也能到达C，B也能到达D。所以假设不成立，原命题成立。定理3：从任何一个格子出发，可以到达的最后一层格子也是连续。证明3：与定理1类似，略。上面3个定理，可以得出一个大概的算法：第一步：先把上面每一个格子对应的区间求出来；第二步：然后再对这些区间进行操作。第一步方法1：枚举上面一层每个格子，进行floodfill，把下面可以到达的区间求出来。然后对于第一层每个格子，它需要枚举当且仅当它左边和右边的格子都不能到达它。第一步方法2：从flx,y表示(x,y)能到达区间的左边界，用frx,y表示(x,y)能到达区间的右边界。flx,y:=min(flx1,y1)，frx,y:=min(frx1,y1)，条件是(x,y)可以走到(x1,y1)。转移顺序按照格子的海拔从小到大进行。第二步方法1：贪心。第二步方法2：动态规划。如果嫌时间多可以加上个单调队列去优化一下。事实上这题的瓶颈在于第1步，第一步方法1是O(N3)的，但是经过试验，我在这题加上了若干常数优化后，A掉了。详细的运行时间看下面的图片。新增一个最短路的方法：NOIPXX第四题引水入城最短路解法这道题目可以说正统的解法是找区间，然后再进行贪心。而经过我的研究发现，这题是可以用最短路来解决的！首先，那样例作为说明：首先，把每个格子当做一个点，然后如果格子A的水能流到格子B，就从A到B连一条边现在称这个图为G。然后我们要构造一个G，就是把G所有边反向。下图为了后面描述方便，就把G的pic进行上下翻转了一下。然后，要构建主图H。主图H有M个点：A1,A2,A3.Am+1，对于任意1=s)A/B-A/B的值尽可能小代码如下vara,b,l,i,j,k:longint;s:real;p:boolean;assign(input,);assign(output,);reset(input);rewrite(output);readln(a,b,l);s:=a/b;a:=l;b:=1;fori:=1toldoforj:=1toldobeginp:=true;fork:=2toidoif(imodk=0)and(jmodk=0)thenp:=false;ifj=1thenp:=true;ifpand(i/j=s)and(i/j-send;whilebx+1dobegina:=a-1;k:=k+1;if(a=j)and(b=i)thenbeginwriteln(k);close(input);close(output);halt;end;end;x:=x+1;whilebx+1dobeginb:=b-1;k:=k+1;if(a=j)and(b=i)thenbeginwriteln(k);close(input);close(output);halt;end;end;end;end.4.子矩阵两个组合产生行和列，计算机和，打出最小值procedurech(y,k1:integer);生成行，如果行的个数超过r生成列，列的个数超过c，计算相邻元素差之和，打擂台求最小值。代码如下：varn,m,r,c,i,j:integer;he,ans:longint;a,b:array1.20,1.20ofinteger;h,l:array1.20ofinteger;procedureqc;vari,j:integer;beginhe:=0;fori:=1tordoforj:=1tocdobeginif(i+1)hethenans:=he;end;fori:=ktomdobeginlx:=i;cl(x+1,i+1);end;end;procedurech(y,k1:integer);vari:integer;beginify=r+1thencl(1,1);fori:=k1tondobeginhy:=i;ch(y+1,i+1);end;end;beginassign(input,);assign(output,);reset(input);rewrite(output);readln(n,m,r,c);fori:=1tondobeginforj:=1tomdoread(ai,j);readlnend;ans:=maxlongint;ch(1,1);writeln(ans);close(input);close(output);end.NOIPXX提高组解题报告T1神奇的幻方【题目大意】告诉你幻方的构造方法，给出N*N幻方的方案。N39且为奇数。【解题说明】直接模拟即可【代码】#includeintn,m,i,j,x,y,a5555;intmain()scanf(%d,&n);m=n*n;x=1;y=(n+1)/2;axy=1;for(i=2;i#include#defineNusingnamespacestd;intn,i,tm,tp,now,ans,sz,toN,dfnN,lowN,stN;boolisN;voiddfs(intx)dfnx=lowx=+tm;st+tp=x;isx=1;inty=tox;if(!dfny)dfs(y),lowx=min(lowx,lowy);elseif(isy)lowx=min(lowx,dfny);if(lowx=dfnx)for(sz=now=0;now!=x;)now=sttp-,sz+;if(sz1)ans=min(ans,sz);intmain()for(ans=1e9,scanf(%d,&n),i=1;i#include#include#definemxhusingnamespacestd;intans,T,n,i,x,y,pai6,cnt15;voidfind(intstep)inti,j,k,w;if(step=ans)return;ans=min(ans,step+pai1+pai2+pai3+pai4);if(pai4)for(i=2;i1)paicntj-;cntj-=2;paicntj+;for(k=j;k1)paicntk-;cntk-=2;paicntk+;find(step+1);paicntk-;cntk+=2;paicntk+;paicntj-;cntj+=2;paicntj+;pai4+;cnti+=4;if(pai3)for(i=2;i=3)paicnti-;cnti-=3;paicnti+;find(step+1);for(j=1;j1)paicntj-;cntj-=2;paicntj+;find(step+1);paicntj-;cntj+=2;paicntj+;paicnti-;cnti+=3;paicnti+;if(pai3+pai4=2)for(i=3;i=3&cnti+1=3)paicnti-;cnti-=3;paicnti+;w=i;for(j=i+1;cntj=3&j=3)for(i=3;i=2&cnti+1=2&cnti+2=2)paicnti-;cnti-=2;paicnti+;paicnti+1-;cnti+1-=2;paicnti+1+;w=i+1;for(j=i+2;cntj=2&j=5)for(i=3;iintL,n,m,i,w,l,r,mid,pos,ans,a55555;boolok(intx)