poj 4044 Score Sequence(暴力)

poj 4044 Score Sequence(暴力)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

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账号...

(0)


相关推荐

  • arduino mpu9250_arduino模拟输出

    arduino mpu9250_arduino模拟输出Arduino有多种通信方式,每一种通信方式都有相对应的类库来支持:1)硬件串口通信——HardwareSerial类库2)软件模拟串口通信——SoftwareSerial类库3)IIC总线的使用——Wire类库4)SPI总线的使用——SPI类库 MPU6050的数据接口用的是I2C总线协议,因此我们需要Wire类库的帮助来实现Arduino与MPU6050之间的通…

  • arcgis10从初学到精通电子版_arcgis入门到精通

    arcgis10从初学到精通电子版_arcgis入门到精通本教程内容包括:ArcGIS平台简介、ArcGIS应用基础、空间数据的采集与组织、空间数据的转换与处理、空间数据的可视化表达、GIS空间分析导论、矢量数据的空间分析、栅格数据的空间分析、三维分析、地统计分析等。适用于高等学校GIS专业、测绘工程、国土测绘与规划等专业,大学本科研究ArcGIS实验教程:ArcGIS10.2手把手图文安装教程ArcGIS实验教程——实验一:ArcGIS软件的认识与使用ArcGIS实验教程——实验二:地理配准完整操作步骤ArcGIS实验教程——实验三:矢量数据采集与编辑

  • centos安装VirtualBox增强包VBoxGuestAdditions

    centos安装VirtualBox增强包VBoxGuestAdditions1.如果你的CentOS版本早于6,那么需要在/etc/grub.conf中添加一行divider=10,以将这个参数传递给核心,以减少idleCPUload。2.#yumupda

  • 递归算法时间复杂度分析[通俗易懂]

    递归算法时间复杂度分析[通俗易懂]递归算法时间复杂度分析时间复杂度:一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。T(n)=o(f(n));它表示随问题规模n的增大,算法的执行时间增长率和f(n)增长率成正比,这称作算法的渐进时间复杂度…

  • python使用RSA加密算法

    python使用RSA加密算法最近换了工作,由于新公司是做个人和企业征信业务的,所以对数据的隐私性看的非常重要,所有涉及隐私的数据一律都要进行加密进行传输。那么问题来了,对我我要做的工作,就是要实现我们接口自动化,免不了要接触加密-签名-解密-验签等一系列过程。这时候就觉得大学真的白学密码学了。。。基于我用python语言搞,那我这里就说说我是如何实现python对数据进行RSA加解密的吧。。一、查找python支…

  • 蓝屏代码0x000000be_电脑蓝屏0*000000ed怎么解决

    蓝屏代码0x000000be_电脑蓝屏0*000000ed怎么解决windows系统相信大家最怕的就是遇到蓝屏的问题了,不太好解决,这不有朋友反馈电脑出现蓝屏代码0x000000BE的问题,电脑此时已经不能用了,那么要怎么解决呢?如果不知道如何操作的话,不妨先试试小编教大家的方法。蓝屏代码0x000000BE是什么意思?0x000000BE错误表示硬件设备的驱动程序试图向只读内存错误地写入数据,这个错误一般是因为硬件设备驱动程序存在BUG或安装不正确引起的。解决…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号