北京大学国际大学生程序竞赛的经典题目的代码和思路.docx
- 文档编号:34772
- 上传时间:2023-04-28
- 格式:DOCX
- 页数:105
- 大小:41.29KB
北京大学国际大学生程序竞赛的经典题目的代码和思路.docx
《北京大学国际大学生程序竞赛的经典题目的代码和思路.docx》由会员分享,可在线阅读,更多相关《北京大学国际大学生程序竞赛的经典题目的代码和思路.docx(105页珍藏版)》请在冰点文库上搜索。
北京大学国际大学生程序竞赛的经典题目的代码和思路
ACM代码总结
经过了一段时间的努力,我再Pku上也算是有了一个阶段性的总结拉,下面是我就这段时间搞ACM来的一些代码的总结,具体的一些题目类型的总结看本Blog的相关文章。
huicpc26ACM_PKU代码总结
1、DP(动态规划)
/*1080-HumanGeneFunctions.cpp*/
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,
则整个解分值变大,与已知的最优矛盾。
所以左边部分的分值必是最大。
同理,右边也是。
可见满足最优子结构的性质。
考虑使用DP:
设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。
考虑一个f[i,j],我们有:
1.s1取第i个字母,s2取“-”:
f[i-1,j]+score[s1[i],''-'']
2.s1取“-”,s2取第j个字母:
f[i,j-1]+score[''-'',s2[j]]
3.s1取第i个字母,s2取第j个字母:
f[i-1,j-1]+score[s1[i],s2[j]]
即f[i,j]=max(f[i-1,j]+score[s1[i],''-''],f[i,j-1]+score[''-'',s2[j]],f[i-1,j-1]+score[s1[i],s2[j]]);
然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1]=f[0,0]+score[s1[i],s2[j]],明显有f[0,0]=0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j]=f[0,j-1]+table[''-'',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0]=f[i-1,0]+table[s1[i],''-'']来计算。
至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。
所谓划分阶段也就是为了达到这个目的。
这样我们使用一个二重循环就可以了。
*/
#include
#include
#include
usingnamespacestd;
#defineMAX(a,b,c)(a>b?
a:
b)>c?
(a>b?
a:
b):
c
intctoi(chara){
intb;
if(a==''A'')b=0;
if(a==''C'')b=1;
if(a==''G'')b=2;
if(a==''T'')b=3;
if(a==''-'')b=4;
returnb;
}
intmain()
{
intt,j,k,m,n;
intf1,f2,f3;
intf[101][101];
intarr[5][5]={{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}};
stringa,b;
cin>>t;
while(t--){
j=k=0;
memset(f,0,sizeof(f));
cin>>m>>a;
cin>>n>>b;
for(j=0;j<=m;j++)
{
for(k=0;k<=n;k++)
{
if(j==0&&k==0)
{
f[j][k]=0;
}
elseif(j==0)
{
f[j][k]=f[j][k-1]+arr[ctoi(''-'')][ctoi(b[k-1])];
}
elseif(k==0)
{
f[j][k]=f[j-1][k]+arr[ctoi(a[j-1])][ctoi(''-'')];
}
else
{
f1=f[j-1][k]+arr[ctoi(a[j-1])][ctoi(''-'')];
f2=f[j][k-1]+arr[ctoi(''-'')][ctoi(b[k-1])];
f3=f[j-1][k-1]+arr[ctoi(a[j-1])][ctoi(b[k-1])];
f[j][k]=MAX(f1,f2,f3);
}
}
}
cout<}
return0;
}
2、/*1088-滑雪.cpp*/
#include
usingnamespacestd;
constinthighest=100000;
inthigh[100][100];
booltravel[100][100];
intvalue[100][100];
intr,c;
constintdir[4][2]={0,1,1,0,-1,0,0,-1};
intfind_rout(intx,inty){
inti,temp;
if(x<0||y<0||x>=r||y>=c)
return0;
if(travel[x][y])
returnvalue[x][y];
intmax_rout=1;
for(i=0;i<4;++i){
if(high[x][y]>high[x+dir[i][0]][y+dir[i][1]])
{
temp=find_rout(x+dir[i][0],y+dir[i][1]);
if(max_rout max_rout=temp+1; } } travel[x][y]=true; value[x][y]=max_rout; returnmax_rout; } intmain(){ cin>>r>>c; inti,j; intmax_rout=1; for(i=0;i for(j=0;j travel[i][j]=false; cin>>high[i][j]; } for(i=0;i for(j=0;j inttemp=find_rout(i,j); if(temp>max_rout) max_rout=temp; } cout< return0; } 3、精度运算 /*2262-Goldbach''sConjecture.cpp*/ #include #include voiddoRun(){ inti,j,sum,a; longt; while(cin>>a){ t=0; if(a==0||a>10000) break; sum=0; i=1; while (1){ sum+=i; if(sum>=a){ t=a-(sum-i); break; } i++; } t=t*i; for(j=1;jt+=j*j; } cout if(a>b){ n=a; a=b; b=n; } s=0; for(i=a;i<=b;i++){ count=1; temp=i; while(temp! =1){ if(temp%2==1)temp=3*temp+1; elsetemp=temp/2; count++; } if(count>s)s=count; } printf("%ld\n",s); } } intmain(){ doRun(); return0; } 5、/*2080-Calendar.cpp*/ #include #include usingnamespacestd; intmday[2][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,0,31,29,31,30,31,30,31,31,30,31,30,31}; charweek[7][20]={"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"}; intmain() { intn; ints,y,m,d,t; while (1){ cin>>n; if(n<0) break; d=n%7; n++; for(y=s=0;s if(y%400==0||y%4==0&&y%100) t=366; else t=365; y--;s-=t;n-=s; cout< t-=365; for(m=0,s=0;s cout< (2)< s-=mday[t][m];n-=s; cout< (2)< cout< } return0; } 6、/*1298-TheHardestProblemEver.cpp*/ #include #include usingnamespacestd; voidmain() { stringS1("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); stringS2("VWXYZABCDEFGHIJKLMNOPQRSTU"); stringstart,end,over("ENDOFINPUT"); stringstr; charch; inti,j; while (1) { getline(cin,start); if(pare(over)==0)break;/* while((ch=getchar())! =''\n'') { if(ch<=''Z''&&ch>=''A'') { j=S1.find(ch); ch=S2[j]; } cout<} cout for(i=0;i{ if(str[i]<=''Z''&&str[i]>=''A'') { j=S1.find(str[i]); str[i]=S2[j]; } } cout } } 7、/*1745-Divisibility.cpp*/ #include #include intd[105],e[105],a,n,k; intmain() { inti,p,q; scanf("%d%d",&n,&k); memset(d,0,k*sizeof(int)); scanf("%d",&a); a=a%k; if(a<0)a+=k; d[a]=1; while(--n) { scanf("%d",&a); p=a%k; q=(-a)%k; if(p<0)p+=k; if(q<0)q+=k; memset(e,0,k*sizeof(int)); for(i=0;i { if(d[i]==1) { e[p%k]=e[q%k]=1; } } memcpy(d,e,k*sizeof(int)); } printf(d[0]? "Divisible\n": "Notdivisible\n"); return0; } 8、/*2249-BinomialShowdown.cpp*/ #include #include usingnamespacestd; intmain() { intn,k; doubletemp; while(cin>>n>>k) { if(n==0&&k==0)break; else { temp=1; if(n-k>k) { for(inti=n-k+1;i<=n;++i) temp*=i; for(intj=1;j<=k;++j) temp/=j; cout<} else { for(inti=k+1;i<=n;++i) temp*=i; for(intj=1;j<=n-k;++j) temp/=j; cout<} } } } 9、/*2309-BST.c*/ #include voiddoRun() { intn; longlongi,j,k,s; longlonga; scanf("%d",&n); for(i=0;i{ scanf("%I64d",&a); s=a; if((s&1)==1) printf("%I64d%I64d\n",s,s); else { j=0; while (1) { if((s&1)==1) break; s>>=1; j++; } k=1; k<<=j; printf("%I64d%I64d\n",a-k+1,a+k-1); } } } intmain() { doRun(); return0; } 10、/*1767-WhichisNext.cpp*/ #include #include #include usingnamespacestd; longNextTreeIdentify(stringt) { strings,t2,t001("001"); s=t; longres; intnode,i,posof0,posof001; boolend=true; for(i=0;i<=s.size()-3;i++) { t2=s.substr(i,3); if(pare(t001)==0) { posof001=i; break; } } end=true; for(i=posof001+3;i{ if(s[i]! =''1'') { end=false; break; } } if(! end) { /*s.erase(posof001+1,2); posof0=s.find_first_of("0",posof001+1); s.insert(posof0+1,"1"); s.insert(posof0+1,"0");*/ s.replace(posof001,3,"0"); posof0=s.find_first_of("0",posof001+1); s.replace(posof0,1,"001"); } else { s[0]=''0''; for(i=1;i{ if(i%2==0) s[i]=''1''; else s[i]=''0''; } } i=s.size()-1; res=0; while(i>=2) { node=s[i]-''0''; if(node==1) res+=node } returnres; } voiddoRun() { longres,n,t; intnode; stacktree; strings; scanf("%ld",&n); if(n==0||n==4) { res=n; } else { t=n; while (1) { node=t%2; tree.push(node); if(t<=1)break; t>>=1; } if(tree.size()>30) return; while(! tree.empty()) { s.insert(0,(char*)(tree.top()+''0'')); tree.pop(); } res=NextTreeIdentify(s); } printf("%ld\n",res); } intmain() { doRun(); return0; } 11、/*2229-Sumsets.cpp*/ #include #defineM1000001 intb[M]; voiddoRun() { inti; b[1]=1; b[2]=2; n=0; for(i=2;i{ b[i]=b[i++-1]; b[i]=(b[i-2]+b[i/2])%1000000000; } while(scanf("%d",&i)! =EOF) printf("%d\n",b[i]); } intmain() { doRun(); return0; } 12、/*2533-LongestOrderedSubsequence.c*/ #include voidprocess(int*a,intsum) { inti,j; intf[1000],res,max; for(i=1;i<=sum;i++) f[i]=0; res=0; for(i=sum;i>0;i--) { max=0; for(j=i+1;j<=sum;j++) { if(a[j]>a[i]) { if(max{ max=f[j]; } } } f[i]=max+1; if(res{ res=f[i]; } } printf("%d",res); } main() { intsum; inta[1000]; inti; scanf("%d",&sum); for(i=1;i<=sum;i++) scanf("%d",a+i); process(a,sum); return0; } 13、/*2545-HammingProblem.c*/ #include #include #include intisPrime(longlonga) { intflag=1; longlongi; for(i=2;i{ if(a%i==0&&a! =2) { flag=0; break; } } returnflag; } longlonggetMin3(longlonga,longlongb,longlongc) { longlongt=a>b? b: a; returnt>c? c: t; } longlonggetNum(longlonga,longlongb,longlongc,longlongpos) { longlongp[3],i,j,count=1; longlongtemp[3]={0},min; longlong*num=(longlong*)malloc((pos+2)*sizeof(longlong)); p[0]=a;p[1]=b;p[2]=c; num[0]=1; count=1; while(count! =pos+1) { for(i=0;i<3;i++) { for(j=0;j{ temp[i]=num[j]*p[i]; if(temp[i]>num[count-1]) break; } } min=getMin3(temp[0],temp[1],temp[2]); num[count]=min; count++; } min=num[pos]; returnmin; } intmain() { longlongp1,p2,p3,i; scanf("%I64d%I64d%I64d%I64d",&p1,&p2,&p3,&i);\ if(isPrime(p1)==0||isPrime(p2)==0||isPrime(p3)==0||p1==p2||p2==p3||p1==p3) return1; printf("%I64d",getNum(p1,p2,p3,i)); getchar(); return0; } 14、/*2567-CodetheTree.cpp*/ #include #include usingnamespacestd; structnode { intparent; intchild[51]; intdu; }nd[51]; voiddoRun() { inti,j,k,len,temp,root; chars[256],b[2]; stacksp; intp[51]; while(gets(s)! =NULL) { for(i=0;i<51;i++) { nd[i].du=1; nd[i].parent=0; for(j=0;j<51;j++) nd[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京大学 国际 大学生 程序 竞赛 经典 题目 代码 思路
![提示](https://static.bingdoc.com/images/bang_tan.gif)