培训套题2

发表于 2016-11-08   |   分类于 套题  |  访问: 41 次

1.铺瓷砖

【问题描述】
有一面很长很长的墙。
你需要在这面墙上贴上两行瓷砖。
你的手头有两种不同尺寸的瓷 砖,你希望用这两种瓷砖各贴一行。
瓷砖的长可以用分数表示,贴在第一行的每块瓷砖长度 为 A B ,贴在第二行的每块瓷砖长度为C D 。
本问题中你并不需要关心瓷砖的宽度。
QQ截图20161108153203
如上图所示,两排瓷砖从同一起始位置开始向右排列,两排瓷砖的第一块的左端的缝隙 是对齐的。
你想要知道,最短铺多少距离后,两排瓷砖的缝隙会再一次对齐。
【输入】
输入的第 1 行包含一个正整数 T,表示测试数据的组数。
接下来 T 行,每行 4 个正整数 A,B,C,D,表示该组测试数据中,两种瓷砖的长度分 别为A B 和 C D 。
【输出】
输出包含 T 行,第 i 行包含一个分数或整数,表示第 i 组数据的答案。
如果答案为分数, 则以“X/Y”的格式输出,不含引号。分数必须化简为最简形式。
如果答案为整数,则输出 一个整数 X。
【输入样例】
2
1 2 1 3
1 2 5 6
【输出样例】
1
5/2
【输入输出样例说明】
对于第一组数据,第一行瓷砖贴 2 块,第二行贴 3 块,总长度都为 1,即在距离起始位 置长度为 1 的位置两行瓷砖的缝隙会再次对齐。
对于第二组数据,第一行瓷砖贴 5 块,第二行贴 3 块,总长度都为5 2 。
【数据规模与约定】
对于 50%的数据,1≤A,B,C,D≤20 对于 70%的数据,T≤10 对于 100%的数据,T≤100,000,1≤A,B,C,D≤10,000

先通分,接着求最小公倍数,再化简一下,特判整数即可。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll a,b,c,d;
ll gcd(ll x,ll y){
	if(!y)
		return x;
	return gcd(y,x%y);
}
int main(){
	freopen("tile.in","r",stdin);
	freopen("tile.out","w",stdout);
	int n;
	scanf("%d",&n);
	while(n--){
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		ll g=gcd(b,d);
		ll fenmu=b*(d/g);
		a=a*(d/g);
		c=c*(b/g);
		ll fenzi=a*c/gcd(a,c);
		g=gcd(fenmu,fenzi);
		fenmu/=g;
		fenzi/=g;
		if(fenmu==1)
			printf("%lld\n",fenzi);
		else
			printf("%lld/%lld\n",fenzi,fenmu);
	}
	return 0;
}

2.小 Y 的问题

【问题描述】
有个孩子叫小 Y,一天,小 Y 拿到了一个包含 n 个点和 n-1 条边的无向连通图,图中的 点用 1~n 的整数编号。
小 Y 突发奇想,想要数出图中有多少个“Y 字形”。
一个“Y 字形”由 5 个不同的顶点 A、B、C、D、E 以及它们之间的 4 条边组成,其中 AB、 BC、BD、DE 之间有边相连,如下图所示。

22222
同时,无向图中的每条边都是有一定长度的。
一个“Y 字形”的长度定义为构成它的四条 边的长度和。
小 Y 也想知道,图中长度最大的“Y 字形”长度是多少。
【输入】
第一行包含一个整数 n,表示无向图的点数。
接下来 n 行,每行有 3 个整数 x、y、z,表示编号为 x 和 y 的点之间有一条长度为 z 的 边。
【输出】
输出包含 2 行。
第 1 行包含一个整数,表示图中的“Y 字形”的数量。
第 2 行包含一个整数,表示图中长度最大的“Y 字形”的长度。
【输入样例】
7
1 3 2
2 3 1
3 5 1
5 4 2
4 6 3
5 7 3
【输出样例】
5
9
【输入输出样例说明】
图中共有 5 个“Y 字形”,如图中用红色标出的部分所示。

3333333

44444
其中,长度最大的“Y 字形”是编号 3、5、7、4、6 的顶点构成的那一个,长度为 9。
【数据规模与约定】
对于 30%的数据,n≤10
对于 60%的数据,n≤2,000
对于 100%的数据,n≤200,000,1≤x,y≤n,1≤z≤10,000

第一个问题:如何求Y型数?

记录每个点的出边数,接着每次选取一条边,对于这条边的两个点u,v

u这点延伸出两个点的情况乘上v延伸出一个点的情况

同理v这点的情况也累加上去

设cnt[u]为n,cnt[v]为m

则sum+=(n-1)*(n-2)*(m-1)/2+(m-1)*(m-2)*(n-1)/2

当然要特判一下n<=2或者m<=2的一些情况

第二个问题:如何求最大值?

用maxn[x][3]这个数组记录从x出边前三大的值

dfs时每次取出一条边u->v

分别判断u作为头和v作为头的情况和各种恶心的特判即可AC
<

#include <cstdio>
#include <iostream>
using namespace std;
const int _maxn=200010;
int maxn[_maxn][3],n,ans,head[_maxn],k,cnt[_maxn];
long long sum;
bool vis[_maxn];
struct e{
	int to,dis,Next;
}edge[_maxn<<1];
void add(int x,int z){
	cnt[x]++;
	if(z>=maxn[x][0]){
		maxn[x][2]=maxn[x][1];
		maxn[x][1]=maxn[x][0];
		maxn[x][0]=z;
	}
	else if(z>=maxn[x][1]){
		maxn[x][2]=maxn[x][1];
		maxn[x][1]=z;
	}
	else if(z>maxn[x][2]){
		maxn[x][2]=z;
	}
}
void addedge(int x,int y,int z){
	++k;
	edge[k].Next=head[x];
	edge[k].to=y;
	edge[k].dis=z;
	head[x]=k;
}
void test(int u,int v,int dis){
	int temp=0;
	//某个点只有一边,或两个点都只有两边 
	if(maxn[u][1]==0 || maxn[v][1]==0 || (maxn[u][2]==0 && maxn[v][2]==0))
		return;
	//u这个点只有两条边,那么它作为Y的脚 
	else if(maxn[u][2]==0){
		temp=maxn[u][0]+maxn[u][1]; 
		if(maxn[v][0]==dis)
			temp+=maxn[v][1]+maxn[v][2];
		else if(maxn[v][1]==dis)
			temp+=maxn[v][0]+maxn[v][2];
		else
			temp+=maxn[v][0]+maxn[v][1];
	}
	//同理与v 
	else if(maxn[v][2]==0){
		temp=maxn[v][0]+maxn[v][1]; 
		if(maxn[u][0]==dis)
			temp+=maxn[u][1]+maxn[u][2];
		else if(maxn[u][1]==dis)
			temp+=maxn[u][0]+maxn[u][2];
		else
			temp+=maxn[u][0]+maxn[u][1];
	}
	else{
		//u点作为Y头 
		if(maxn[u][0]==dis || maxn[u][1]==dis || maxn[u][2]==dis){
			if(maxn[v][0]==dis)
				temp=maxn[v][1];
			else
				temp=maxn[v][0];
			temp+=maxn[u][0]+maxn[u][1]+maxn[u][2];
		}
		else{
			if(maxn[v][0]==dis)
				temp=maxn[v][1];
			else
				temp=maxn[v][0];
			temp+=maxn[u][0]+maxn[u][1]+dis;
		}
		//v点作为头 
		if(maxn[v][0]==dis || maxn[v][1]==dis || maxn[v][2]==dis){
			if(maxn[u][0]==dis)
				temp=max(temp,maxn[v][1]+maxn[v][0]+maxn[v][2]+maxn[u][1]);
			else
				temp=max(temp,maxn[v][1]+maxn[v][0]+maxn[v][2]+maxn[u][0]);
		}
		else{
			if(maxn[u][0]==dis)
				temp=max(temp,maxn[v][0]+maxn[v][1]+dis+maxn[u][1]);
			else
				temp=max(temp,maxn[v][0]+maxn[v][1]+dis+maxn[u][0]);
		}
	}
	if(temp>ans)
		ans=temp;
}
void calc(int u,int v){
	long long x1=cnt[u],x2=cnt[v];
	if(x1>2 && x2>1)
		sum+=((x1-1)*(x1-2)*(x2-1))>>1;
	if(x2>2 && x1>1)
		sum+=((x2-1)*(x2-2)*(x1-1))>>1;
}
void dfs(int x){
	vis[x]=true;
	int v;
	for(int i=head[x];i;i=edge[i].Next){
		v=edge[i].to;
		if(!vis[v]){
			dfs(v);
			test(x,v,edge[i].dis);
			calc(x,v);
		}
	}
}
int main(){
	freopen("question.in","r",stdin);
	freopen("question.out","w",stdout);
	int x,y,z;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,z);
		add(y,z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	dfs(1);
	printf("%lld\n%d\n",sum,ans);
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark