大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
http://poj.org/problem?id=4044
大致题意:给出两个班级的成绩,先按降序排序,而且没有成绩同样的。然后求连续的最长公共子序列。输出时,先输出最长公共子序列,然后按个位数字递增的顺序输出,若各位数字一样就按成绩递增。
人数小于30,注意去重,直接暴力就可以。
#include <stdio.h> #include <iostream> #include <map> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 32; int n1,n2; int a[maxn],b[maxn],aa[maxn],bb[maxn]; int cmp(int a, int b) { return a > b; } struct node { int num; int dig; bool operator < (const struct node &tmp)const { if(dig == tmp.dig) return num < tmp.num; return dig < tmp.dig; } }ans[maxn]; bool judge(int s1, int s2, int len) { int k; for(k = 0; k < len; k++) { if(a[s1+k] != b[s2+k]) break; } if(k < len) return false; return true; } int main() { int test; scanf("%d",&test); while(test--) { int i,j,t; scanf("%d %d",&n1,&n2); for(i = 0; i < n1; i++) scanf("%d",&aa[i]); for(i = 0; i < n2; i++) scanf("%d",&bb[i]); sort(aa,aa+n1,cmp); sort(bb,bb+n2,cmp); a[0] = aa[0]; t = 1; for(i = 1; i < n1;) { while(aa[i] == aa[i-1] && (i+1) < n1) i++; if(aa[i] != aa[i-1]) a[t++] = aa[i++]; else break; } n1 = t; b[0] = bb[0]; t = 1; for(i = 1; i < n2; ) { while(bb[i] == bb[i-1] && (i+1) < n2) i++; if(bb[i] != bb[i-1]) b[t++] = bb[i++]; else break; } n2 = t; int len = 0; int cnt; for(i = 0; i < n1; i++) { for(j = 0; j < n2; j++) { for(int k = 1; k <= min(n1-i,n2-j); k++) { if(judge(i,j,k) && len < k) { len = k; cnt = 0; for(int g = 0; g < k; g++) ans[cnt++] = (struct node){a[i+g],a[i+g]%10}; } } } } if(len == 0) { printf("NONE\n"); continue; } for(int i = 0; i < cnt-1; i++) printf("%d ",ans[i].num); printf("%d\n",ans[cnt-1].num); sort(ans,ans+cnt); for(i = 0; i < cnt-1; i++) printf("%d ",ans[i].num); printf("%d\n",ans[cnt-1].num); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118545.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...