2018-03-02 • 于 CodeForces, 比赛阅读

CodeForces近期比赛题解

注意

此处比赛分别为Round462, 463, 464, 466，均为Div2

Round462

A

题面

Tommy有n个灯笼，BanBan有m个灯笼，Tommy拿走一个灯笼，分别从Tommy的和BanBan的选择一个灯笼，求最大乘积，假设双方都使用最优决策。

题解

枚举Tommy拿走的灯笼，及Tommy拿走该灯笼后所选的两个灯笼，求max即可

代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<climits>
const int MAXN=50+5;
std::priority_queue<int>pq,pq2,pq3,pq4;
int n,m,x,a[MAXN],b[MAXN];long long ans=LLONG_MAX,tmp;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)//hide x
	{
		tmp=LLONG_MIN;
		for(int j=1;j<=n;j++)
		{
			if(i==j) continue;
			for(int k=1;k<=m;k++)
				tmp=std::max(tmp,(long long)a[j]*b[k]);
		}
		//std::cout<<tmp<<std::endl;
		ans=std::min(ans,tmp);
	}
	std::cout<<ans;
	return 0;
}

B

题面

题面很玄乎。。其实就是求一个数字的形状中有k个圈的数。。

题解

首先排除的数，因为不超过即使圈数最大，也就36个圈
那么时间复杂度也就很小了。
然后输出8（两个圈）直至，然后输出6（一个圈）不住

代码

#include<cstdio>
int loop[10]={1,0,0,0,1,0,1,0,2,1},k,r;
int main()
{
	scanf("%d",&k);
	if(k>18*2) printf("-1\n"); else {
		r=k/2;
		k-=r*2;
		for(int i=1;i<=k;i++)
			printf("6");
		for(int i=1;i<=r;i++)
			printf("8");
	}
	return 0;
}

Round463

A

题面

给出一个字符串S，输出一个新字符串Str，使得S是Str的子串

题解

输出原字符串，再输出字符串的反转串即可
这样，从左往右和从右往左都是先正着再反着读

代码

#include<cstdio>
#include<cstring>
const int MAXN=1000+5;
char c[MAXN];int l;
int main()
{
	scanf("%s",c);
	l=strlen(c);
	printf("%s",c);
	for(int i=l-1;i>=0;i--)
		printf("%c",c[i]);
	return 0;
}

B

题面

给定一个函数，输出x在间该函数参数为x，值=k的参数数量

题解

显然函数结果，且时间复杂度较低，暴力求出各参数的值，做个二维前缀和即可

代码

#include<cstdio>
#include<algorithm>
const int MAXN=1000000+5;
const int MAXC=9+5;
int pfx[MAXC][MAXN],pfxr[MAXC][MAXN];
int g(int x)
{
	if(x<10) return x;
	int product=1;
	while(x)
	{
		if(x%10) product*=x%10;
		x/=10;
	}
//	printf("product x=%d\n",product);
	return g(product);
}
int main()
{
//	int tmp=0;
	for(int i=1;i<=1000000;i++)
	{
//int i=23333;
		pfxr[g(i)][i]++;
//		tmp=std::max(tmp,g(i));
	}
	for(int i=1;i<=9;i++)
		for(int j=1;j<=1000000;j++)
			pfx[i][j]=pfx[i][j-1]+pfxr[i][j];
	int q,l,r,k;
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d %d %d",&l,&r,&k);
		printf("%d\n",pfx[k][r]-pfx[k][l-1]);
	}
	return 0;
}

Round464

A

题面

给出各个人的相爱关系，寻找是否有A爱B，B爱C，C爱A

题解

对于每个i
关系坐标三层嵌套，看是否等于i

代码

#include<cstdio>
const int MAXN=10000+5;
int n,list[MAXN];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&list[i]);
	for(int i=1;i<=n;i++)
		if(list[list[list[i]]]==i)
		{
			printf("YES");
			return 0;
		}
	printf("NO");
	return 0;
}

B

题面

给出n种箱子，共k个物体，每个箱子必须装满，但是不一定k个物体都要装进去，求最大可装进去的物体数及箱子种类

题解

简单判断

代码

#include<cstdio>
#include<iostream>
const int MAXN=100000+5;
int k;long long max,maxcnt,maxid=1,box,n,tmp,r;
int main()
{
	std::cin>>n>>k;
//	scanf("%lld %d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		scanf("%lld",&r);
		box=n/r;
		tmp=box*r;
		if(tmp>max)
		{
			max=tmp;
			maxid=i;
			maxcnt=box;
		}
	}
//	printf("%lld %lld",maxid,maxcnt);
	std::cout<<maxid<<' '<<maxcnt;
	return 0;
}

酷暑一夏1

CodeForces近期比赛题解

注意

Round462

A

题面

题解

代码

B

题面

题解

代码

Round463

A

题面

题解

代码

B

题面

题解

代码

Round464

A

题面

题解

代码

B

题面

题解

代码

Vijos 1881闪烁的繁星题解

注意

Round462

A

题面

题解

代码

B

题面

题解

代码

Round463

A

题面

题解

代码

B

题面

题解

代码

Round464

A

题面

题解

代码

B

题面

题解

代码

Vijos 1881闪烁的繁星 题解

Vijos 1881闪烁的繁星题解