acm入门基础题解一.docx

Problem A: 数字三角形#include#includeconst int maxn=110;int amaxnmaxn,bmaxnmaxn,n;void data_set() for(int i=1;i=n;i+) for(int j=1;j=i;j+) scanf(%d,&aij); void solve() for(int j=1;j=1;i-) for(int j=1;jbi+1j) bij=bi+1j+1+aij; else bij=bi+1j+aij; printf(%dn,b11);int main() while(scanf(%d,&n)!=EOF&n!=0) data_set(); solve(); return 0;Problem B: 去北京看奥运#include#includeconst int maxn=110;const int inf=200000000;int amaxn,bmaxnmaxn,dpmaxnmaxn,n;void data_set() for(int j=0;jmaxn;j+) for(int k=0;kmaxn;k+) dpkj=inf; dp01=0; int s,e,l; scanf(%d,&n); a0=1;an+1=1; for(int i=1;i=n;i+) scanf(%d,&ai); for(int i=0;i=n;i+) for(int j=1;jmaxn;j+) for(int k=1;kmaxn;k+) bkj=inf; while(1) scanf(%d,&s); if(s=0) break; scanf(%d%d,&e,&l); bse=l; for(int j=1;j=ai+1;j+) for(int k=1;kdpik+bkj&bkj!=inf) dpi+1j=dpik+bkj; printf(%dn,dpn+11);int main(void) int t; scanf(%d,&t); while(t-) data_set();Problem C: 计算直线的交点数#include #include using namespace std;int main() int n,tmp; set s21; s0.insert(0); s1.insert(0); for(int i=2;i21;i+) for(int j=0;ji;j+) set:iterator it; for(it=sj.begin();it!=sj.end();it+) tmp=*it+(i-j)*j; si.insert(tmp); while(cinn) set:iterator it; for(it=sn.begin();it!=sn.end();it+) if(it!=sn.begin() cout ; cout*it; coutendl; Problem D: 免费馅饼#include#includeint a10005011;int main() int i, j, n, p, q, x, m; while(scanf(%d, &n)!=EOF) if(n=0) break; m=0; memset(a, 0, sizeof(a); for(i=1;im) m=p; for(i=m;i=0;i-) for(j=0;j0&ai+1j-1x) x=ai+1j-1; if(jx) x=ai+1j+1; aij+=x; printf(%dn, a05); return 0;Problem E: 地道战#include#includeconst int maxn=110;const int inf=200000000;int n,m,amaxnmaxn,rmaxnmaxn,dmaxnmaxn;int min(int a,int b) return ab?a:b;void data_set() for(int i=1;i=n;i+) for(int j=1;jm;j+) scanf(%d,&rij); for(int i=1;i=m;i+) for(int j=1;jn;j+) scanf(%d,&dji); for(int i=0;i=n;i+) for(int j=0;j=m;j+) aij=inf;void solve() a11=0; for(int i=2;i=m;i+) a1i=a1i-1+r1i-1; for(int i=2;i=n;i+) ai1=ai-11+di-11; for(int i=2;i=n;i+) for(int j=2;j=m;j+) aij=min(aij-1+rij-1,ai-1j+di-1j); printf(%dn,anm);int main() while(scanf(%d%d,&n,&m)!=EOF) data_set(); solve(); Problem F: 最长不下降序列#include#include#includeusing namespace std;const int maxn=2000;int i,j,n,t,x,lmax,amaxn,bmaxn;int main() int max; while(scanf(%d,&n)!=EOF) for(i=1;iai; bn=1; lmax=0; for(i=n-1;i=1;i-) max=0; for(j=i+1;j=n;j+) if(aimax) max=bj; bi=max+1; if(bilmax) lmax=bi; coutlmaxendl; return 0;Problem A: Substrings#include#include#includeusing namespace std;bool comp(string str1,string str2) return str1.length()t; while(t-) int n; cinn; int i=0; for(i=0;istri; sort(str,str+n,comp); string:iterator p1; string:iterator p2; string:iterator p0; int ans=0,max=0; for(p1=str0.begin();p1=p1;p2-) string ss1=str0.substr(p1-str0.begin(),p2-p1+1); string ss2; for(string:iterator it=p2;it=p1;it-) ss2+=*it; ans=ss1.length(); int flag=1; for(i=1;in;i+) int x=stri.find(ss1); int y=stri.find(ss2); if(x=-1&y=-1) flag=0; break; if(flag=1&max=ans) max=ans; coutmaxendl; return 0;ProblemB:Calling Extraterrestrial Intelligcn#include#include#include#define N 100005using namespace std;bool no_primN;int m,a,b,p,q;void primetable() int i,j; for(i=3;i317;i+=2) if(no_primi=false) int tmp=i1; for(j=i*i;jN;j+=tmp) no_primj=true; int main() int i,j; primetable(); while(scanf(%d%d%d,&m,&a,&b)&m&a&b) p=q=0; double limit=a*1.0/b; for(i=2;i=m;i+) if(!no_primi&i%2!=0|i=2) for(j=2;j=i&i*j=limit&i*jp*q) /i和j的顺序 p=j; q=i; printf(%d %dn,p,q); return 0;Problem C: 深入浅出学算法028-桥本分数式#include int main() int i,k,g,s; int m1,m2,m3,a10; a1=1;i=1;g=1;s=0; while(1) g=1; for(k=i-1;k0;k-) if(ak=ai) g=0; break; if(i=9 & g=1 & a1a4) m1=a2*10+a3; m2=a5*10+a6; m3=a8*10+a9; if(a1*m2*m3+a4*m1*m3=a7*m1*m2) s+; if(i1) i-; if(ai=9 & i=1) break; else ai+; printf(%dn,s);Problem D: 深入浅出学算法029-素数和环#include#includeint main() int t,i,j,n,k,s,a2000,b1000; while(scanf(%d,&n) for(k=1;k=2*n;k+) bk=0; for(k=3;k=2*n;k+=2) for(t=0,j=3;j=sqrt(k);