ACM入门题(北大oj).doc

1000#includeint main() int a,b,c; while(scanf(%d%d,&a,&b)!=EOF) c=a+b; printf(%dn,c); 1067#include#include#includeint main() int a,b; while(scanf(%d%d,&a,&b)!=EOF) if(ab) int t=a; a=b; b=t; int k=b-a; int a0=(int)(k*(1+sqrt(5.0)/2); if(a0=a) printf(0n); else printf(1n); 1080#include#includeint a55=5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,-2,-2,-1,-2,-2,5, -1,-3,-4,-2,-1,0;int main() int ca; scanf(%d,&ca); while(ca-) int n,m,i,j,max105105,b105,d105; char s105,c105; scanf(%d%s,&n,s); scanf(%d%s,&m,c); for(i=1;i=n;i+) if(si-1=A) bi=0; if(si-1=C) bi=1; if(si-1=G) bi=2; if(si-1=T) bi=3; for(i=1;i=m;i+) if(ci-1=A) di=0; if(ci-1=C) di=1; if(ci-1=G) di=2; if(ci-1=T) di=3; max00=0; for(i=1;i=n;i+) maxi0=maxi-10+abi4; for(i=1;i=m;i+) max0i=max0i-1+a4di; for(i=1;i=n;i+) for(j=1;jmaxij) maxij=maxi-1j+abi4; if(maxij-1+a4djmaxij) maxij=maxij-1+a4dj; printf(%dn,maxnm); 1013#include#include#include#include#define PI 3.141592653using namespace std;struct point double x; double y;p30005,res30005;int cmp(point p1,point p2) return p1.yp2.y|(p1.y=p2.y&p1.xp2.x);bool ral(point p1,point p2,point p3) if(p2.x-p1.x)*(p3.y-p1.y)=(p2.y-p1.y)*(p3.x-p1.x) return true; return false;double dis(point p1,point p2) return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);int main() int n,m; while(scanf(%d%d,&n,&m)!=EOF) int i,j; for(i=0;in;i+) scanf(%lf%lf,&pi.x,&pi.y); sort(p,p+n,cmp); res0=p0; res1=p1; int top=1; for(i=2;i=0;i-) while(top!=len&ral(restop-1,restop,pi) top-; res+top=pi; double t=0; for(i=0;itop;i+) t=t+dis(resi,resi+1); printf(%.lfn,t+2*PI*m); 1149#include#includeusing namespace std;#define inf 0x5fffffffint a105105,f1005,ct1005,pre205,n,m,q105;int bfs() int flow=inf,qh=0,qe=1,i; memset(pre,-1,sizeof(pre); q1=0; pre0=-1; while(qhqe) int t=q+qh; for(i=1;i0) prei=t; if(atiflow) flow=ati; if(i=n+1) return flow; q+qe=i; return -1;void maxflow() int res=0,ans,t; while(ans=bfs()!=-1) res=res+ans; t=n+1; while(t) aprett-=ans; atpret+=ans; t=pret; printf(%dn,res);int main() while(scanf(%d%d,&m,&n)!=EOF) memset(f,-1,sizeof(f); memset(a,0,sizeof(a); int i,j,k,t; for(i=1;i=m;i+) scanf(%d,&cti); for(i=1;i=n;i+) scanf(%d,&k); for(j=1;j=k;j+) scanf(%d,&t); if(ft!=-1) afti=inf; else a0i=a0i+ctt; ft=i; scanf(%d,&k); ain+1=k; maxflow(); 1157#include#includeint a105105,b105105;int main() int max(int x,int y); int n,m; while(scanf(%d%d,&n,&m)!=EOF) int i,j; for(i=1;i=n;i+) for(j=1;j=m;j+) scanf(%d,&aij); b11=a11; for(i=2;i=m-n+1;i+) if(a1ib1i-1) b1i=b1i-1; else b1i=a1i; for(i=2;i=n;i+) for(j=i;jbij-1) bij=aij; else bij=bij-1; printf(%dn,bnm); 1200#include#includebool flag20000000;int a300;char s20000000;int main() int n,m; while(scanf(%d%d,&n,&m)!=EOF) memset(flag,0,sizeof(flag); scanf(%s,s); int i,j=0,len=strlen(s); memset(a,0,sizeof(a); for(i=0;ilen;i+) asi=1; for(i=0;i256;i+) if(ai=1) ai=j+; int mod=1,res=0; for(i=0;in-1;i+) mod=mod*m; for(i=0;in;i+) res=res*m+asi; flagres=1; for(i=n;ilen;i+) res=res%mod*m+asi; flagres=1; int count=0; mod=mod*m; for(i=0;i=mod;i+) if(flagi=1) count+; printf(%dn,count); 1207#include#includeint main() int b,c,i,j,max=0,k,t,r; while(scanf(%d%d,&b,&c)!=EOF) if(bc) t=b; r=c; else t=c; r=b; max=0; for(i=r;imax) max=j; printf(%d %d %dn,b,c,max); /system(pause);1273#include#include#includeusing namespace std;#define inf INT_MAXint n,m,a205205,pre205,lev205,num205;void bfs() queueQ; memset(lev,-1,sizeof(lev); memset(num,0,sizeof(num); Q.push(n); levn=0; num0=1; while(!Q.empty() int t=Q.front(),i; Q.pop(); for(i=1;i0) levi=levt+1; numlevi+; Q.push(i); int maxflow() int flow=0,i,ans,cur=1; bfs(); while(levcurn) if(cur=n) ans=inf; while(cur!=1) if(aprecurcurans) ans=aprecurcur; cur=precur; cur=n; while(cur!=1) aprecurcur-=ans; acurprecur+=ans; cur=precur; flow=flow+ans; for(i=1;i0&levcur=levi+1) prei=cur; cur=i; break; if(in) levcur=n+1; numlevcur-; if(numlevcur=0) break; for(i=1;i0&levi+1levcur) levcur=levi+1; numlevcur+; if(cur!=1) cur=precur; return flow;int main() while(scanf(%d%d,&m,&n)!=EOF) int i,j; memset(a,0,sizeof(a); for(i=0;im;i+) int b,c,d; scanf(%d%d%d,&b,&c,&d); abc+=d; printf(%dn,maxflow(); 1285#include#includeint num55;unsigned _int64 f5555;int main() int n,m,ct=0; while(scanf(%d%d,&n,&m)!=EOF) if(n=0&m=0) break; int i,j,a,k; memset(num,0,sizeof(num); for(i=0;in;i+) scanf(%d,&a); numa+; memset(f,0,sizeof(f); f00=1; for(i=0;i50;i+) for(j=0;j=50;j+) for(k=0;k=numi+1;k+) fi+1j+k=fi+1j+k+fij; printf(Case %d:n,+ct); for(i=0;im;i+) scanf(%d,&a); printf(%I64dn,f50a); 1364#include #include #include using namespace std;int v105,pre105,w105,h105,flag105,ct105,d105,n,m,num;void add(int a,int b,int c)vnum=b;prenum=ha;wnum=c;ha=num+;bool spfa() int i; queue Q; for(i=0;i=0;i=prei) int p=vi; if(dt+win) return false; return true;int main()while(cinn)if(n=0) break;cinm;int a,b,c;char s3;num=0;memset(flag,0,sizeof(flag);memset(ct,0,sizeof(ct);memset(h,-1,sizeof(h);for(int i=1;iabsc;if(strcmp(s,gt)=0) add(a-1,a+b,-1-c);else add(a+b,a-1,c-1);if(spfa() coutlamentable kingdomendl;else coutsuccessful conspiracyendl;return 0;1384#include#includeint b10005,a6002;int main() int ca; scanf(%d,&ca); while(ca-) int M1,M2,M,n,i,j,value; scanf(%d%d,&M1,&M2); M=M2-M1; scanf(%d,&n); for(i=0;in;i+) scanf(%d%d,&ai0,&ai1); for(i=0;i=M;i+) bi=-1; b0=0; for(i=0;in;i+) for(j=0;j+ai1=M;j+) if(bj!=-1) value=bj+ai0; if(valuebj+ai1|bj+ai1=-1) bai1+j=value; if(bM=-1) printf(This is impossible.n); else printf(The minimum amount of money in the piggy-bank is %d.n,bM); 1473#include#include#include#includeint main() char S300,c300100; int count1=0; while(scanf(%s,S)!=EOF) if(strcmp(S,END)=0) break; int len=strlen(S),i,count=0,j=0,d; for(i=0;ilen;i+) if(Si!=,&Si!=.) ccountj=Si; j+; else ccountj=0; j=0; count+; int nw=0,ne=0,sw=0,se=0,n=0,s=0,e=0,w=0; for(i=0;icount;i+) char cc10; sscanf(ci,%0-9,cc); sscanf(cc,%d,&d); if(strlen(ci)=strlen(cc)+1) if(cistrlen(cc)=N) n+=d; if(cistrlen(cc)=S) s+=d; if(cistrlen(cc)=E) e+=d; if(cistrlen(cc)=W) w+=d; if(strlen(ci)=strlen(cc)+2) if(cistrlen(cc)=N&cistrlen(cc)+1=W) nw+=d; if(cistrlen(cc)=N&cistrlen(cc)+1=E) ne+=d; if(cistrlen(cc)=S&cistrlen(cc)+1=W) sw+=d; if(cistrlen(cc)=S&cistrlen(cc)+1=E) se+=d; double x=e-w+(ne+se-nw-sw)*sqrt(2)/2; double y=n-s+(nw+ne-sw-se)*sqrt(2)/2; double ss=sqrt(x*x+y*y); count1+; printf(Map #%dn,count1); printf(The treasure is located at (%.3lf,%.3lf).n,x,y); printf(The distance to the treasure is %.3lf.n,ss); printf(n); 1505#include#include#includeint a510,s510,t505505,num505,flag505;int ma(int x,int y) if(xy) return y; return x;int main() int ca; scanf(%d,&ca); while(ca-) int n,m,i,j,k,res; scanf(%d%d,&n,&m); for(i=1;i=n;i+) scanf(%d,&ai); s0=0; for(i=1;i=n;i+) si=si-1+ai; for(i=1;in;i+) t1i=si; memset(flag,0,sizeof(flag); for(i=2;im;i+) for(j=i;jn;j+) res=1000000000; for(k=i-1;kma(ti-1k,sj-sk) res=ma(ti-1k,sj-sk); tij=res; res=sn; for(i=m-1;in;i+) if(ma(tm-1i,sn-si)res) res=ma(tm-1i,sn-si); num0=n; for(i=1;im-i;j-) ti=ti+aj; if(tires) break; numi=j; flagj=1; for(i=1;in;i+) if(flagi=0) printf(%d ,ai); else printf(%d / ,ai); printf(%dn,ai); 1511#include#include#include#include#define inf 2000000000using namespace std;int ct,pre1000005,len1000005,v1000005,h1000005,n,m,vis1000005,l1000005;int a1000005,b1000005,c1000005;queue Q;void add(int a,int b,int c) prect=ha; lenct=c; vct=b; ha=ct+;void spfa() int i; memset(vis,0,sizeof(vis); Q.push(1); vis1=1; for(i=1;i=n;i+) li=inf; l1=0; while(!Q.empty() int t=Q.front(); for(i=ht;i!=-1;i=prei) if(lt+lenilvi) lvi=lt+leni; if(visvi=0) visvi=1; Q.push(vi); Q.pop(); vist=0; int main() int ca; scanf(%d,&ca); while(ca-) scanf(%d%d,&n,&m); int i,j; _int64 res=0; ct=0; memset(h,-1,sizeof(h); for(i=0;im;i+) scanf(%d%d%d,&ai,&bi,&ci); add(ai,bi,ci); spfa(); for(i=2;i=n;i+) res=res+li; ct=0; memset(h,-1,sizeof(h); for(i=0;im;i+) add(bi,ai,ci); spfa(); for(i=2;i=n;i+) res=res+li; printf(%I64dn,res); 1609#include#includeint a105105;int main() int n; while(scanf(%d,&n)!=EOF) if(n=0) printf(*n); break; int i,j; for(i=0;i101;i+) for(j=0;j101;j+) aij=0; for(i=0;in;i+) int m,k; scanf(%d%d,&m,&k); amk=amk+1; for(i=1;i101;i+) for(j=1;j=ai-1j) aij=aij+aij-1; else aij=aij+ai-1j; printf(%dn,a100100); 1611#includeusing namespace std;int f30005,cont30005;int findf(int a) if(fa!=a) fa=findf(fa); return fa;void com(int a,int b) int x=findf(a); int y=findf(b); if(x=y) return; if(contx=conty) fx=y; conty=contx+conty; else fy=x; contx=contx+conty; int main() int m,n; while(scanf(%d%d,&n,&m)!=EOF&n) int num,st,i,j,ed; for(i=0;in;i+) fi=i; conti=1; fo