2009省选第二轮第七节试题七年第一试

第七节试题七（2009年省选第二轮第一试1、HH去散HH有个一成不变的，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一但是同时HHHH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步1B共有多少条符合条件的路径。HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。MAi，BiAiBiAi≠Bi，但不保证任路口从0到N−145989。453000023430%的数据，N4，M10，t10100%的数据，N20，M60，t230，0A,B<N，0Ai,BiN。本题给定一个可能有重边但没有自环的无向图和两个点A,BA走t步到达B的方案数。Ak步后的状态仅与最后走过的边和当前所在的A点走过k步后的状态可以仅用最后走过的有向边来230）,且转移方程为“和”的关系，所以想到用矩阵乘法来优化算法。考虑如何构造矩阵。通常是将答案矩阵设为1×N，第k个元素表示转移若干次后状态为k时的TP，那么： jii、j10×10的矩阵如下：0000000010000100000100001000000000010000000100100001100000001010000000110000000000000010010000000100t0步的状态仅为一个点，无法mR为0m的最。第i条边的起点是HH散步的起点A，那S[1][i]=1，否则为0。对于最终1×N的答案矩阵T，有效的元HHB的边。那么： j的终点为B如果i的起点为A，那么S[1][i]=1,得到： i的起点为A，j的终点为B1×N的矩阵，只需要一个二重循环即可计算出答案。事实上通常做矩阵1×N的矩阵。iP[i][i]=1，即可以从这个状态转移到下个阶段同一个状态。本题构思妙主要矩阵乘的基础识和动规划“无后性由于目所给是无向图状态也是本的最点试时多选手都没有想“拆而没思路或用点表programconstmatrix=array[0..123,0..123]oflongint;edge:array[0..63,0..1]oflongint;functionmul(a,b:matrix):matrix;vari,j,k:longint;fori:=1tom+mdoforj:=1tom+mdofork:=1tom+mdomul[i][j]:=smodmm;assign(input,filename+'.in');reset(input);assign(output,filename+'.out');rewrite(output); fori:=1tomdoreadln(edge[i][0],edge[i][1]);fori:=1tomdoforj:=1tomfi<>jthenifedge[i][1]=edge[j][0]thenifedge[i][0]=edge[j][0]thenifedge[i][1]=edge[j][1]thenifedge[i][0]=edge[j][1]thenb[i+m][j+m]:=1;fori:=1tom+mdoa[i][i]:=1;fork:=0to30doif1shlk>lenthenif(1shlk)andlen>0thena:=mul(a,b);fori:=1tomdoifedge[i][0]=enthenk:=i+melseifedge[i][1]=enthenk:=ielsecontinue;forj:=1tomifedge[j][0]=stheninc(ans,a[j][k])elseifedge[j][1]=sthen n(ansmodmm);close(input);close(output);2、常和别人比赛计算。有一天Shengbill很嚣张地找到了你，并要求和你比赛，但是输给Shengbill岂一行，表示AB的最大公约数。620%的数据，0A,B1018100%的数据，0A,B1010000。本题需要用高精度求两数的最大公约数。通常所常用的求最大公约数的方法是辗转相除法。即取模相对比较麻烦，且并不常用，初次写易写错。因此，使用另外法——二进制算法。至多一次减法后就会有一个数除2，所以该算法的时间复杂度为O(log2n)。相对于本题的数据规模，6位即可。52的幂次tt2乘回。本题的两种求的方法时间复杂度均为O(log2n)，在压相同位的情况下效率相近。而对于普通两个整型数求，如果使用二进制算法，并用位运算优化，对于随机数据在速度上是有一定优势的。由于高精度取模容易写错，因此二进制算法对于高精度求是很好的选择。programconstfilename='typenumber=array[0..2003]oflongint;procedureprint(a:number);vari:longint;fori:=a[0]-1downto1doif(a[i]<100000)thenwrite(0);if(a[i]<10000)thenwrite(0);if(a[i]<1000)thenwrite(0);if(a[i]<100)thenwrite(0);if(a[i]<10)thenwrite(0);proceduredivide(vara:number;k:longint);varx,i:longint;fori:=a[0]downto1doa[i]:=xdivk;x:=(xmodk)*mm;while(a[a[0]]=0)and(a[0]>0)dodec(a[0]);procedurechange(s:ansistring;varvark,i:longint;k:=length(s)mod6;a[0]:=length(s)div6+ord(k>0);ifk>0thenfori:=a[0]-1downto1doelsefori:=a[0]downto1functionlarger(vara,b:number):longint;vari:longint;if(a[0]<>b[0])thenexit(ord(a[0]>b[0]));fori:=a[0]downto1doifa[i]>b[i]thenexit(1)elseifa[i]<b[i]thenexit(0);procedureminus(vara,b:number);vari:longint;fori:=1toa[0]doifa[i]<b[i]begininc(a[i],mm);dec(a[i+1]);end;while(a[a[0]]=0)and(a[0]>0)dodec(a[0]);proceduremultiply(vara:number;k:longint);vari,x:longint;fori:=1toa[0]doa[i]:=xmodmm;x:=xdivmm;if(x>0)begininc(a[0]);a[a[0]]:=x;end;assign(input,filename+'.in');reset(input);assign(output,filename+'.out');rewrite(output);readln(s);change(s,a);readln(s);fortwo:=0tomaxlongintifodd(a[1])orodd(b[1])thenbreakelsebegindivide(a,2);divide(b,2);end;whiletruedoif(k=2)thenbreakelseif(k=1)thenminus(a,b)elseminus(b,a);whilenotodd(a[1])dodivide(a,2);whilenotodd(b[1])dofork:=1totwodomultiply(a,2);close(input);close(output);3、晨Elaxia最近迷恋上了空手道，他为自己设定了一套计划，比如俯卧撑、仰卧起坐等等，不过到目现在给出一张学校附近的地图，这张地图中包含N个路口和M条街道，Elaxia只能从一个路口跑向另外一个路口，街道之间只在路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室为1，学校为N。每天的晨跑路线都不会相交（在路口处寝室和学校不算路口。Elaxia耐力不太好，他希望在一M3a,b,ca和路口b之间有条长度为c的街道（单向。7121324365767230%的数据，N20，M120100%的数据，N200，M20000。大流的模型。题目中要求在路口不相交，即要求各路线没有公共点（除起点和终点。而通常的网络iii+n，i接受流，i+n送出流，边(i,i+n)1i一次。1。构造新图。首先根据“不在路口相交对于2≤i≤n-1,添加边(i,i+n)，容量为1，费用为0。对于k的边(i,j)，添加边(i+n,j)1k。由于起点和终点没有流量限制，可以直接以1+n、n0的边(1,1+n)、(n,n+n)1、n+n为源汇点。模仿sap算法的“高度标号，对每个点一个“距离标号，即该点到汇点的最短增广路的长度。初始0zkw流的“重标号”过程会调用O(N2)次，每次复杂度为O(E)，所以算法的时间复杂度为O(N2E)。虽spfadijkstraspfa进行初始，但这样无疑会增加代码量。其实通常可以根据图的结构来确定算法。通常来说，对于spfa算法；而对于那种可以保证增广路不会“太长”的图，zkw流。情况下反而会使算法变的更慢。zkwsap算法相似，也同样可以进行初始距离标号，以及“当前弧”优化，有时会取得不错的效果。有的选手可以针对不同形状、密度的图对各种算法及优化方法进programconstfilename='run';e:array[0..50000]ofsro;re:array[0..403]oflongint;q:array[0..100000]oflongint;v:array[0..403]ofboolean;inc(num);e[num].c:=c;inc(num);e[num-1].r:=num;e[num].r:=num-1;assign(input,filename+'.in');reset(input);assign(output,filename+'.out');rewrite(output);readln(n,m);num:=0;fori:=1tomdofori:=2ton-1doaddedge(i,i+n,1,0);s:=n+1;en:=n;cost:=0;forflow:=0tomaxlongintdofilldword(d,sizeof(d)shr2,1000000000);h:=0;t:=1;q[1]:=s;d[s]:=0;while(h<t)doinc(h);k:=q[h];v[k]:=false;j:=a[k];while(j>0)doif(e[j].c>0)and(d[e[j].w]>d[k]+e[j].f)thenifnotv[e[j].w]theninc(t);q[t]:=e[j].w;ifd[en]=1000000000thenbreak;whilek<>sdo n(flow,'',cost);close(input);close(output);第八节试题八（2009年省选第二轮第二试1、HH的项HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都第一行：一个整数N第二行：N个整数，表示依次表示项链中贝壳的（为0到1000000之间的整数。MHH询问的个数。M行：每行两个整数，LR（1LRN，表示询问的区间。M行，每行一个整数，依次表示询问对应的答案。612343313222420%的数据，N≤100，M≤1000；40%的数据，N3000，M200000；100%的数据，N50000，M200000。此需要找出一个有“代表性”的点，当然是第一个最有“代表性。观察该点，以及它前后同色点它们上一个色点然在区内这样的工作是找到问区间,r中这样点x的数点x,r左侧。。到这一步，有一个算法：建线段树，将询问分成O(log2n)个小区间分别处理。如果再套平衡树，需要二分查找才能求符合条件的点的“个数。这样总的理论复杂度为O(m(log2n)3)，虽然实际情。当然，线段树是无法再套树状数组的，那样空间复杂度会达到O(n2)，所以要舍弃线段树，寻找新的算法。对于一堆“无序”的询问区间，如果没有线段树，便很难处理。因此考虑将区间按左端点过，而区间内其他点却没有！这样，如果换个角度，改“上一个”为“下一个，预处理出每个点iO(mlog2n)。inext[i]n+1。同时，由于某颜色第1。tt次1programconstfilename='diff';a,next,x,y,o,c,ans:array[1..200003]oflongint;last:array[1..1000000]oflongint;proceduresort(l,r:longint);vart,i,j,k:longint;i:=l;j:=r;k:=x[(i+j)shr1];whilex[i]<knc(i);whilex[j]>kdodec(j);ifi<=jthent:=o[i];o[i]:=o[j];o[j]:=t;inc(i);dec(j);untili>j;ifl<jthensort(l,j);ifi<rthenprocedureadd(x,t:longint);whilex<=ndoinc(x,xand(-x));functiongetsum(x:longint):longint;whilex>0dodec(x,xand(-x));assign(input,filename+'.in');reset(input);assign(output,filename+'.out');rewrite(output);fori:=1tondoread(a[i]);filldword(last,sizeof(last)shr2,n+1);fori:=ndownto1dofori:=1to1000000iflast[i]<>0thenadd(last[i],1);fori:=1tomdofori:=1tondowhilex[k]=idofori:=1tomdowrin(ans[i]);close(input);close(output);2、Bill的与他打成了平局，这导致Shengbill极度的不满。于是他再次你。这次你可不能输！，S1,S2,...,SN1000003若字符串Sx（1xN）和T1iSx.length，满足Sx[i]=′?Sx[iT[i]。T只包含小写英文字母。第一行：两个整数，N和K（含义如题目表述。N行：每行一个字符串。对于每组数据，输出方案数目（T行。1230%的数据，T≤5，N≤5，字符串长度≤20；70%的数据，T≤5，N≤13，字符串长度≤30；100%的数据，T5，N1550。是匹配“恰好”k个字符串，所以很自然地想到状态压缩的动态规划。设f[i][j]i个字符，对于本题来说，某一个状态j需要由他的若干包含自己的状态转移到。首先，知道转移时可能要举这一位所放的字母。好在字母只有26个，可以一一枚举。由此可以做一个预处理：设g[i][ch]表示k，这一位上放chkandg[i][ch]。发现，无法得知能够转移到状态f[i][j]的状态具体是哪些，因为需要一次“和”操作才能判断是否转移。所以须换个思路，反向思考，可以发现，虽然无法判断谁能转移到f[i][j]，但是可以很轻松的找到f[i][j]所能转移到的状态。假设已经计算好了f[i][j]，枚举下一位ch(‘a’..‘z’)，这样下一位的状态便是jandg[i+1][ch]，可以将f[i][j]直接加到f[i+1][jandg[i+1][ch]]中。得到以下方程：f[i][j]→f[i+1][jand len)，情况约4.4×107。有个非常有效的“剪枝，就是当f[i][j]>0时才进行接下来的转移，这个剪枝10倍左右，可以在时限内通过全部测试点。预处理出g数组后，首先赋初值，可以让f[0][2N-1]=1,其他全为0。然后枚举位数i(0~len-1)、状态j，f[i][j]>0ch(‘a’~’{‘)len位后,计算答案ANS=∑f[len][j]（j包k个字符串。3倍。个呢？那么便无法找到有效的状态转移方法，因此需要放弃动态规划，另辟蹊径 考虑如下公式 CCt n

(n>k)有了这个公式，可以想出另一个算法。初始ans=0，2N枚举某个字符串tcc>=kc个字符串的num（0ans=ans+(-1)(c-k)×numCk。ck个时它被算了Ckk+1个时它被算了Ck1次……g个时它被算了Cg gans时都乘上了Ck,(1)tkCtCkg=kg gt由于本题字母只有26个，与状态压缩动态规划相比，该算法无明显优势。但当字母数非常多时，该算法programconsta:array[0..15]ofstring[53];b:array[0..53,'a'..'{']oflongint;f:array[0..53,0..1shl15]oflongint;procedureadd(varx:longint;y:longint);if(x>=mm)thendec(x,mm);functioncount(x:longint):longint;while(x>0)dox:=xand(x-1);assign(input,filename+'.in');reset(input);assign(output,filename+'.out');rewrite(output);forii:=1tottfori:=0ton-1doiflen<length(a[i])thenlen:=length(a[i]);fori:=1tolendoforch:='a'to'z'doforj:=0ton-1doif(length(a[j])>=i)and(a[j][i]in['?',ch])theninc(b[i][ch],1shlj);forj:=0ton-1if(length(a[j])<i)theninc(b[i]['{'],1shlans:=0;f[0][1shln-1]:=1;fori:=0tolen-1doforj:=1to1shln-1 if((count(j)>=m)and(f[i][j]>0))theniff[i][j]>0thenforch:='a'to'{'add(f[i+1][jandb[i+1][ch]],f[i][j]);forj:=1to1shln-1doif(count(j)=m)thenadd(ans,f[len][j]);close(input);close(output);3、Elaxia的路最近，Elaxiaw**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和之间，他们希望在节约时间的前现在已知的是Elaxia和w**所在的宿舍和的以及学校的地图地图上有N个路口M条路，第一行：两个整数NM（含义如题目描述x1、y1、x2、y2（1x1N，1y1N，1x2N，1≤y2N分别表示Elaxia的宿舍和及w**的宿舍和的标号（两对点分别为x1,y1和x2,y2M行：每行三个整数，u、v、l（1uN，1vN，1l10000uvl。9334394546475879330%的数据，N≤100；60%的数据，N1000；100%的数据，N1500，输入数据保证没有重边和自环。dijkstraspfa求最短路，并加上一些处理而成的。N1500，因此floyd算法肯定会超时，但直接使用dijkstra很难找到突破口。假设答案路线是从点u到v，那么显然，u、v一定都在x1到y1和x2到y2的最短。那么反过来呢？由此，有了一个初步的算法：假如u、v都在x1到y1和x2到y2的最短，那么直接将u、v当作答案路线的两端点来更新答案。判断某个点k是否同时在两条最短并d[x2][k]+d[y2][k]d[x2][y2]u、v为端点的公共最短路线的长度了。猜想其为d[x1][u]-d[x1][v]，用其来更新答案。这样，可以在做完4遍dijkstra后n2枚举u、v，判有问题。有问题的地方就是更新答案，因为无法判断点u、v之间是否能够有所想要的那种公共图中u、v均在两条最短，但是d[x1][u]-d[x1][v]=1，而答案很显然为0。该算法之所以出错，就是因为u、v中并没有那种“公共最短路，而是根本就在两条不相干的最短。u、vx1为源点，spfa的算法，只不过要对于每个点up，满足“从ux1的某条最短路p容易构造出专杀数据。需要另辟蹊径。，从点难以手便边下手刚的算法所有反例是因两个同公共最路的点间可公共最路考虑适当的取反这样就将最长变求最可以用a求短观察下图：，图中边的为1至5，需要求的答案是3，而3中可能包含若干条原图中的边。这些边权取反，其他边1245取0，这样，发现答案就是从x1做spfa/