acm--8.29测试.doc

8.29测试-题号 题目 杭电对应题号1001 彼岸 2569（递推）1002 Eddys picture 1162（最小生成树）1003 Sort it 2689（求逆序数）1004 Common Subsequence 1159（最长公共子序列 简单DP）1005 Move Move Look 1295（算是递推。额，这个水了吧？）1006 Fruit 2152（母函数）1007 Wooden Sticks 1051（典型贪心，结构体排序）1008 How Many Tables 1213（简单并查集）1009 最短路 2544（最短路径，两种算法均可以过）1010 Nightmare 1072（搜索，题目长了些）-HDOJ2569 ( 彼岸 ) 【递推公式】f(n)=2*f(n-1)+f(n-2)f1=3f2=9f3=21f4=51#include int main() int cas,n,i; int seq50; seq1=3; seq2=9; seq3=21; for (i=4;i41;i+) seqi=seqi-1*2+seqi-2; scanf(%d,&cas); while(cas-) scanf(%d,&n); printf(%dn,seqn); return 0;-hdu1162 Eddys picture 【最小生成树】这个题目可以想到最小生成树，关键就是如何将坐标点转化到求解最小生成树上，下面给出一个用避圈法做的/*最小生成树*/#include #include #include #include using namespace std;const int N=10005;double lefttN,righttN;int fatherN,rN;struct point int x,y; double value;aa10005;int cmp(const int i,const int j) return aai.valueaaj.value;int find(int x) if(fatherx!=x) fatherx=find(fatherx); return fatherx;int main() int n; while(scanf(%d,&n)!=EOF) for(int i=0;iN;+i) fatheri=i; ri=i; aai.value=0.0; for(int i=0;in;+i) scanf(%lf%lf,&leftti,&rightti); int k=0; for(int i=0;in;+i) for(int j=0;jn;+j) if(i!=j) aak.value=sqrt(leftti-lefttj)*(leftti-lefttj)+(rightti-righttj)*(rightti-righttj); aak.x=i; aak.y=j; k+; sort(r,r+k,cmp); double sum=0; for(int i=0;ik;+i) int e=ri; int x=find(aae.x); int y=find(aae.y); if(x!=y) sum+=aae.value; fatherx=y; printf(%.2lfn,sum); return 0;-hdu 2689 Sort it 【求逆序数】一个大家普遍会想到的方法，遍历一遍，直接比较，求逆序的个数：#includeusing namespace std;int main() int arr1005; int n; while(scanf(%d,&n)!=EOF) int i,j,sum=0; for(i=0;i!=n;+i) scanf(%d,&arri); for(i=1;i!=n;+i) for(j=0;j!=n-i;+j) if(arrjarrj+1) int temp=arrj; arrj=arrj+1; arrj+1=temp; sum+; coutsumendl; return 0;其实这个也是树状数组的一个用处，可以求序列的逆序数#include #include #define INF0x7f7f7f7f#define MAXSIZE 1010int n ;int treeMAXSIZE ;int lowbit (int x)return x & (-x) ;void add (int pos, int val)while (pos 0)sum += treepos ;pos -= lowbit (pos) ;return sum ;int main ()int i, j ;int x, sum ;while (scanf (%d, &n) != EOF)memset (tree, 0, sizeof (tree) ;sum = 0 ;for (i = 1 ; i = n ; +i)scanf (%d, &x) ;sum += getSum (n) - getSum (x) ;add (x, 1) ;printf (%dn, sum) ;return 0 ;-hdu1159 Common Subsequence 【最长公共子序列 简单DP】课件上有这一道题，但是不知道你们写了没有，这算是动态规划的入门题目，想了解深层的DP还是得从简单的基础来啊。#include#includeusing namespace std;int data500500;string str1,str2;int main() int i,j,n,m; while(cinstr1str2) memset(data,0,sizeof(data); n=str1.length(); m=str2.length(); for(i=0;i=n;+i) data0i=0; for(j=0;j=m;+j) dataj0=0; for(i=1;i=n;+i) for(j=1;jdataij-1?datai-1j:dataij-1; coutdatanmendl; return 0;-hdu1295 Move Move Look 【能算上是递推题么？】代码亮瞎了24K纯金眼。能算得上杭电最简代码么？不管你信不信，我反正信了#includeusing namespace std ;int main() int n ; while(cin n) cout n endl ; return 0 ;-hdu2152 Fruit 【母函数】母函数，其实也就是把你平常解多项式的过程给模拟了一遍，不过用的是三个循环而已#include using namespace std;const int lmax=10000; int c1lmax+1,c2lmax+1,low10000,high10000;int main() int n,i,j,k,N,S,sh; while (cinNS) for (i=0;i=S;i+) c1i=0; c2i=0; for(i=0;ilowihighi; for (i=low0;i=high0;i+) c1i=1; sh=high0; for (i=1;iN;i+) for (j=0;j=sh;j+) for (k=lowi;k=highi;+k) c2j+k+=c1j; for (j=0;j=sh+highi;j+) c1j=c2j; c2j=0; sh+=highi; coutc1Sendl; return 0;-hdu 1051Wooden Sticks 【典型贪心，结构体排序】贪心算法的经典题目，再加上结构体排序的接触，嗯我想你懂的。#includeusing namespace std;struct Wooden int length; int weight;sticks5001;bool flag5001;int cmp(const void *a,const void *b) struct Wooden *c=(Wooden *)a; struct Wooden *d=(Wooden *)b; if(c-length!=d-length) return c-length-d-length; else return c-weight-d-weight;int main() int T,n; int i,j; int minutes,m; cinT; while(T-) minutes=0; memset(flag,false,sizeof(flag); cinn; for(i=0;isticksi.lengthsticksi.weight; qsort(sticks,n,sizeof(sticks0),cmp);/qsort哦 for(i=0;in;+i) if(flagi) continue; m=sticksi.weight; for(j=i+1;j=m) flagj=true; m=sticksj.weight; for(i=0;in;+i) if(!flagi) minutes+; coutminutesendl; return 0;-hdu 1213How Many Tables 【简单并查集】额，这个并查集就不用再说了吧，压缩路径是要体会的，在综合用的时候是会减少查询时间的#include using namespace std;int parent1001;int find(int a) if(parenta0) parenta=find(parenta); return parenta0?parenta:a;void union_set(int x,int y) x=find(x); y=find(y); if(x!=y) if(parentxNM; int i=0; int a=0,b=0; for(i=0;iab; union_set(a,b); int num=0; for(i=1;i=N;+i) if(parenti0) num+; coutnumendl; 当然我还是想然你们从下面的的这个代码了解一下-并查集#include #include int set1005,s,num;void MergeSet(int a,int b) int i; s-; for (i=0;inum;i+)/把所有的set=a的修改为b，相当于更改集合代表元素 if(seti=a) seti=b; int main() int i,n,a,b,f,t,T; scanf(%d,&T); while(T-) scanf(%d%d,&num,&n); s=num; for (i=0;inum;i+)/注意是从0开始的哦 seti=i; for (i=0;in;i+) scanf(%d%d,&a,&b); f=seta-1;/因为是从0开始的 t=setb-1; if(f!=t) MergeSet(f,t); printf(%dn,s); return 0;-hdu2544 最短路 【最短路径，两种算法均可以过】其实还是上次说的，模版上的算法虽然全面，但是对于不同题目来说，要那么多就有点儿画蛇添足了#include#define MAX_N 105int mapMAX_NMAX_N;int main()/ freopen(in.txt,r,stdin); int n,m,i,j,k,a,b,c; while(scanf(%d%d,&n,&m),n|m) for(i=1;i=n;i+) for(j=1;j=n;j+) mapij=100000000; for(i=1;ic) mapab=mapba=c; for(k=1;k=n;k+) for(i=1;in;i+) for(j=1;j=n;j+) if(mapik+mapkjmapij) mapij=mapik+mapkj; printf(%dn,map1n); return 0;-hdu1072 Nightmare【搜索，题目长了些】题目长一些，但是应该能读懂的ho在nm的地图上，0表示墙，1表示空地，2表示人3表示目的地，4表示有炸弹重启器。炸弹的时间是6，人走一步所需要的时间是1,求人从2走到3的最短时间?#include using namespace std; #define inf 0x3fffffff #define M 10 /stepij表示从起点到ij需要的最小步数，Tij表示走到ij诈弹还剩下的时间 int r, c, mins; int mapMM, stepMM, TMM; int x_move4 = -1, 0, 1, 0; int y_move4 = 0, 1, 0, -1; void dfs (int x, int y) if (Txy = 0) /炸死了 return ; if (mapxy = 3) if (stepxy mins) mins = stepxy; return ; for (int i = 0; i 4; i+) int tx = x + x_movei;int ty = y + y_movei; if (tx = r | ty = c) continue;if (maptxty = 0 | steptxty = Txy - 1)continue; /已访问过，而且如果走下去诈弹时间没变甚至变小，那还不如不走呢 steptxty = stepxy + 1;Ttxty = Txy - 1; if (maptxty = 4 & Ttxty 0)Ttxty = 6; /将诈弹时间置为6，按照题意走到txty必须诈弹还有剩余时间，否则还是要爆 dfs (tx, ty); int main() /freopen(in.txt,r,stdin);int t, i, j, sx, sy; scanf (%d, &t); while (t-) scanf (%d %d, &r, &c); for (i = 0; i r; i+)