acm--8.29测试

《acm--8.29测试》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、8.29测试-------------------------------------------------------------------题号题目杭电对应题号1001彼岸2569（递推）1002Eddy'spicture1162（最小生成树）1003Sortit2689（求逆序数）1004CommonSubsequence1159（最长公共子序列简单DP）1005MoveMoveLook1295（算是递推。额，这个水了吧？）1006Fruit2152（母函数）1007WoodenSticks1051（典型贪心，结构体排序）1

2、008HowManyTables1213（简单并查集）1009最短路2544（最短路径，两种算法均可以过）1010Nightmare1072（搜索，题目长了些）--------------------------------------------------------------------HDOJ2569(彼岸)【递推公式】f(n)=2*f(n-1)+f(n-2)f1=3f2=9f3=21f4=51#includeintmain(){intcas,n,i;intseq[50];seq[1]=3;seq[2]=

3、9;seq[3]=21;for(i=4;i<41;i++)seq[i]=seq[i-1]*2+seq[i-2];scanf("%d",&cas);while(cas--){scanf("%d",&n);printf("%d",seq[n]);}return0;}------------------------------------------------------------------------------hdu1162Eddy'spicture【最小生成树】这个题目可以想到最小生成树，关键就是如何将坐标点转化到求解最小

4、生成树上，下面给出一个用避圈法做的/*最小生成树*/#include#include#include#includeusingnamespacestd;constintN=10005;doubleleftt[N],rightt[N];intfather[N],r[N];structpoint{intx,y;doublevalue;}aa[10005];intcmp(constinti,constintj){returnaa[i].value

5、e;}intfind(intx){if(father[x]!=x)father[x]=find(father[x]);returnfather[x];}intmain(){intn;while(scanf("%d",&n)!=EOF){for(inti=0;i

6、;j

7、;father[x]=y;}}printf("%.2lf",sum);}return0;}-----------------------------------------------------------------------------------hdu2689Sortit【求逆序数】一个大家普遍会想到的方法，遍历一遍，直接比较，求逆序的个数：#includeusingnamespacestd;intmain(){intarr[1005];intn;while(scanf("%d",&n)!=EOF)

8、{inti,j,sum=0;for(i=0;i!=n;++i)scanf("%d",&arr[i]);for(i=1;i!=n;++i)for(j=0;j!=n-i;++j)if(arr[j]>arr[j+1]){inttemp=ar