OJ算法题已AC
在刷OJ题时遇到了一个题，无论怎么优化，仍然超时， 最后把输出语句换成了append()； 如下：
[java] view plain copy
- <span style="font-size:24px;">StringBuilder sb = new StringBuilder();
- for (Student std : students) {
- sb.append(std.num).append(" ").append(std.name).append(" ").append(std.grade).append("\n");
- // System.out.printf(std.num + " " + std.name + " " +std.grade);
- // System.out.println();
- }
- System.out.print(sb);</span>
append()最大用途是当需要大量的字符串拼接时使用 优点效率比+=要高很多 （+=内存中是相当于创建副本重新赋值，StringBuffer是指针的引用） 运行时间由>3000ms变成了1700ms，困扰了好久......
n：1 0 0 2 10 4 40 92 352 724 2680 14200 73712 365596
3: 0 0 4 6 0 0 12 40 0 0 171 410 0 0 1896 5160 0 0 32757 59984 0 0 431095 822229 0 0 0
Ambiguous operators need parentheses 不明确的运算需要用括号括起
Ambiguous symbol 'xxx' 不明确的符号
Argument list syntax error 参数表语法错误
Array bounds missing 丢失数组界限符
Array size toolarge 数组尺寸太大
Bad character in paramenters 参数中有不适当的字符
Bad file name format in include directive 包含命令中文件名格式不正确
Bad ifdef directive synatax 编译预处理ifdef有语法错
Argument list syntax error
Array bounds missing 丢失数组界限符
Bad character in paramenters 参数中有不适当的字符
Bad undef directive syntax 编译预处理undef有语法错
1331 是否可达、keda
#include<stdio.h> #include<string.h> int cnt; int head[1000]; int n; struct node { int v; int net; }Eg[1000]; void build(int from,int to) { Eg[cnt].v=to;Eg[cnt].net=head[from];head[from]=cnt++; } int main() { int e,t,i,j,x,y,fa,que[1000],book[500][500],qhead,qtail; while(scanf("%d%d",&n,&e)!=EOF) { memset(head,-1,sizeof(head)); for(i=1;i<=e;i++) { scanf("%d%d",&x,&y); build(x,y); } scanf("%d",&t); for(i=1;i<=t;i++) { fa=0; memset(book,0,sizeof(book)); scanf("%d%d",&x,&y); if(x==y) { printf("yes\n"); continue; } qhead=qtail=1; que[qtail]=x; qtail++; while(qhead<qtail) { for(j=head[que[qhead]];j!=-1;j=Eg[j].net) { if(book[que[qhead]][Eg[j].v]==0) { book[que[qhead]][Eg[j].v]=1; que[qtail]=Eg[j].v; qtail++; } if(Eg[j].v==y) { fa=1; break; } } if(fa==1) break; qhead++; } if(fa==1) printf("yes\n"); else printf("no\n"); } printf("\n"); } return 0; }
1351 二分查找、erfen
#include <stdio.h> #include <stdlib.h> void search(int M[],int key,int len){ int mid,low = 0,high = len-1; while(low <= high){ mid = (low+high)/2; if(M[mid] == key){ printf("%d\n",mid); return; }else if(M[mid] > key){ high = mid-1; }else{ low = mid+1; } } printf("Not Found\n"); } int main(){ int m,n,i; int *M = (int *)malloc(sizeof(int)*m); int *N = (int *)malloc(sizeof(int)*n); scanf("%d",&m); for(i = 0;i < m;i++){ scanf("%d",&M[i]); } scanf("%d",&n); for(i = 0;i < n;i++){ scanf("%d",&N[i]); } for(i = 0;i < n;i++){ search(M,N[i],m); } return 0; }
1360 快速排序、kuaipai
#include <stdio.h> #include <stdlib.h> int n; int *N = NULL; void display(){ for(int i = 0;i < n;i++){ printf("%d ",N[i]); } printf("\n"); } void quicksort(int begin,int end){ int i,j,root = N[begin]; if(begin < end){ i = begin; j = end; while(i < j){ while(i < j){ if(root > N[j]){ N[i] = N[j]; break; }else{ j--; } } while(i < j){ if(root < N[i]){ N[j] = N[i]; break; }else{ i++; } } } N[i] = root; display(); quicksort(begin,i-1); quicksort(j+1,end); } } int main(){ scanf("%d",&n); N = (int *)malloc(sizeof(int)*n); for(int i = 0;i < n;i++){ scanf("%d",&N[i]); } quicksort(0,n-1); }
1567 中位数、zhongwei
#include <stdio.h> #define MAX 100001 int a[MAX],b[MAX]; int main(){ int n,i,j,goal; scanf("%d",&n); getchar(); for(i = 0;i < n;i++){ scanf("%d",&a[i]); } for(i = 0;i < n;i++){ scanf("%d",&b[i]); } i = 0; j = 0; while(n--){ if(a[i] >= b[j]){ goal = b[j++]; }else{ goal = a[i++]; } } printf("%d\n",goal); return 0; }
1901 最长公共子序列、zuichang
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 1001 int dp[MAX][MAX]; char str1[MAX],str2[MAX]; int sequenceLength(){ int i,j; int len1 = strlen(str1); int len2 = strlen(str2); int len = len1 > len2 ? len1 : len2; for(i = 0;i <= len;i++){ dp[0][i] = 0; dp[i][0] = 0; } for(i = 1;i <= len1;i++){ for(j = 1;j <= len2;j++){ if(str1[i-1] == str2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]; } } } return dp[len1][len2]; } int main(){ int T; scanf("%d",&T); getchar(); while(T--){ gets(str1); gets(str2); printf("%d\n",sequenceLength()); } return 0; }
1923 符号三角形问题、sanjiao #include <stdio.h> #include <stdlib.h> #define MAX 26 unsigned char p[MAX][MAX]; int n,half,c,sum; void Cal(int t){ int i,j; if(t > n){ sum++; }else{ for(i=0;i<2;++i){ p[1][t]=i; c+=i; for(j=2;j<=t;++j){ p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; c+=p[j][t-j+1]; } if((c<=half)&&(t*(t+1)/2-c<=half)){ Cal(t+1); } for(j=2;j<=t;++j){ c-=p[j][t-j+1]; } c-=i; } } } int main(){ int T,t=1; scanf("%d",&T); while(T--){ scanf("%d",&n); half=n*(n+1)/2; c=0; sum=0; if(half%2==0){ half/=2; Cal(1); } printf("Case %d: %d\n",t++,sum); } return 0; } 1924 n后问题、nhou #include <stdio.h> #include <stdlib.h> #define MAX 15 int n; int x[MAX]; int sum; int place(int k){ if(k==1) return 1; else{ for(int i=1;i<k;i++){ if((abs(k-i)==abs(x[k]-x[i]))||(x[k]==x[i])) return -1; } return 1; } } void backtrack(int t){ if(t>n) sum++; else{ for(int i=1;i<=n;i++){ x[t]=i; if(place(t)==1) backtrack(t+1); } } } int main(){ int T; scanf("%d",&T); getchar(); while(T--){ sum=0; scanf("%d",&n); backtrack(1); printf("%d\n",sum); } return 0; } 1925 最大团、tuan #include <stdio.h> #include <stdlib.h> typedef struct node{ int **a,*x,*bestx; int n,m,cn,bestn; }Node; void backTrack(Node *node,int i){ if (i > node->n){ for (int j = 1; j <= node->n; j++){ node->bestx[j] = node->x[j]; } node->bestn = node->cn; return; } bool OK = true; for (int j = 1; j < i; j++) if (node->x[j]==1&&node->a[i][j]==0){ OK = false; break; } if (OK){ node->x[i] = 1; node->cn++; backTrack(node,i+1); node->cn--; } if (node->cn + node->n - i >= node->bestn){ node->x[i] = 0; backTrack(node,i+1); } } int maxClique(int **a, int v[], int n){ Node *node = (Node *)malloc(sizeof(Node)); int *temp = (int *)malloc(sizeof(int)); node->x = temp; node->a = a; node->n = n; node->cn = 0; node->bestn = 0; node->bestx = v; backTrack(node,1); return node->bestn; } int main(){ int T,t,i,j,n,m,x,y; scanf("%d",&T); while(T--){ t=1; scanf("%d",&n); scanf("%d",&m); int *v = (int *)malloc(sizeof(int)*(n+1)); int **a = (int **)malloc(sizeof(int *)*(n+1)); for(i = 0;i <= n;i++){ a[i] = (int *)malloc(sizeof(int)*(n+1)); } for(i = 0;i <= n;i++){ for(j = 0;j <= n;j++){ a[i][j]=0; } } for(i = 1;i <= m; i++){ scanf("%d",&x); scanf("%d",&y); a[x][y]=1; a[y][x]=1; } printf("Case %d: %d\n",t++,maxClique(a,v,n)); } return 0; }
1927 旅行售货员问题、lvxing
#include<stdio.h> #include<string.h> struct citys{ int t; int w; int p; }; struct citys a[105]; int n, m, b[15], minn, num; void dfs(int z, int ww){ if(z==n&&(num<minn||minn==-1)){ minn=num; return; } else{ int i; for(i=0;i<m;i++){ if(a[i].t==ww&&b[ww]==0&&b[a[i].w]==0){ b[ww]=1; num+=a[i].p; dfs( z+1, a[i].w ); num-=a[i].p; b[ww]=0; }else if(a[i].w==ww&&b[ww]==0&&b[a[i].t]==0){ b[ww]=1; num+=a[i].p; dfs( z+1, a[i].t ); num-=a[i].p; b[ww]=0; }else if(z==n-1&&b[ww]==0&&((a[i].w==1&&a[i].t==ww)||(a[i].t==1&&a[i].w==ww))){ num+=a[i].p; b[ww]=1; dfs( z+1, 1 ); b[ww]=0; num-=a[i].p; } } } } int main(){ int T, item=1; scanf("%d",&T); while(T--){ minn=-1; num=0; memset(b, 0 , sizeof(b)); scanf("%d%d",&n,&m); int x, y; for(int i=0;i<m;i++){ scanf("%d%d%d",&x,&y,&a[i].p); if(x<y){ a[i].t=x; a[i].w=y; } else{ a[i].t=y; a[i].w=x; } } dfs( 0 , 1 ); printf("Case %d: %d\n", item++, minn); } return 0; }
1930 主元素、zhu
#include <stdio.h> #include <stdlib.h> #include <time.h> int x; int t[100001]; bool majority2(int n){ int i=rand()%n+1; x=t[i]; int k=0; for(int j=1;j<=n;j++){ if(t[j]==x) k++; } return (k>n/2); } bool majority1(int n){ if(majority2(n)){ return true; }else{ return majority2(n); } } int main(){ int T,i; srand((int)time(0)); scanf("%d",&T); while(T--){ int n; scanf("%d",&n); for(i = 1;i <=n ;i++){ scanf("%d",&t[i]); } if(majority1(n)){ printf("%d\n",x); }else{ printf("no\n"); } } }
1940 用DFS计算pre和post、jisuan
#include<stdio.h> #include<malloc.h> #define MAX 1000 struct Node{ int flag,v,pre,post; struct Node *next; }; int clock; struct Node node[MAX+1]; void explore(int i){ if(node[i].flag==-1) return; node[i].flag=-1; node[i].pre=clock; clock++; struct Node *temp=&node[i]; while(temp->next!=NULL){ if(temp->next->flag==1) explore(temp->next->v); temp=temp->next; } node[i].post=clock; clock++; } void DFS(int v_count){ for(int i=1;i<=v_count;i++){ if(node[i].flag==1){ explore(i); } } } int main(){ int v_count,line_count,v_head,v_target,i; while(scanf("%d",&v_count)!=EOF){ scanf("%d",&line_count); clock=1; for(i=1;i<=v_count;i++){ node[i].flag=1; node[i].next=NULL; node[i].v=i; } for(i=1;i<=line_count;i++){ scanf("%d %d",&v_head,&v_target); struct Node *temp=&node[v_head]; struct Node *temp_next=temp->next; while(temp_next!=NULL&&temp_next->v<v_target){ temp=temp_next; temp_next=temp_next->next; } if(temp_next==NULL){ struct Node *n=(struct Node *)malloc(sizeof(struct Node)); n->v=v_target; n->flag=1; n->next=NULL; temp->next=n;//true }else{ struct Node *n=(struct Node *)malloc(sizeof(struct Node)); n->v=v_target; n->flag=1; n->next=temp_next; temp->next=n; } } DFS(v_count); for (int i = 1; i <= v_count; i++)printf("%d ", node[i].pre); printf("\n"); for (int i = 1; i <= v_count; i++)printf("%d ", node[i].post); } return 0; }
1941 强连通分量、qiangliantong
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stack> using namespace std; typedef struct bian{ int a; int b; }Node; Node node[100010]; int n, e; int res; int first[1010]; int _next[100010]; int dfn[1010]; int low[1010]; int ins[1010]; int num; stack<int> s; int top = 0; void dfs(int t){ dfn[t] = low[t] = ++num; s.push(t); ins[t] = 1; int i = first[t]; while( i != -1){ int v = node[i].b; if(!dfn[v]){ dfs(v); if(low[t]>low[v]) low[t] = low[v]; }else if(ins[v]){ if(low[t]>dfn[v]) low[t] = dfn[v]; } i = _next[i]; } if(dfn[t] == low[t]){ while(true) { int v = s.top(); s.pop(); ins[v] = 0; if(t == v) break; } res++; } } int main(){ res = 0; num = 0; memset(node, 0, sizeof(node)); memset(first, -1, sizeof(first)); memset(ins, 0, sizeof(ins)); memset(dfn, 0, sizeof(dfn)); scanf("%d", &n); scanf("%d", &e); for(int i = 0; i < e; i++){ scanf("%d%d", &node[i].a, &node[i].b); _next[i] = first[node[i].a]; first[node[i].a] = i; } for(int i = 1; i <= n; i++){ if(!dfn[i]) dfs(i); } printf("%d", res); return 0; }
1943 多重背包、duozhong
#include <stdio.h> #define N 100 #define C 10000 int main(){ int T; scanf("%d",&T); while(T--){ int n,c,w[N+1],v[N+1],m[N+1],i,j,k = 0,t,f[C] = {0}; scanf("%d %d",&n,&c); for(i = 1;i <= n;i++){ t = 1; scanf("%d %d %d",&w[i],&v[i],&m[i]); if(m[i] > 1){ while(m[i] > t){ k++; w[n+k] = w[i] * t; v[n+k] = v[i] * t; m[n+k] = 1; m[i] -= t; t *= 2; } w[i] *= m[i]; v[i] *= m[i]; m[i] = 1; } } for(i = 1;i <= n+k;i++){ if(m[i] == 1){ for(j = c;j >= w[i];j--){ f[j]=f[j]>f[j-w[i]]+v[i] ? f[j]:f[j-w[i]]+v[i]; } }else{ for(j = w[i];j <= c;j++){ f[j]=f[j]>f[j-w[i]]+v[i] ? f[j]:f[j-w[i]]+v[i]; } } } printf("%d\n",f[c]); } return 0; }
1945 二维背包、erwei #include<stdio.h> int f[1000][1000]; int v[1000]; int w[1000]; int p[1000]; int N,C,L; void calc_max(); int main(){ int T; scanf("%d",&T); while(T){ int i; scanf("%d %d %d",&N,&C,&L); for(i=1;i<=N;i++){ scanf("%d",&v[i]); scanf("%d",&w[i]); scanf("%d",&p[i]); } calc_max(); T--; } return 0; } void calc_max(){ int i,j,k,max; for(i=0;i<=L;i++) for(j=0;j<=C;j++) f[i][j] = 0; for(i=1;i<=N;i++){ for(j=L;j>=w[i];j--){ for(k=C;k>=v[i];k--){ max = f[j][k]; if(max < f[j-w[i]][k-v[i]] + p[i]) max = f[j-w[i]][k-v[i]] + p[i]; f[j][k] = max; } } } printf("%d\n",f[L][C]); } 1946 分组背包、fenzu #include<stdio.h> int N,C; int num[1000]; //i组有多少种物品 int w[1000][100]; //第i组物品的第j种物品的体积 int v[1000][100]; int f[1000]; void calc_max(); int main(){ int i,j; int T; scanf("%d",&T); while(T){ scanf("%d %d",&N,&C); for(i=1;i<=N;i++){ scanf("%d",&num[i]); for(j=1;j<=num[i];j++){ scanf("%d %d",&w[i][j],&v[i][j]); } } calc_max(); T--; } return 0; } void calc_max(){ int i,j,k,max=0; for(i=0;i<1000;i++) f[i] = 0; for(k=1;k<=N;k++){ for(j=C;j>=0;j--){ for(i=1;i<=num[k];i++){ if(j >= w[k][i]){ max = f[j]; if(max < f[j-w[k][i]] + v[k][i]) max = f[j-w[k][i]] + v[k][i]; f[j] = max; } } } } printf("%d\n",f[C]); }
2005 输油管道、shuyou
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; int a[10010]; int b[10010]; int cmp(int a, int b){ return a < b; } int main() { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int n; scanf("%d", &n); int x, y; for(int i = 0; i < n; i++){ scanf("%d%d", &x, &y); b[i] = y; } sort(b, b+n, cmp);//从大到小排序 int c = b[n/2]; //选最中间的点为基点。 int res = 0; for(int i = 0; i < n; i++){ res += abs(c - b[i]); } printf("%d\n", res); }
2028 租用游艇问题、youting #include <stdio.h> #define MAX 200 int money[MAX][MAX]; int cal(int n){ int i, j=n, k,h=n-1; for (i = n - 2; i >= 1; i--){ for (k = h; k <= n - 1; k++){ if (money[i][j]>(money[i][k] + money[k][j])){ money[i][j] = money[i][k] + money[k][j]; } } h--; } return money[1][n]; } int main(){ int n; scanf("%d",&n); int j, k = 2; for (int i = 1; i <= n - 1; i++){ for (j = k; j <= n; j++){ scanf("%d",&money[i][j]); } k++; } printf("%d\n",cal(n)); return 0; }
2060 子集和问题 zijihe
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[7000]; bool book[7000]; int b[7000]; int n,c; int flag; int mark; void dfs(int step,int sum) { if(step==n) { if(sum<c) mark=1; return ; } if(mark) return ; if(a[step]>c) return ; if(sum>c) return ; if(flag) return ; int i; if(sum==c) { flag=1; for(i=0;i<step-1;i++) printf("%d ",b[i]); printf("%d \n",b[i]); return ; } for(i=0;i<n;i++) { if(book[i]==0) { book[i]=1; b[step]=a[i]; dfs(step+1,sum+a[i]); book[i]=0; } } } int main(void) { while(scanf("%d%d",&n,&c)!=EOF) { int i; for(i=0;i<n;i++) scanf("%d",&a[i]); memset(book,0,sizeof(book)); sort(a,a+n); flag=0; mark=0; if(a[0]>c) { printf("No Solution!\n"); continue ; } dfs(0,0); if(flag==0||mark==1) printf("No Solution!\n"); } return 0; }
------------------------------------------------------------------------------------------------------------------
1331 是否可达、keda
#include<stdio.h> #include<string.h> int n,m; int v[105]; int vis[105]; int edge[105][105]; int h; struct nod{ int b; int next; }node[1000]; nod tnode; void dfs(int i){ int j; if(vis[i]) return; vis[i]=1; for(j=v[i];j!=-1;j=node[j].next){ dfs(node[j].b); edge[h][node[j].b]=1; } } int main(){ int a,b,i; while(scanf("%d %d",&n,&m)!=EOF){ memset(edge,0,sizeof(edge)); memset(vis,0,sizeof(vis)); memset(v,-1,sizeof(v)); for(i=0;i<m;i++){ scanf("%d %d",&a,&b); node[i].b=b; node[i].next=v[a]; v[a]=i; } for(i=1;i<=n;i++){ h=i; dfs(i); } for(i=1;i<=n;i++) edge[i][i]=1; scanf("%d",&m); for(i=0;i<m;i++){ scanf("%d%d",&a,&b); if(edge[a][b]) printf("yes\n"); else printf("no\n"); } } return 0; }
1351 二分查找、erfen
#include<stdio.h> int main(){ int m,n,x,a[20000]; int low,high,mid,i; scanf("%d",&m); for(i=0;i<m;i++){ scanf("%d",&a[i]); } scanf("%d",&n); while(n--){ scanf("%d",&x); low=0;high=m-1; while(low<=high){ mid=(low+high)/2; if(x==a[mid]) break; else if(x<a[mid]) high=mid-1; else low=mid+1; } if(low<=high) printf("%d\n",mid); else printf("Not Found\n"); } }
1360 快速排序、kuaipai
#include<stdio.h> int n; void kp(int *a,int l,int r){ if(l>=r) return; int i=l,j=r,key=a[l],k; while(i<j){ while(i<j&&key<=a[j]) j--; k=a[i];a[i]=a[j];a[j]=k; while(i<j&&key>=a[i]) i++; k=a[i];a[i]=a[j];a[j]=k; } for(k=0;k<n;k++){ if(k!=n-1) printf("%d ",a[k]); else printf("%d\n",a[k]); } kp(a,l,i-1); kp(a,i+1,r); } int main() { int a[100000],i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); kp(a,0,n-1); return 0; }
1503 捕牛记、puniu #include<stdio.h> #include<string.h> int v[1000000],p[1000000],s[1000000]; int main(){ int n,m,h,t; while(scanf("%d%d",&n,&m)!=EOF&&n!=-1){ h=0,t=1; memset(v,0,sizeof(v)); memset(p,0,sizeof(v)); memset(s,0,sizeof(v)); v[n]=1,p[t]=n; while(h<t){ h++; if(p[h]==m){ printf("%d\n",s[h]); break; } if(v[p[h]-1]==0&&p[h]-1>=0) t++,p[t]=p[h]-1,s[t]=s[h]+1,v[p[h]-1]=1; if(v[p[h]+1]==0&&p[h]+1<=100000) t++,p[t]=p[h]+1,s[t]=s[h]+1,v[p[h]+1]=1; if(v[2*p[h]]==0&&2*p[h]<=100000) t++,p[t]=2*p[h],s[t]=s[h]+1,v[2*p[h]]=1; } } return 0; }
1567 中位数、zhongwei
#include<stdio.h>
int a[1000001],b[1000001]; int main(){ int L,i,j,item=0,sum; scanf("%d",&L); for(i=0;i<L;i++) scanf("%d",&a[i]); for(i=0;i<L;i++) scanf("%d",&b[i]); for(i=0,j=0;i<L&&j<L;){ if(a[i]>=b[j]){ item++; sum = b[j++]; } else{ item++; sum = a[i++]; } if(item==L) break; } printf("%d\n",sum); return 0; }
1901 最长公共子序列、zuichang
#include<stdio.h> #include<stdlib.h> #include<string.h> int map[1000][1000]; int main(){ int i,j,len1,len2,T; char s[1000],t[1000]; scanf("%d",&T); while(T--){ scanf("%s %s",&s,&t); len1 = strlen(s); len2 = strlen(t); memset(map,0,sizeof(map)); for(i=1;i<=len2;i++){ for(j=1;j<=len1;j++){ if(s[j]==t[i]) map[i][j] = map[i-1][j-1]+1; else if(map[i-1][j]>map[i][j-1]) map[i][j] = map[i-1][j]; else map[i][j]= map[i][j-1]; } } printf("%d\n",map[len2][len1]); } return 0; }
1923 符号三角形问题、sanjiao #include<stdio.h> int n,half,count,sum; int p[27][27]; void backtrack(int t){ int i,j; if( (count>half) || (t*(t-1)/2-count>half) ) return; if(t>n) sum++; else{ for(i=0;i<2;i++){ p[1][t]=i; count+=i; for(j=2;j<=t;j++){ p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1]; } backtrack(t+1); for(j=2;j<=t;j++){ count-=p[j][t-j+1]; } count-=i; } } } int main(){ int T,i,j,k; scanf("%d",&T); for(i=1;i<=T;i++){ count=sum=0; scanf("%d",&n); half=n*(n+1)/2; if(half%2==0){ half=half/2; for(j=0;j<=n;j++) for(k=0;k<=n;k++) p[j][k] = 0; backtrack(1); printf("Case %d: %d\n",i,sum); } else printf("Case %d: 0\n",i); } return 0; } 1924 n后问题、nhou #include<stdio.h> #include<stdlib.h> int count; int n; int column[15]; void traceBack(int k); int legal(int k); int main(){ int T; scanf("%d",&T); while(T){ scanf("%d",&n); count = 0; traceBack(1); printf("%d\n",count); T--; } return 0; } int legal(int k){ int i; for(i=1;i<k;i++) if(abs(k-i)==abs(column[k]-column[i]) || column[k]==column[i]) return 0; return 1; } void traceBack(int k){ if(k > n) count++; else{ int i; for(i=1;i<=n;i++){ column[k] = i; if(legal(k)) traceBack(k+1); } } } 1925 最大团、tuan #include <stdio.h> #include <string.h> int book[25][25],vist[25],que[25]; int n,m,maxx; void dfs(int x,int sum){ if(x>n){ maxx=sum; return ; } int vt=0; for(int j=0;j<sum;j++){ if(book[x][que[j]] == 0){ vt=1; break; } } if(vt == 0) { vist[x]=1; que[sum]=x; dfs(x+1,sum+1); } if(sum+n-x >maxx) dfs(x+1,sum); } int main(){ int t,vi=0; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); int x,y; memset(vist,0,sizeof(vist)); memset(book,0,sizeof(book)); maxx=0; for(int i=1;i<=m;i++){ scanf("%d %d",&x,&y); book[x][y]=1; book[y][x]=1; } dfs(1,0); vi++; printf("Case %d: %d\n",vi,maxx); } return 0; }
1927 旅行售货员问题、lvxing
#include<iostream> #define N 100 using namespace std; int n,m,w, graph[N][N], c=0, bestc=-1, x[N], bestx[N]; void swap(int &a,int &b){ int temp=a; a=b; b=temp; } void backtrack(int k) { if(k==n) { if( (c+graph[x[n-1]][x[n]]+graph[x[n]][1]<bestc||bestc==-1) && graph[x[n-1]][x[n]]!=-1 && graph[x[n]][1]!=-1 ) { bestc=c+graph[x[n-1]][x[n]]+graph[x[n]][1]; for(int i=1;i<=n;i++) { bestx[i]=x[i]; } } return ; } else { for(int i=k;i<=n;i++) { if( graph[x[k-1]][x[i]]!=-1 && (c+graph[x[k-1]][x[i]]<bestc || bestc==-1)) { swap(x[i],x[k]); c+=graph[x[k-1]][x[k]]; backtrack(k+1); c-=graph[x[k-1]][x[k]]; swap(x[i],x[k]); } } } } int main(void) { int i,j,tmp=1,testNum; cin>>testNum; while(tmp<=testNum){ cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) graph[i][j]=-1; for(int k=1;k<=m;k++){ cin>>i>>j>>w; graph[i][j]=w; graph[j][i]=w; } for(i=1;i<=n;i++) { x[i]=i; bestx[i]=i; } backtrack(2); cout<<"Case "<<tmp<<": "<<bestc<<endl; bestc=-1; c=0; tmp++; } return 0; }
1930 主元素、zhu
#include<stdio.h> #include<stdlib.h> int main(){ int N,n,a[100000],count,seed; scanf("%d",&N); while(N--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); count = 1;seed = a[0]; for(int i=1;i<n;i++){ if(a[i] == seed) count++; else count--; if(count == 0){ if(i<n-1) { seed = a[i+1];count = 1; } else break; } } if(count == 0) printf("no\n"); else{ count = 0; for(int i=0;i<n;i++) if(a[i] == seed) count++; if(count>n/2) printf("%d\n",seed); else printf("no\n"); } } system("pause"); return 0; }
1940 用DFS计算pre和post、jisuan
#include<stdio.h> #include<stdlib.h> int num,n,m; int map[1005][1005]; int pre[1005],post[1005],flag[1005]; void dfs(int i){ int j,k; if(flag[i] == 1) return ; pre[i] = num++; for(j=1;j<=n;j++){ if(map[i][j] == 1 && j != i){ for(k=1;k<=n;k++) map[k][i] = 0; dfs(j); } } flag[i] = 1; post[i] = num++; return ; } int main(){ int i; scanf("%d %d",&n,&m); num=1; for( i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j] = 0; for( i=1;i<=n;i++){ pre[i] = 0,post[i] = 0,flag[i] = 0; } for( i=0;i<m;i++){ int x,y; scanf("%d %d",&x,&y); map[x][y] = 1; } for( i=1;i<=n;i++) dfs(i); for( i=1;i<=n;i++) printf("%d ",pre[i]); printf("\n"); for( i=1;i<=n;i++) printf("%d ",post[i]); return 0; }
1941 强连通分量、qiangliantong
#include<stdio.h> #include<string.h> int G[1001][1001]; int cG[1001][1001]; int v[1001]; int visited[1001]; int n, e; struct stack{ int data[1001]; int top; } s; void cDFS(int k); void DFS(int k); int count; int main(){ int i, j, k; scanf("%d %d",&n,&e); for(i=1;i<=n;i++){ v[i] = i; visited[i] = 0; } for(k=1;k<=e;k++){ scanf("%d %d",&i,&j); G[i][j] = 1; cG[j][i] = 1; } s.top = -1; for(i=1;i<=n;i++) if(!visited[i]){ cDFS(i); s.top++; s.data[s.top] = v[i]; } i =0; while(s.top!=-1){ i++; v[i] = s.data[s.top]; s.top--; } count = 0; memset(visited,0,sizeof(visited)); for(i=1;i<=n;i++) if(!visited[v[i]]){ count++; DFS(v[i]); } printf("%d",count); } void cDFS(int k){ int i; visited[k] = 1; for(i=1;i<=n;i++){ if(!visited[i] && cG[k][i]==1){ cDFS(i); s.top++; s.data[s.top] = v[i]; } } } void DFS(int k){ int i; visited[k] = 1; for(i=1;i<=n;i++){ if(!visited[i] && G[k][i]==1) DFS(i); } }
1943 多重背包、duozhong
#include<stdio.h> #include<string.h> int f[10000],w[10000],v[10000]; int size,n,c; void calc_max(){ int i,j,max; for(i=0;i<=10000;i++) f[i] = 0; for(i=0;i<size;i++){ for(j=c;j>=w[i];j--){ max = f[j]; if(max < f[j-w[i]] + v[i]) max = f[j-w[i]] + v[i]; f[j] = max; } } printf("%d\n",f[c]); } int main(){ int T; scanf("%d",&T); while(T--){ int i,j,weight,value,num; size = 0; scanf("%d %d",&n,&c); for(i=1;i<=n;i++){ scanf("%d %d %d",&weight,&value,&num); for(j=1;j<=num;j=j*2){ w[size] = j * weight; v[size] = j * value; size++; num -= j; } if(num>0){ w[size] = num * weight; v[size] = num * value; size++; } } calc_max(); } return 0; }
1945 二维背包、erwei #include<stdio.h> int f[1000][1000]; int v[1000],w[1000],p[1000]; int N,C,L; void calc_max(){ int i,j,k,max; for(i=0;i<=L;i++) for(j=0;j<=C;j++) f[i][j] = 0; for(i=1;i<=N;i++){ for(j=L;j>=w[i];j--){ for(k=C;k>=v[i];k--){ max = f[j][k]; if(max < f[j-w[i]][k-v[i]] + p[i]) max = f[j-w[i]][k-v[i]] + p[i]; f[j][k] = max; } } } printf("%d\n",f[L][C]); } int main(){ int T; scanf("%d",&T); while(T--){ int i; scanf("%d %d %d",&N,&C,&L); for(i=1;i<=N;i++){ scanf("%d",&v[i]); scanf("%d",&w[i]); scanf("%d",&p[i]); } calc_max(); } return 0; } 1946 分组背包、fenzu #include<stdio.h> int N,C; int num[1000]; int f[1000]; int w[1000][100]; int v[1000][100]; void calc_max(){ int i,j,k,max=0; for(i=0;i<1000;i++) f[i] = 0; for(k=1;k<=N;k++){ for(j=C;j>=0;j--){ for(i=1;i<=num[k];i++){ if(j >= w[k][i]){ max = f[j]; if(max < f[j-w[k][i]] + v[k][i]) max = f[j-w[k][i]] + v[k][i]; f[j] = max; } } } } printf("%d\n",f[C]); } int main(){ int i,j; int T; scanf("%d",&T); while(T--){ scanf("%d %d",&N,&C); for(i=1;i<=N;i++){ scanf("%d",&num[i]); for(j=1;j<=num[i];j++){ scanf("%d %d",&w[i][j],&v[i][j]); } } calc_max(); } return 0; }
1948 最大子矩阵和、zuida
#include <stdio.h> #define MAX 400 int main(){ int i,j,k,temp,max,m,n,flag,map[MAX][MAX]; while(scanf("%d %d",&m,&n)!=EOF){ flag = 0; for(i = 0;i < m;i++){ for(j = 0;j < n;j++){ scanf("%d",&map[i][j]); } for(k = 0;k < i;k++){ for(j = 0;j < n;j++){ map[k][j] += map[i][j]; } } for(k = 0;k <= i;k++){ for(j = n-1;j >= 0;j--){ if(j == n-1) max = map[k][j]; else max = map[k][j] > (map[k][j] + max) ? map[k][j] : (map[k][j] + max); if(flag == 0){ temp = max; flag = 1; }else{ temp = temp > max ? temp : max; } } } } printf("%d\n",temp); } return 0; }
2005 输油管道、shuyou
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; int a[10010]; int b[10010]; int cmp(int a, int b){ return a < b; } int main() { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); int n; scanf("%d", &n); int x, y; for(int i = 0; i < n; i++){ scanf("%d%d", &x, &y); b[i] = y; } sort(b, b+n, cmp); int c = b[n/2]; int res = 0; for(int i = 0; i < n; i++){ res += abs(c - b[i]); } printf("%d\n", res); }
2028 租用游艇问题、youting #include <stdio.h> int p[200][200]; int main(){ int i,j,k,n; scanf("%d",&n); for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) scanf("%d",&p[i][j]); for(j=2;j<=n-1;j++){ for(i=1;i<=n-j;i++){ for(k=i+1;k<=(i+j);k++){ if( p[i][i+j] > (p[i][k]+p[k][i+j]) ) p[i][i+j] = p[i][k]+p[k][i+j]; } } } printf("%d\n",p[1][n]); return 0; } 2060 子集和问题