哈理工2016級新生賽解題報告(答案)

A采用遞推的方法，由于要到達棋盤上的一個點，只能從左邊或者上邊過來，根據(jù)加法原則，到達某一點的路徑數(shù)目，就等于到達其相鄰的上點和左點的路徑數(shù)目的總和。所有海盜能達到的點將其路徑數(shù)置為0即可。#include<stdio.h>#include<string.h>#include<stdlib.h>intmain(){inti,j,x,y,n,m,f[100][100];longlongans[100][100];intt;scanf("%d",&t);while(t--){scanf("%d%d%d%d",&n,&m,&x,&y);memset(f,1,sizeof(f));memset(ans,0,sizeof(ans));ans[0][0]=1;f[x][y]=0,f[x+1][y+2]=0,f[x-1][y+2]=0;f[x+1][y-2]=0,f[x-1][y-2]=0,f[x+2][y+1]=0;f[x-2][y+1]=0,f[x+2][y-1]=0,f[x-2][y-1]=0;for(i=1;i<=n;i++)if(f[i][0])ans[i][0]=1;elsebreak;for(i=1;i<=m;i++)if(f[0][i])ans[0][i]=1;elsebreak;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(f[i][j])ans[i][j]=ans[i-1][j]+ans[i][j-1];printf("%lld\n",ans[n][m]);}return0;}B對于任意點K，其與點1之間的最短路有兩種情況：直接從點1走到K；從1走到點A，通過A直接跳到點B，再從B走到K。或者說，這條最短路等于min（直接從1走到K的距離，從1走到點A通過A跳到B在從B走到K的距離）。設點I和J之間的直線距離為DIS[I,J]，則：在第（1）種情況下，最短路長度為DIS[1,K]；在第（2）種情況下，最短路長度為DIS[1,A]+DIS[B,K];由于DIS[1,A]是一個常數(shù)（因為A固定），而與K有關(guān)的只有B，應直接選擇A=1使DIS[1,1]=0.（也就是說傳送門的第一個點一定要建在1點上）。對當前枚舉的第二個傳送點位置B,必有唯一一個點C具有如下性質(zhì)：DIS[1,C]<=DIS[C,K]且DIS[1,C+1]＞DIS[C,K]此時距離1最長的點為C，C+1或N中的一個。留意到隨著B的遞增，C是不遞減的，所以在O（n）枚舉B的同時只需要O（1）就可以找到Ｃ。#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>usingnamespacestd;constintmaxn=1100000;inti,j,r,n,m,ansi,ansj,ansr;longlongans;longlongp[maxn];inlinevoidmake(){longlongtemp;ans=p[n];i=j=1;while(i<=n){while(j<i&&p[j]<=p[i]-p[j])j++;temp=max(p[i]-p[j],p[j-1]);temp=max(p[n]-p[i],temp);if(temp<ans){ans=temp;ansi=i;ansj=j;}i++;}}intmain(){intT;scanf("%d",&T);while(T--){memset(p,0,sizeof(p));scanf("%d",&n);for(i=2;i<=n;i++){scanf("%lld",&p[i]);p[i]+=p[i-1];}make();printf("%lld\n",ans);}return0;}SC首先需要判斷行和列的總和是否相等，因為它們都應該是整個矩陣的所有元素之和。如果他們不相等則這個矩陣肯定不存在。這道題的貪心策略是，把列和從大到小枚舉，對每個列和，按行和從大到小的順序進行選擇填上1，然后該行的行和減去1.這種貪心策略之所以有效，是因為這種策略會使各行的行和趨向于平均，盡可能地使行和減為零的情況推遲發(fā)生，而行和減為零意味著，當前可選的行數(shù)減少1，因此后面的計算可選擇方法肯定比這種貪心的策略要少。#include<stdio.h>#include<algorithm>usingnamespacestd;constintsize=100000; //最大行列數(shù)inta[size],b[size]; //分別保存行和與列和intmain(){ intr,c,i,j; longlongs,t; //枚舉時比較的行和與列和總數(shù) while(scanf("%d%d",&r,&c)==2){//輸入整數(shù)r,c直到文件結(jié)束 for(i=0,s=0;i<r;i++){ scanf("%d",&a[i]); //輸入行和 s+=a[i]; //累加行和 } for(i=0,t=0;i<c;i++){ scanf("%d",&b[i]); //輸入列和 t+=b[i]; //累加列和 } if(s!=t){ //如果行和與列和總數(shù)不相等 printf("NO\n"); //則不可能有解 continue; } sort(a,a+r); //行和排序 sort(b,b+c); //列和排序 for(i=j=0,t=s=0;i<c;i++){//從大到小枚舉列和 t+=b[c-i-1]; //當前已枚舉的列和總數(shù) s+=r-j; //當前可用的行和總數(shù) while(j<r&&a[j]<i+1){ //如果某行和小于枚舉列數(shù) s-=i+1-a[j]; //把行和總數(shù)多算出來的部分減去 j++; } if(s<t)break; //如果可用行和小于當前列和則不可能有解 } printf(i==c?"YES\n":"NO\n");//輸出答案 } return0;}D因為要求出N的因子個數(shù)，我們從素數(shù)開始討論。N=1時只有一個因子1，對于任意一個質(zhì)數(shù)p，只有1和p兩個因子，所以Sp=13+23=9,而對于一個質(zhì)數(shù)的冪pk，它的因子分別是p0,p1,p如果N有兩個不同的素因子p1和p2，這時不妨設N=p1k1*p2k2,這時可以把N的因子按照和p2k2的最大公約數(shù)來分成kSN ==i=0k1n=i=1采用類似的方法，對N的因子使用數(shù)學歸納法，可以證明對任意N=S#include<stdio.h>#include<algorithm>usingnamespacestd;constintsize=100000; //最大行列數(shù)inta[size],b[size]; //分別保存行和與列和intmain(){ intr,c,i,j; longlongs,t; //枚舉時比較的行和與列和總數(shù) while(scanf("%d%d",&r,&c)==2){//輸入整數(shù)r,c直到文件結(jié)束 for(i=0,s=0;i<r;i++){ scanf("%d",&a[i]); //輸入行和 s+=a[i]; //累加行和 } for(i=0,t=0;i<c;i++){ scanf("%d",&b[i]); //輸入列和 t+=b[i]; //累加列和 } if(s!=t){ //如果行和與列和總數(shù)不相等 printf("NO\n"); //則不可能有解 continue; } sort(a,a+r); //行和排序 sort(b,b+c); //列和排序 for(i=j=0,t=s=0;i<c;i++){//從大到小枚舉列和 t+=b[c-i-1]; //當前已枚舉的列和總數(shù) s+=r-j; //當前可用的行和總數(shù) while(j<r&&a[j]<i+1){ //如果某行和小于枚舉列數(shù) s-=i+1-a[j]; //把行和總數(shù)多算出來的部分減去 j++; } if(s<t)break; //如果可用行和小于當前列和則不可能有解 } printf(i==c?"YES\n":"NO\n");//輸出答案 } return0;}E將每個排列利用康托展開壓縮為一個整數(shù)，采用廣度優(yōu)先搜索的方式不停的搜索直到得到目標狀態(tài)即可。#include<stdio.h>#include<string.h>constintMAXNODE=362880; //最大狀態(tài)數(shù)structState{ chard[9]; //狀態(tài)中的9個字符 shortf; //這個狀態(tài)到達目標狀態(tài)的最少操作數(shù)};//pow[i]表示(i+1)!intpow[]={1,2,6,24,120,720,5040,40320};//4種不同的操作的逆操作的置換順序introt[4][9]={{1,4,2,0,3,5,6,7,8},{0,2,5,3,1,4,6,7,8},{0,1,2,4,7,5,3,6,8},{0,1,2,3,5,8,6,4,7}};shortans[MAXNODE]; //到達每個狀態(tài)的結(jié)果inthead,tail; //廣度優(yōu)先搜索中使用的隊列頭與尾StateQ[MAXNODE]; //廣度優(yōu)先搜索中使用的隊列//用康托展開把一個狀態(tài)變換成一個整數(shù)intState2I(State&p){ intret=0; for(inti=0;i<8;i++) //使用康托展開的公式 for(intj=i+1;j<9;j++)if(p.d[i]>p.d[j])ret+=pow[7-i]; returnret;}//預處理所有狀態(tài)到達目標狀態(tài)的最少操作數(shù)voidPreCom(){ memset(ans,255,sizeof(ans)); //清空數(shù)組為-1 head=-1,tail=0; //初始化隊列頭尾 Q[0].f=0; //初始狀態(tài)操作數(shù)為0 for(inti=0;i<9;i++)Q[0].d[i]=i+1;//初始化初始狀態(tài) ans[State2I(Q[0])]=0; //初始狀態(tài)的答案為0 while(head++<tail){ //運算直到隊列為空 State&p=Q[head],q; q.f=p.f+1; //經(jīng)過一次操作 for(inti=0;i<4;i++){ //枚舉4種不同的操作 //按操作的置換順序變換 for(intj=0;j<9;j++)q.d[j]=p.d[rot[i][j]]; intu=State2I(q); //得到新狀態(tài)的康托展開值 if(ans[u]<0){ //這個狀態(tài)并未被擴展 ans[u]=q.f; //更新狀態(tài)答案 Q[++tail]=q; //新狀態(tài)放到隊列末端 } } }}//處理輸入和輸出voidWork(){ Statep; intx; while(scanf("%d",&x)==1){ //輸入整數(shù)x直到文件結(jié)束 p.d[0]=x; for(inti=1;i<9;i++){ scanf("%d",&x); //共輸入9個數(shù)字 p.d[i]=x; } printf("%d\n",ans[State2I(p)]);//直接查表得到結(jié)果并輸出 }}intmain(){ PreCom(); //預處理 Work(); //處理輸入輸出 return0;}F首先把問題簡化，給定m和n，求出以[0,m]X[0,n]為包含這個零星的最小矩形的菱形的個數(shù)。在這個問題簡化方面，只有兩種情況，如下所示：nnymmx（1）菱形的四個點分別在對角線的四邊上，或者（2）菱形的其中一對對角線定點分點在矩形的一對對角線頂點上。因此我們只需要求出這兩個情況下菱形的個數(shù)即可。在情況1中，設變量x，y，有菱形的四邊長度相等，得到：x2mx-2ny=同理在情況2中，可以得到：x2mx+2ny=上面的兩個方程，都要求x，y為整數(shù)，且0<=x<=m,0<=y<=n，這兩個方程都可以看做是求解ax+by=c，采用擴展歐幾里得算法便可求解，注意當4個點都在矩形上且有兩個點在矩形頂點上會出現(xiàn)重復計算，菱形面積為0的點也應該去掉。這樣先預處理出所有可能的矩形中菱形的個數(shù)，然后離線存儲答案。#include<stdio.h>#include<string.h>#include<stdlib.h>constintmaxn=1001; //矩形最大邊長intf[maxn][maxn]; //以[0,m]×[0,n]為包含菱形的最小矩形的菱形的個數(shù)longlongg[maxn][maxn];//在[0,m]×[0,n]以m,n為邊界的菱形的個數(shù)longlongh[maxn][maxn];//在[0,m]×[0,n]中菱形的個數(shù)//擴展歐基里德算法，返回結(jié)果為最大公約數(shù)d，且ax+by=dintegcd(inta,intb,longlong&x,longlong&y){ longlongk; //臨時變量 intd; //最大公約數(shù) if(b==0) //終止條件 { x=1; //滿足終止條件時x的值 y=0; //滿足終止條件時y的值 returna; //最大公約數(shù)為a } else { d=egcd(b,a%b,x,y); //遞歸求解 k=a/b; k=x-k*y; //臨時變量用于交換兩個數(shù) x=y; //擴展歐基里德算法中，從上一層得到x=y y=k; //擴展歐基里德算法中，從上一層得到y(tǒng)=x-(a/b)*y returnd; //最大公約數(shù)為遞歸求解結(jié)果 }}//計算區(qū)間的上下界voidcal_bound(longlongx,longlongstep,longlong&l,longlong&r,intlb,intrb){ inttemp; if(step<0) //當步長為負數(shù)時，進行鏡像調(diào)整使得步長為正 { x=-x; //x取相反數(shù) step=-step; //步長取相反數(shù) temp=lb; lb=-rb; rb=-temp; //把左右邊界取相反數(shù)并且交換 } //求最小的l使x+l*step>=lb if(lb-x>=0) //左邊界在已知解的右邊 l=(lb-x+step-1)/step; else //左邊界在已知解的左邊 l=(lb-x)/step; //求最大的r使x+r*step<=rb if(rb-x>=0) //右邊界在已知解的右邊 r=(rb-x)/step; else //右邊界在已知解的左邊 r=(rb-x-step+1)/step; return;}//求ax+by=c在lx<=x<=rx且ly<=y<=ry時整數(shù)解的個數(shù)intcal(inta,intb,intc,intlx,intrx,intly,intry){ longlongx,y,dx,dy,l1,r1,l2,r2; intd; d=egcd(abs(a),abs(b),x,y); //使用擴展歐基里德算法 if(c%d!=0) //不存在解的情況 return0; if(a<0) //如果a為負數(shù)，則相應調(diào)整x x=-x; if(b<0) //如果b為負數(shù)，則相應調(diào)整y y=-y; x*=c/d; //求出其中一個解的x值 y*=c/d; //求出其中一個解的y值 dx=b/d; //x的變化步長 dy=-a/d; //y的變化步長 cal_bound(x,dx,l1,r1,lx,rx);//通過x求t的左右邊界 cal_bound(y,dy,l2,r2,ly,ry);//通過y求t的左右邊界 if(l1<l2) //取左邊界的最大值 l1=l2; if(r1>r2) //取右邊界的最小值 r1=r2; returnr1-l1+1; //返回解的個數(shù)}intinit() //預處理函數(shù){ inti,j,temp; for(i=1;i<maxn;i++){ //枚舉矩形的其中一邊長 for(j=1;j<maxn;j++){ //枚舉矩形的另一邊長 temp=cal(2*i,-2*j,i*i-j*j,0,i,0,j);//計算情況(1)的結(jié)果 if(i==j) //當矩形為正方形時，正方形重復計算了一次 temp--; if(temp>0) f[i][j]+=temp; //將合法解累加到f數(shù)組中 temp=cal(2*i,2*j,i*i+j*j,1,i-1,1,j-1);//計算情況(2)的結(jié)果 if(i%2==0&&j%2==0) //減去菱形面積為0的情況 temp--; if(temp>0) f[i][j]+=temp; //將合法解累加到f數(shù)組中 //從f數(shù)組到g數(shù)組的轉(zhuǎn)移方程 g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+f[i][j]; //從g數(shù)組到h數(shù)組的轉(zhuǎn)移方程 h[i][j]=h[i-1][j]+h[i][j-1]-h[i-1][j-1]+g[i][j]; } } return0;}intmain(){ intm,n; init(); //預處理 while(scanf("%d%d",&m,&n)!=EOF){ //輸入整數(shù)m,n直到文件結(jié)束 printf("%I64d\n",h[m][n]); //輸出答案 } return0;}G利用指針建立二叉樹，再進行后續(xù)遍歷。直接構(gòu)造一棵二叉樹即可，可以用最后一層節(jié)點來保存2^N個值，則他們的父親結(jié)點的字符值就已經(jīng)由左右兒子的B,I決定了，故不用保存串，只需要記錄字符值。#include<iostream>#include<cstring>#include<cstdio>#include<cmath>usingnamespacestd;chars1[2]="0",s2[2]="1";chars[1200];structFBI{chars;FBI*lchild,*rchild;};voidshowtree(FBI*head)//后序遍歷樹{if(head==NULL)return;showtree(head->lchild);showtree(head->rchild);printf("%c",head->s);}voidmaketree(FBI*node,char*p,intlen){if(len==1){if(strstr(p,s1)&&strstr(p,s2))node->s='F';elseif(strstr(p,s1)&&!strstr(p,s2))node->s='B';elseif(!strstr(p,s1)&&strstr(p,s2))node->s='I';node->lchild=NULL;node->rchild=NULL;return;}charq[520],*r=newchar;FBI*z=newFBI;strncpy(q,p,len/2);r=p;inti=len/2;while(i--)r++;//將p一分為二q和r兩個字符串if(strstr(q,s1)&&strstr(q,s2))//判斷左兒子的類型z->s='F';elseif(strstr(q,s1)&&!strstr(q,s2))z->s='B';elseif(!strstr(q,s1)&&strstr(q,s2))z->s='I';node->lchild=z;FBI*c=newFBI;if(strstr(r,s1)&&strstr(r,s2))//判斷右兒子的類型c->s='F';elseif(strstr(r,s1)&&!strstr(r,s2))c->s='B';elseif(!strstr(r,s1)&&strstr(r,s2))c->s='I';node->rchild=c;maketree(z,q,len/2);//遞歸構(gòu)建maketree(c,r,len/2);}intmain(){intT;scanf("%d",&T);while(T--){intn;scanf("%d",&n);scanf("%s",&s);if(strlen(s)==1){if(!strcmp(s,"0"))printf("B\n");elseif(!strcmp(s,"1"))printf("I\n");continue;}FBI*head=newFBI;chars1[2]="0",s2[2]="1";if(strstr(s,s1)&&strstr(s,s2))head->s='F';elseif(strstr(s,s1)&&!strstr(s,s2))head->s='B';elseif(!strstr(s,s1)&&strstr(s,s2))head->s='I';maketree(head,s,(int)pow(2.0,(double)n));showtree(head);printf("\n");}return0;}H每讀入一片雪花，就將該雪花進行哈希操作，并判斷哈希表里是否有相同的哈希值，如有相同的哈希值就從鏈表中一一取出并判斷是否同構(gòu)即可。#include<iostream>#include<cstdio>#include<stdlib.h>#include<vector>usingnamespacestd;constintM=90001;//myhash函數(shù)，取余的數(shù)intsnow[100005][6];//存儲雪花信息vector<int>myhash[M];//myhash表，表中存儲的是snow數(shù)組的下標boolisSame(inta,intb)//判斷a與b是否同樣{ for(inti=0;i<6;i++) { //順時針 if((snow[a][0]==snow[b][i]&& snow[a][1]==snow[b][(i+1)%6]&& snow[a][2]==snow[b][(i+2)%6]&& snow[a][3]==snow[b][(i+3)%6]&& snow[a][4]==snow[b][(i+4)%6]&& snow[a][5]==snow[b][(i+5)%6]) ||//逆時針 (snow[a][0]==snow[b][i]&& snow[a][1]==snow[b][(i+5)%6]&& snow[a][2]==snow[b][(i+4)%6]&& snow[a][3]==snow[b][(i+3)%6]&& snow[a][4]==snow[b][(i+2)%6]&& snow[a][5]==snow[b][(i+1)%6])) returntrue; } returnfalse;}intmain(){ freopen("h.out","w",stdout); intT; cin>>T; while(T--){ intok=0; intn; inti,j; cin>>n; for(i=0;i<n;i++) for(j=0;j<6;j++) cin>>snow[i][j]; intsum,key; for(i=0;i<n;i++) { sum=0;//求出雪花六個花瓣的和 for(j=0;j<6;j++) sum+=snow[i][j]; key=sum%M;//求出key //判斷是否與myhash表中myhash[key]存儲的雪花相同 for(vector<int>::size_typej=0;j<myhash[key].size();j++) { if(isSame(myhash[key][j],i))//如相同 { cout<<"Twinsnowflakesfound."<<endl; ok=1; break; } } if(ok){ break; } myhash[key].push_back(i);//若沒找到相同的 } if(ok==0) cout<<"Notwosnowflakesarealike."<<endl; } return0;}I簽到題，直接模擬就好。#include<fstream>#include<cstdio>#include<string>#include<iostream>usingnamespacestd;strings;chara[5005];intp;intmain(){ intT; scanf("%d",&T); while(T--){ inti,len; cin>>s; len=s.size(); for(i=0;i<len;++i) { if(s[i]=='@') p=0; elseif(s[i]=='#'&&p>0) --p; elseif(s[i]!='#') a[++p]=s[i]; } for(i=1;i<=p;++i) cout<<a[i]; cout<<'\n'; } return0;}J本題乍看可以用樹的劃分等比較麻煩的方法去做，但實際上考慮到異或的特殊性質(zhì)，不需要用到這些方法的方法。首先回想我們是如何計算樹上兩點之間的距離的，先分別求出根到這兩點之間的距離，記為l1,l2，根到這兩點的最近公共祖先的距離為lc.那么這兩點距離就是（l1＋l2）-(lc+lc).然后回到原問題，我們要求的是兩點之間的異或距離，同樣先求出根到這兩點的異或距離，記為x1,x2，根到這兩點最近公共祖先距離為xc，那么這兩點的異或距離就是x1⊕x2⊕xc⊕xc,所以異或距離就是x1⊕x2，那么我們只需要直到有多少點對，滿足根分別到他們的異或距離異或后等于K。于是我們把問題轉(zhuǎn)換為一個很簡單的問題，給出N個數(shù)字，問有多少對數(shù)字異或后等于K，枚舉這些數(shù)字，然后統(tǒng)計枚