2016天梯模拟赛 进阶题解

L2-005 集合相似度

题目链接:

https://www.patest.cn/contests/gplt/L2-005

题目的意思是要求两个集合的交集中互不相同元素的个数和两个集合并集中互不相同的元素的个数

先求交集中互不相同的元素,然后用两个集合互不相同元素个数的和减去,就是并集中的个数

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <string>

using namespace std;
int n;
int a[55][1005];
int b[55];
double ans[55][55];
int Get[55];
int k;
int x,y;
int bin(int x,int y)
{
	int l=0;
	int r=b[y]-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(a[y][mid]==x)
			return 1;
		else if(x>a[y][mid])
			l=mid+1;
		else
			r=mid-1;
	}
	return 0;
}
int fun(int x,int y)
{
	int num=0;
	int i=0,j=0;
	for(int i=0;i<b[x];i++)
	{
		if(i==0||a[x][i]!=a[x][i-1])
			num+=bin(a[x][i],y);
	}
	return num;
}
int get(int x)
{
	int num=0;
	for(int i=1;i<b[x];i++)
	{
		if(a[x][i]!=a[x][i-1])
			num++;
	}
	num++;
	return num;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			for(int j=0;j<b[i];j++)
			{
				scanf("%d",&a[i][j]);
			}
			sort(a[i],a[i]+b[i]);
		}
		for(int i=1;i<=n;i++)
			Get[i]=get(i);
		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<=n;j++)
			{
				if(i==j)
					ans[i][j]=1;
				else
				{
					int num1=fun(i,j);
					int num2=Get[i]+Get[j];
					int num3=num2-num1;
					ans[i][j]=1.0*num1/num3;
				}

			}
		}
		scanf("%d",&k);
		for(int i=1;i<=k;i++)
		{
			scanf("%d%d",&x,&y);
			if(x>y)
				swap(x,y);
			printf("%.2f%%\n",100.0*ans[x][y]);
		}
	}
}

L2-006 树的遍历

题目链接:

https://www.patest.cn/contests/gplt/L2-006

根据二叉树的后序中序建立这颗二叉树,二叉树可以用链式指针存储也可以用数组存储

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>

using namespace std;
typedef struct Tree
{
	int data;
	Tree *lchild;
	Tree *rchild;
}a[40];
int post[40];
int in[40];
int n;
int ans[40];
void dfs(int l1,int r1,int l2,int r2,Tree* &root)
{
	root=new Tree();
	int i;
	for( i=l1;i<=r1;i++)
		if(in[i]==post[r2])
			break;
	root->data=post[r2];
	if(i==l1)
		root->lchild=NULL;
	else
		dfs(l1,i-1,l2,l2+i-l1-1,root->lchild);
	if(i==r1)
		root->rchild=NULL;
	else
		dfs(i+1,r1,r2-(r1-i),r2-1,root->rchild);
}
int cnt;
void bfs(Tree *tree)
{
	queue<Tree*> q;
	q.push(tree);
	while(!q.empty())
	{
		Tree *root=q.front();
		q.pop();
		ans[cnt++]=root->data;
		if(root->lchild!=NULL)
			q.push(root->lchild);
		if(root->rchild!=NULL)
			q.push(root->rchild);
	}
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&post[i]);
		for(int i=1;i<=n;i++)
			scanf("%d",&in[i]);
		Tree *tree;
		dfs(1,n,1,n,tree);
		cnt=0;
		bfs(tree);
		for(int i=0;i<cnt;i++)
		{
			if(i==cnt-1)
				printf("%d\n",ans[i]);
			else
				printf("%d ",ans[i]);
		}
	}
	return 0;
}

L2-007 家庭房产

https://www.patest.cn/contests/gplt/L2-007

按照编号和编号之间的关系,建立一个图,然后dfs求连通块

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;
struct Node
{
	int next;
	int value;
	int weight;
}edge[100005*4];
int head[10005];
int flag[10005];
int vis[10005];
int tot;
int n;
int tag[1005];
void add(int x,int y,int z)
{
	edge[tot].weight=z;
	edge[tot].value=x;
	edge[tot].next=head[y];
	head[y]=tot++;
}
int area[1005];
int house[1005];
int member[15];
struct node
{
	int minn;
	int num;
	int house;
	int area;
	double ah;
	double aa;
}b[10005];
int cmp(node a,node b)
{
	if(a.aa==b.aa)
		return a.minn<b.minn;
	return a.aa>b.aa;
}
void dfs(int x,int cnt)
{
	vis[x]=1;
	for(int i=head[x];i!=-1;i=edge[i].next)
	{
		int y=edge[i].value;
		if(!tag[edge[i].weight])
		{
			b[cnt].area+=area[edge[i].weight];
			b[cnt].house+=house[edge[i].weight];
			tag[edge[i].weight]=1;
		}
		if(vis[y])
			continue;
		b[cnt].minn=min(b[cnt].minn,y);
		b[cnt].num++;
		dfs(y,cnt);
	}
}
int k;
int main()
{
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	memset(flag,0,sizeof(flag));
	tot=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{scanf("%d",&member[j]);flag[member[j]]=1;}
		scanf("%d",&k);
		for(int j=4;j<=k+3;j++)
		{scanf("%d",&member[j]);flag[member[j]]=1;}
		scanf("%d%d",&house[i],&area[i]);
		for(int j=1;j<=k+3;j++)
		{
			for(int p=1;p<=k+3;p++)
			{
				if(member[j]!=-1&&member[p]!=-1)
				{
					add(member[j],member[p],i);
					add(member[p],member[j],i);
				}
			}
		}
	}
	int cnt=-1;
	memset(vis,0,sizeof(vis));
	memset(tag,0,sizeof(tag));
	for(int i=0;i<10000;i++)
	{
		if(!vis[i]&&flag[i])
		{
			b[++cnt].minn=i;
			b[cnt].num=1;b[cnt].house=0;b[cnt].area=0;
			dfs(i,cnt);
		}
	}
	for(int i=0;i<=cnt;i++)
	{
		b[i].aa=1.0*b[i].area/b[i].num;
		b[i].ah=1.0*b[i].house/b[i].num;
	}
	sort(b,b+cnt+1,cmp);
	printf("%d\n",cnt+1);
	for(int i=0;i<=cnt;i++)
	{
		printf("%04d %d %.3f %.3f\n",b[i].minn,b[i].num,b[i].ah,b[i].aa);
	}
	return 0;
}

L2-008 最长对称子串

https://www.patest.cn/contests/gplt/L2-008

暴力三个for循环,最近学了回文树,就用了

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <string>

using namespace std;
#define MAX 1000
char str[MAX+5];
int ans;
struct Tree
{
	int next[MAX+5][500];
	int fail[MAX+5];
	int len[MAX+5];
	int s[MAX+5];
	int last;
	int p;
	int n;
	int new_node(int x)
	{
		memset(next[p],0,sizeof(next[p]));
		len[p]=x;
		return p++;
	}
	void init()
	{
		p=0;
		new_node(0);
		new_node(-1);
		last=0;
		n=0;
		s[0]=-1;
		fail[0]=1;
	}
	int get_fail(int x)
	{
		while(s[n-len[x]-1]!=s[n])
			x=fail[x];
		return x;
	}
	int add(int x)
	{
		s[++n]=x;
		int cur=get_fail(last);
		if(!(last=next[cur][x]))
		{
			int now=new_node(len[cur]+2);
			ans=max(ans,len[cur]+2);
			fail[now]=next[get_fail(fail[cur])][x];
			next[cur][x]=now;
			last=now;

		}
		return 1;
	}
}tree;
int main()
{
	gets(str);

	int len=strlen(str);
	tree.init();
	ans=0;
	for(int i=0;i<len;i++)
		tree.add(str[i]);
	printf("%d\n",ans);

	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android群英传

深入Java源码解析容器类List、Set、Map

1843
来自专栏Java爬坑系列

【Java入门提高篇】Day20 Java集合类详解(三)List接口

  今天要说的是Collection族长下的三名大将之一,List,Set,Queue中的List,它们都继承自Collection接口,所以Collectio...

2277
来自专栏LanceToBigData

JavaSE(八)集合之Set

今天这一篇把之前没有搞懂的TreeSet中的比较搞得非常的清楚,也懂得了它的底层实现。希望博友提意见! 一、Set接口 1.1、Set集合概述   Set集合:...

2305
来自专栏计算机视觉与深度学习基础

java在acm中大数运算教程

import java.io.*; import java.util.*; public class Main { public static void ...

2059
来自专栏Java帮帮-微信公众号-技术文章全总结

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&正则【悟空教程】

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&简单正则表达式【悟空教程】

972
来自专栏郭耀华‘s Blog

剑指offer第三天

21.栈的压入、弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,...

2876
来自专栏黑泽君的专栏

java基础学习_集合类03_用户登录注册案例(集合版)、Set集合、Collection集合总结_day17总结

============================================================================= ==...

992
来自专栏LinkedBear的个人空间

唠唠SE的集合-01——Collection接口

当集合中存储的对象类型不同时,那么会导致程序在运行的时候的转型异常,所以jdk1.5加入了泛型机制。

652
来自专栏java一日一条

JAVA集合类汇总

数组(可以存储基本数据类型)是用来存现对象的一种容器,但是数组的长度固定,不适合在对象数量未知的情况下使用。 集合(只能存储对象,对象类型可以不一样)的长度可变...

1223
来自专栏desperate633

排列类算法问题大总结全排列分析带重复元素的全排列代码下一个排列分析上一个排列分析第k个排列分析排列序号分析排列序号II分析

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

901

扫码关注云+社区