前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >OJ算法题已AC

OJ算法题已AC

作者头像
chenchenchen
发布2023-01-30 17:04:22
4560
发布2023-01-30 17:04:22
举报
文章被收录于专栏:chenchenchen

在刷OJ题时遇到了一个题,无论怎么优化,仍然超时, 最后把输出语句换成了append(); 如下:

[java] view plain copy

  1. <span style="font-size:24px;">StringBuilder sb = new StringBuilder();  
  2. for (Student std : students) {  
  3.     sb.append(std.num).append(" ").append(std.name).append(" ").append(std.grade).append("\n");  
  4. // System.out.printf(std.num + " " + std.name + " " +std.grade);
  5. // System.out.println();
  6. }  
  7.     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 子集和问题

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-10-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档