OJ算法题

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("yes\n");                 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("yes\n");             else printf("no\n");         }         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("%d\n",mid);             return;         }else if(a[mid] > x){             high = mid - 1;         }else{             low = mid + 1;         }     }     printf("Not Found\n"); } 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("%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> #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("%d\n",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("%d\n",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: %d\n",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("%d\n",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: %d\n",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("%d\n",x);         else printf("no\n");     }     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("%d\n",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("%d\n",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("%d\n",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("%d\n",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("%d\n",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("%d\n",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; }