本文共 16153 字，大约阅读时间需要 53 分钟。
本文转载自
http://blog.csdn.net/mzx0821
雨纷纷、旧故里草木深、我听闻、你始终一个人、斑驳的城门、盘踞着老树根、石板上回荡的是再等、
—— 永不放弃的Mzx0821
希望全部的同学算法分析都都不会挂科、
注：题库包含卓越班实验题和非卓越班实验题、由于不知道老师会不会考超范围的、
由于OJ数据弱的原因、不保证下面解法的正确性、特别感谢small rabbit贡献的部分答案、
非卓越班实验题汇总
实验一：
249 凸包面积
#include #include #include using namespace std; struct P{ double x,y; P(){} P(double x1,double y1) { x=x1; y=y1; } double add(double a,double b) { return a+b; } P operator + (P p) { return P(add(x,p.x),add(y,p.y)); } P operator - (P p) { return P(add(x,-p.x),add(y,-p.y)); } double det(P p) { return x*p.y-y*p.x; }}; bool cmp(P a,P b){ if(a.x != b.x) return a.x =2 && (s[k-1]-s[k-2]).det(p[i]-s[k-2]) <= 0) k--; s[k++]=p[i]; } int t=k; for(i=n-1;i>=0;i--) { while(k>t && (s[k-1]-s[k-2]).det(p[i]-s[k-2]) <= 0) k--; s[k++]=p[i]; } double ans=0; while(k>=2) { P p1=s[k-1]; P p2=s[k]; P p3=s[0]; ans+=fabs(0.5*(p1.det(p2)+p2.det(p3)+p3.det(p1))); k--; } printf("%.1lf\n",ans); } return 0;}
303 取模 #include #include #include #include
352 合并果子 #include #include #include #include #include #include using namespace std; class MergeFruit{ private: priority_queue
, greater
>q; int n; int x; int sum; public: void Init() { sum=0; } void Scan() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&x); q.push(x); } } void Run() { while(!q.empty()) { int min_1=q.top(); q.pop(); if(q.empty())break; int min_2=q.top(); q.pop(); int ans=min_1+min_2; q.push(ans); sum+=ans; } } void Print() { cout<
< 493 PostOffice #include #include #include using namespace std;int main(){ int n,i,mid,length=0; int pos_x[10005],pos_y[10005]; scanf("%d",&n); for (i=0;i
794 近期对问题 #include #include #include #include using namespace std;#define inf 0x7ffffff struct node{ double x; double y;}a[100001];int temp[100001];bool cmp(node a,node b){ if(a.x != b.x) return a.x >1; double d1=Find(l,mid); double d2=Find(mid+1,r); d=min(d1,d2); int cnt=0; int i,j; for(i=l;i<=r;++i) { if(fabs(a[i].x-a[mid].x) <= d) temp[cnt++]=i; } sort(temp,temp+cnt,cmp1); for(i=0;i
实验二： 76 数字模式的识别 #include #define N 4000001int a[N]={0};int main(){ int n,i,b,x,y; scanf("%d",&n); for(i=0;i x) { x=a[i]; y=i; } } printf("%d\n",y-2000000); return 0;}
254 翻煎饼 #include using namespace std;int s[1000];int main(){ int i,n,k=0; cin>>n; for(i=0l;i >s[i]; for(;n>1;n--) { int max=0,l=0; for(i=0;i max) { max=s[i]; l=i; } } if(l==0) { k+=1; for(i=0;i
342 变位词 #include #include #include using namespace std;int main(){ char s1[1000],s2[1000]; int n,len1,len2; cin>>n; while(n--) { cin>>s1>>s2; len1=strlen(s1); len2=strlen(s2); sort(s1,s1+len1); sort(s2,s2+len2); if(strcmp(s1,s2)==0) cout<<"Yes"<
445 选择问题 #include using namespace std;int main(){ int n,i,j,a[10002],temp,m; cin >> n >> m; for(i=0;i > a[i]; } for(i=0;i a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } cout << a[m-1] << endl; return 0;}
541 排列的字典序问题 #include #include #include using namespace std; #define ll long longint a[55];int t[55];int main(){ int n; ll num[15]; num[1]=1; int i; for(i=2;i<15;++i) num[i]=num[i-1]*i; while(scanf("%d",&n) != EOF) { ll ans=0; int ss=0; int f=-1; for(i=0;i a[j]) count++; } t[i]=count; } for(i=0;i =0;--i) { if(a[i] tt) { vis=i; break; } } printf("%lld\n",ans); for(i=0;i
642 俄式乘法 #include #include int main(){ int n,m; while(scanf("%d%d",&n,&m) != EOF) { bool first=0; int ans=0; while(n) { if(n%2 == 0) { n/=2; m*=2; } else { if(first) printf(" + "); n=(n-1)/2; printf("%d",m); first=1; ans+=m; m=m*2; } } printf(" = %d\n",ans); } return 0;}
实验三： ：http://blog.csdn.net/mzx0821/article/details/41593241
卓越班实验题目汇总
#include #include int a[5000001];int main(){ int n,k; while(scanf("%d%d",&n,&k) != EOF) { int i; for(i=0;i k) r=mid-1; else l=mid+1; } printf("%d\n",ans+1); } return 0;}
956 约瑟夫问题的实现 #include int main(){ int n,m; while(scanf("%d%d",&n,&m) != EOF) { int ans=0; for(int i=2;i<=n;++i) ans=(ans+m)%i; printf("%d",ans+1); } return 0;}
实验二： #include int a,b; int gcd(int a,int b){ return b==0?a:gcd(b,a%b);} int main(){ while(scanf("%d%d",&a,&b) != EOF) { int t=gcd(a,b); a/=t; b/=t; if(a%2 == 1)printf("A\n"); else printf("B\n"); } return 0;}
405 Fibonacci number #include int a[41];int main(){ int n,i; scanf("%d",&n); a[0]=0; a[1]=1; a[2]=1; for(i=3;i<=n;i++) { a[i]=a[i-1]+a[i-2]; } printf("%d\n",a[n]); return 0;}
413 Quick Sort #include #include int a[50005]; void quick_sort(int l,int r,int a[]){ if(l = temp) j--; if(i
414 The Next Permutation #include #include #include using namespace std; char str[1005]; int main(){ int m,n,len; cin>>m; memset(str,0,sizeof(str)); while(m--) { cin>>n>>str; len=strlen(str); if(next_permutation(str,str+len)) cout< <<" "< <
425 Polynomial calculate #include #include int main(){ int n,x; while(scanf("%d%d",&n,&x) != EOF) { int a[22]; for(int i=0;i<=n;++i) { scanf("%d",&a[i]); } if(n == 0) { printf("0\n"); continue; } int sum=a[n]; for(int i=n-1;i>=0;i--) sum=sum*x+a[i]; printf("%d\n",sum); } return 0;}
446 合并排序 #include int a[10005];int b[10005]; void merge(int a[],int l,int mid,int r){ int cnt=0; int i=l; int j=mid+1; while(i<=mid && j <= r) { if(a[i] < a[j]) { b[cnt++]=a[i++]; } else b[cnt++]=a[j++]; } while(i<=mid) b[cnt++]=a[i++]; while(j<=r) b[cnt++]=a[j++]; int t=0; for(int i=l;i<=r;++i) a[i]=b[t++]; } void hebing(int l,int r,int a[]){ int mid=(l+r)/2; if(l
480 Locker doors #include #include #include int a[100005];int main(){ for(int i=1;i <= 100000;++i) { int t=sqrt((double)i); if(t*t == i) a[i]=1; a[i]+=a[i-1]; } int n; while(scanf("%d",&n) != EOF) { printf("%d\n",a[n]); } return 0;}
641 The Dutch flag problem #include char str[500005]; int main(){ int numR,numB,numW; int n; while(scanf("%d",&n) != EOF) { numR=numB=numW=0; scanf("%s",str); for(int i=0;str[i];++i) { if(str[i] == 'W') numW++; else if(str[i] == 'B') numB++; else if(str[i] == 'R') numR++; } for(int i=0;i
411 售货员的难题 #include #include #define inf 0x3f3f3f3fint dp[21][1<<20];int map[25][25];int n;int min(int a,int b){ return a
a:b; } int solve() { int i,j,k; int st=1<<(n+1); for(i=0;i<=n;++i) for(j=0;j<st;++j) dp[i][j]=inf; dp[0][1]=0; for(i=1;i<st;++i) { for(j=0;j<=n;++j) { if((i&(1<<j)) == 0) continue; for(k=0;k<=n;++k) { if((i&(1<<k)) == 0) dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+map[j][k]); } } } return dp[n][st-1]; } int main() { while(scanf("%d",&n) != EOF) { int i,j; for(i=0;i<n;++i) { for(j=0;j<n;++j) scanf("%d",&map[i][j]); map[i][n]=map[i][0]; } int ans=solve(); printf("%d\n",ans); } return 0; }
572 Boyer–Moore–Horspool algorithm #include #include char str1[200005];char str2[800005];int next[800005]; void getnext(int len){ int j,k; j=0,k=-1; next[0]=-1; while(j =len1) return i-len1; return -1;} int main(){ while(scanf("%s%s",str1,str2) != EOF) { int len1=strlen(str1); int len2=strlen(str2); int ans=kmpindex(len1,len2); printf("%d\n",ans); } return 0;}
649 NBA Finals #include #include #include using namespace std; float dp[505][505]; int main(){ int n; float p,q; while(cin>>n>>p) { q=1-p; memset(dp,0,sizeof(dp)); float ans=0; for(int i=0;i<=n;i++) dp[0][i]=1; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { dp[i][j]=dp[i-1][j]*p+dp[i][j-1]*q; } } cout<
680 Jack Straws #include #include #define MAX_N 13 #define MAXV(x, y) ((x) >= (y) ?
(x) : (y)) #define MINV(x, y) ((x) <= (y) ? (x) : (y)) using namespace std; int num; struct node { int x1, y1, x2, y2; }data[MAX_N + 1]; int set[MAX_N + 1]; int rank[MAX_N + 1]; //推断第3个点在1,2点构成的线短的哪个方向, -1: 逆时针方向, 1: 顺时针方向 int direct(int x1, int y1, int x2, int y2, int x3, int y3) { return (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1); } //推断第3个点是否在1,2点构成的线短上 bool onLine(int x1, int y1, int x2, int y2, int x3, int y3) { return (MINV(x1, x2) <= x3 && x3 <= MAXV(x1, x2) && MINV(y1, y2) <= y3 && y3 <= MAXV(y1, y2)); } //推断点1,2构成的线短与点3,4构成的线短是否相交 bool intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { int d1 = direct(x3, y3, x4, y4, x1, y1); int d2 = direct(x3, y3, x4, y4, x2, y2); int d3 = direct(x1, y1, x2, y2, x3, y3); int d4 = direct(x1, y1, x2, y2, x4, y4); if(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return true; if(d1 == 0 && onLine(x3, y3, x4, y4, x1, y1)) return true; else if(d2 == 0 && onLine(x3, y3, x4, y4, x2, y2)) return true; else if(d3 == 0 && onLine(x1, y1, x2, y2, x3, y3)) return true; else if(d4 == 0 && onLine(x1, y1, x2, y2, x4, y4)) return true; else return false; } int find(int pos) { if(pos != set[pos]) set[pos] = find(set[pos]); return set[pos]; } void joinSet(int pos1, int pos2) { if(pos1 == pos2) return; int pre1 = find(pos1); int pre2 = find(pos2); if(pre1 == pre2) return; else { int rank1 = rank[pre1]; int rank2 = rank[pre2]; if(rank1 < rank2) set[pre1] = pre2; else if(rank1 > rank2) set[pre2] = pre1; else { rank[pre1]++; set[pre2] = pre1; } } } void init() { int i; for(i = 1; i <= num; i++) { set[i] = i; rank[i] = 0; } } int main() { int i, n1, n2, pre1, pre2; while(cin>>num && num != 0) { for(i = 1; i <= num; i++) cin>>data[i].x1>>data[i].y1>>data[i].x2>>data[i].y2; init(); for(n1 = 1; n1 <= num; n1++) { for(n2 = n1; n2 <= num; n2++) { pre1 = find(n1); pre2 = find(n2); if(pre1 == pre2) continue; else { if(intersect(data[n1].x1, data[n1].y1, data[n1].x2, data[n1].y2, data[n2].x1, data[n2].y1, data[n2].x2, data[n2].y2)) joinSet(n1, n2); } } } while(cin>>n1>>n2 && !(n1 == 0 && n2 == 0)) { pre1 = find(n1); pre2 = find(n2); if(pre1 == pre2) cout<<"CONNECTED"<<endl; else cout<<"NOT CONNECTED"<<endl; } } return 0; }
410 尼克的任务 #include #include using namespace std;int main(){ int p[10005][20], dp[10005]; int Time, N; int s, len; while(cin>>Time>>N) { memset(p, 0, sizeof(p)); memset(dp, 0, sizeof(dp)); for (int i = 0; i < N; i++) { cin>>s>>len; p[s][0]++; p[s][p[s][0]] = len; } for (int i = Time; i >= 1; i--) { if (p[i][0] == 0) { dp[i] = dp[i + 1] + 1; } else if (p[i][0] == 1) { dp[i] = max(dp[i + p[i][1]], dp[i]); } else { for (int j = 1; j <= p[i][0]; j++) { dp[i] = max(dp[i], dp[i + p[i][j]]); } } } cout< <
544 跑跑卡丁车 #include #include #include #include using namespace std;#define INF 0x73737373int a[10010], b[10010], dp[10010][15];void input(int L, int N, int a[]){ for(int i = 1; i <= L; i++) { scanf("%d", &a[i]); for(int j = 1; j < N; j++) a[i + j * L] = a[i]; }}int main(){ int L, N; while(~scanf("%d%d", &L, &N)) { input(L, N, a); input(L, N, b); for(int i = 0; i <= L * N; i++) for(int j = 0; j < 15; j++) dp[i][j] = INF; dp[0][0] = 0; for(int i = 1; i <= L * N; i++) { for(int j = 0; j < 15; j++) { if(j != 0)dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a[i]); if(j == 10) dp[i][j] = min(dp[i][j], dp[i-1][14] + a[i]); if(j < 10)dp[i][j] = min(dp[i][j], dp[i-1][j+5] + b[i]); } } int ret = INF; for(int i = 0; i < 15; i++) ret = min(dp[L * N][i], ret); printf("%d\n", ret); } return 0;}
679 Secret Code #include #include #include using namespace std;typedef long long LL;const int maxn=110;LL xr,xi,br,bi,num;LL flag,t;LL ans[maxn];//保存枚举的aivoid dfs(LL rr,LL ii,LL step){ LL x,y,i; if (step>100)return; if(flag)return; if(rr==0&&ii==0) { flag=1; t=step; return; } for(i=0;i*i =0;i--) printf(",%lld",ans[i]); printf("\n"); } } return 0;}
698 Independent Task Scheduling #include int main(){ float x1,x2,x3,y1,y2,y3; float s; while(scanf("%f%f%f%f%f%f",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF) { s=(x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1)/2.0; if(s<0)s=-s; printf("%.1f\n",s); } return 0;}
1080 单纯行法 明明叫做单纯形法好么。 。
。数学渣、不会做、等有空问下理学院的同学怎么搞、
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5175271.html，如需转载请自行联系原作者