1331 是否可达、keda
#include <stdio.h> #include <string.h> #define MAX 1000 struct Node{ int v,net; }; struct Node node[MAX]; int main(){ int n,e,t,i,x,y,z,head[MAX],que[MAX],map[MAX/2][MAX/2],qh,qt; while(scanf("%d %d",&n,&e)!=EOF){ memset(head,-1,sizeof(head)); for(i = 0;i < e;i ){ scanf("%d %d",&x,&y); node[i].v = y; node[i].net = head[x]; head[x] = i; } scanf("%d",&t); while(t--){ z = 0; memset(map,0,sizeof(map)); qh = qt = 1; scanf("%d %d",&x,&y); if(x == y){ printf("yesn"); continue; } que[qt ] = x; while(qh < qt){ for(i = head[que[qh]];i != -1;i = node[i].net){ if(map[que[qh]][node[i].v] == 0){ map[que[qh]][node[i].v] = 1; que[qt ] = node[i].v; } if(node[i].v == y){ z = 1; break; } } if(z == 1) break; qh ; } if(z == 1) printf("yesn"); else printf("non"); } printf("n"); } return 0; }
1351 二分查找、erfen
#include <stdio.h> #define MAX 200000 int a[MAX],b[MAX]; void search(int x,int len){ int low = 0,high = len-1; while(low <= high){ int mid = (low high)/2; if(a[mid] == x){ printf("%dn",mid); return; }else if(a[mid] > x){ high = mid - 1; }else{ low = mid 1; } } printf("Not Foundn"); } int main(){ int M,N,i; scanf("%d",&M); getchar(); for(i = 0;i < M;i ){ scanf("%d",&a[i]); } scanf("%d",&N); for(i = 0;i < N;i ){ scanf("%d",&b[i]); } for(i = 0;i < N;i ){ search(b[i],M); } return 0; }
1360 快速排序、kuaipai
#include <stdio.h> #define MAX 100000 int a[MAX],n; void show(){ for(int i = 0;i < n;i ){ printf("%d ",a[i]); } printf("n"); } void quicksort(int begin,int end){ if(begin < end){ int root = a[begin]; int m = begin,n = end; while(m < n){ while(m < n){ if(a[n] < root){ a[m] = a[n]; break; }else{ n--; } } while(m < n){ if(a[m] > root){ a[n] = a[m]; break; }else{ m ; } } } a[m] = root; show(); quicksort(begin,m-1); quicksort(n 1,end); } } int main(){ scanf("%d",&n); getchar(); for(int i = 0;i < n;i ){ scanf("%d",&a[i]); } quicksort(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("%dn",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> #define MAX 1000000 int n; int a[MAX],b[MAX]; int main(){ scanf("%d",&n); getchar(); for(int i = 0;i < n;i ){ scanf("%d",&a[i]); } for(int i = 0;i < n;i ){ scanf("%d",&b[i]); } int i=0,j=0,goal; while(n--){ if(a[i] >= b[j]){ goal = b[j ]; }else{ goal = a[i ]; } } printf("%dn",goal); return 0; }
1901 最长公共子序列、zuichang
#include <stdio.h> #include <string.h> #define MAX 1001 char str1[MAX],str2[MAX]; int dp[MAX][MAX]; void cal(){ int len1 = strlen(str1); int len2 = strlen(str2); int len = len1 > len2 ? len1 :len2; for(int i = 1;i <= len;i ){ dp[0][i] = 0; dp[i][0] = 0; } for(int i = 1;i <= len1;i ){ for(int 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]; } } } printf("%dn",dp[len1][len2]); } int main(){ int T; scanf("%d",&T); getchar(); while(T--){ gets(str1); gets(str2); cal(); } }
1923 符号三角形问题、sanjiao
#include <stdio.h> #define MAX 26 int n,c,sum,half,p[MAX][MAX]; void Cal(int t){ if(t > n){ sum ; }else{ int i,j; 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 1)*t/2-c) <= half){ Cal(t 1); } c -= i; for(j = 2;j <= t; j){ c -= p[j][t-j 1]; } } } } int main(){ int T,t=1; scanf("%d",&T); while(T--){ scanf("%d",&n); c = 0; sum = 0; half = (n 1)*n/2; if(half%2==0){ half/=2; Cal(1); } printf("Case %d: %dn",t ,sum); } return 0; }
1924 n后问题、nhou
#include <stdio.h> #include <stdlib.h> #define MAX 15 int n,sum,x[MAX]; int place(int k){ if(k == 1) return 1; for(int i = 1;i < k;i ){ if((abs(k-i)==abs(x[k]-x[i]))||(x[k]==x[i])) return 0; } return 1; } void backtrack(int t){ if(t > n){ sum ; }else{ for(int i = 1;i <= n;i ){ x[t] = i; if(place(t)) backtrack(t 1); } } } int main(){ int T; scanf("%d",&T); getchar(); while(T--){ sum = 0; scanf("%d",&n); backtrack(1); printf("%dn",sum); } return 0; }
1925 最大团、tuan
#include <stdio.h> #include <stdlib.h> struct Node{ int **a,*x,*bestx; int n,cn,bestn; }; void cal(struct Node *node,int i){ int j,flag = 1; if(i > node->n){ for(j = 1;j <= node->n;j ){ node->bestx[j] = node->x[j]; } node->bestn = node->cn; return; } for(j = 1;j < i;j ){ if(node->x[j] == 1&&node->a[i][j] == 0){ flag = 0; break; } } if(flag){ node->x[i] = 1; node->cn ; cal(node,i 1); node->cn--; } if(node->n node->cn - i >= node->bestn){ node->x[i] = 0; cal(node,i 1); } } int main(){ int T,t = 1,i,n,m,x,y; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); int *v = (int *)malloc(sizeof(int)*(n 1)); int *temp = (int *)malloc(sizeof(int)*(n 1)); int **a = (int **)malloc(sizeof(int *)*(n 1)); for(i = 0;i <= n;i ){ a[i] = (int *)calloc(sizeof(int),n 1); } for(i = 1;i <= m;i ){ scanf("%d %d",&x,&y); a[x][y] = 1; a[y][x] = 1; } struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->a = a; node->x = temp; node->bestx = v; node->n = n; node->cn = 0; node->bestn = 0; cal(node,1); printf("Case %d: %dn",t ,node->bestn); } 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> #include <time.h> #define MAX 100001 int n,x,t[MAX]; int m2(){ int i = rand()%n 1; x = t[i]; int k; for(int j = 1;j <= n;j ){ if(t[j]==x) k ; } if(k > n/2) return 1; else return 0; } int m1(){ int l = 100; while(l--){ if(m2()) return 1; else return m2(); } } int main(){ int T,i; srand((int)time(0)); scanf("%d",&T); while(T--){ scanf("%d",&n); for(i = 1;i <= n;i ){ scanf("%d",&t[i]); } if(m1()) printf("%dn",x); else printf("non"); } return 0; }
1940 用DFS计算pre和post、jisuan
#include <stdio.h> #include <stdlib.h> struct Node{ int flag,v,pre,post; struct Node *next; }; int clock; struct Node node[1001]; void explore(int i){ if(node[i].flag == -1) return; node[i].flag = -1; node[i].pre = clock ; struct Node *temp = &node[i]; while(temp->next){ if(temp->next->flag ==1) explore(temp->next->v); temp = temp->next; } node[i].post = clock ; } void DFS(int v_count){ for(int i = 1;i <= v_count;i ){ if(node[i].flag == 1){ explore(node[i].v); } } } int main(){ int v_count,line_count,v_head,v_target; while(scanf("%d",&v_count)!=EOF){ clock = 1; scanf("%d",&line_count); for(int i = 1;i <= v_count;i ){ node[i].flag = 1; node[i].next = NULL; node[i].v = i; } for(int 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->flag = 1; n->v = v_target; n->next = NULL; temp->next = n; }else{ struct Node *n = (struct Node *)malloc(sizeof(struct Node)); n->flag = 1; n->v = v_target; 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); } printf("n"); } }
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> #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 ){ scanf("%d %d %d",&w[i],&v[i],&m[i]); t = 1; 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("%dn",f[c]); } return 0; }
1945 二维背包、erwei
#include <stdio.h> #define MAX 1000 int T,i,j,k,max,N,C,L,v[MAX],w[MAX],p[MAX],f[MAX][MAX]; int main(){ scanf("%d",&T); while(T--){ scanf("%d %d %d",&N,&C,&L); for(i = 1;i <= N;i ){ scanf("%d %d %d",&v[i],&w[i],&p[i]); } 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("%dn",f[L][C]); } return 0; }
1946 分组背包、fenzu
#include <stdio.h> #define MAX 1000 int T,max,i,j,k,N,C,num[MAX],v[MAX][MAX],p[MAX][MAX],f[MAX]; int main(){ 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",&v[i][j],&p[i][j]); } } for(i = 0;i <= C;i ){ f[i] = 0; } for(i = 1;i <= N;i ){ for(j = C;j >= 0;j--){ for(k = 1;k <= num[i];k ){ if(j >= v[i][k]){ max = f[j]; if(max < f[j-v[i][k]] p[i][k]){ max = f[j-v[i][k]] p[i][k]; } f[j] = max; } } } } printf("%dn",f[C]); } 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("%dn",temp); } return 0; }
2005 输油管道、shuyou
#include <stdio.h> #include <math.h> #include <algorithm> #define MAX 10000 using namespace std; int cmp(int x, int y){ return x < y; } int main(){ int n,x,y,b[MAX]={0}; scanf("%d",&n); 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("%dn",res); }
2028 租用游艇问题、youting
#include <stdio.h> #define MAX 201 int money[MAX][MAX]; void 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--; } printf("%dn",money[1][n]); } int main(){ int n,i,j,k = 2; scanf("%d",&n); for(i = 1;i <= n-1;i ){ for(j = k;j <= n;j ){ scanf("%d",&money[i][j]); } k ; } cal(n); return 0; }
2060 子集和问题
#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; }
