[CF934X]Codeforces Round #462 (Div.2)

这次比赛真的在一个很好的时候举办了,这次比赛前,老师要求我们全部到班比赛,否则就怀疑我们去旁边电影院了(你懂的):)

比赛充分展现了各位出题 dalao 的大智慧,成功坑倒一片人(当然包括我),难度嘛,绝对达到了极高水平(比如 Div.2 的 D 题),题目中还有无数陷阱,比赛结束后,哀叹声不断。

好了,话不多说,进入正题(我读完题后才知道自己过的都是假春节)

题目链接

http://codeforces.com/contest/934

A. A Compatible Pair

大意

Tommy 有 \(n\) 个灯笼,Banban 有 \(m\) 个灯笼,Tommy 会将自己的一个灯笼藏起来,随后 Banban 会在 Tommy 剩下的灯笼中挑一个,再在自己的灯笼中挑一个,这对灯笼的亮度将是两灯笼亮度之积(灯笼的亮度可能有负数,这会坑死一大群人!)。

Tommy 想让这对灯笼的亮度尽可能小,而 Banban 想让亮度尽可能大,你所要做的就是把灯笼亮度求出来。

题解

这道题表面上十分简单,但事实上暗藏各种坑,关键在于,Tommy 会去遮挡哪盏灯笼呢?

首先贴出一个最简单的错误贪心版本:

#include <iostream>
#include <algorithm>
using namespace std;
long long n,m,a[55],b[55];
int main()
{
 cin>>n>>m;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 for(int i=1;i<=m;i++)
  cin>>b[i];
 sort(a+1,a+n+1);
 sort(b+1,b+m+1);
 cout<<a[n-1]*b[m];
 return 0;
}

很简单粗暴,但忽略了负数和负数相乘的这种情况,于是很快就被 hacked 了(但竟然 PP 了)。

所以我们还是要用常规的方法来想这个问题,那就是枚举遮挡的灯笼。

在枚举遮挡灯笼的时候,我们要把剩下灯笼的两两之积(当然是 Tommy 的一盏灯笼和 Banban 的一盏灯笼了)比较一下,算出一个最大值,然后呢,求出这些最大值中的最小值,这就是最终的答案了。

所以接下来应该是正确的版本了(当然还有其他的方法,不过这个方法是编程难度最低的):

#include <iostream>
#include <algorithm>
#define INF 0x7fffffffffffffff
using namespace std;
long long a[55],b[55];
int main()
{
 int n,m;
 cin>>n>>m;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 for(int i=1;i<=m;i++)
  cin>>b[i];
 long long res=INF;
 for(int i=1;i<=n;i++)
 {
  long long now=-INF;
  for(int j=1;j<=n;j++)
   if(j!=i)
    for(int k=1;k<=m;k++)
     now=max(now,a[j]*b[k]);
  res=min(res,now);
 }
 cout<<res;
 return 0;
}

PS:据出题人说,在原来,有 10 个 pretests,那个错误版本会WA在最后一个 pretest,但出题人删去了包括最后一组数据在内的 3 组 pretests,于是这样的程序就蒙混过关了。

B. A Prosperous Lot

大意

输入数 \(k\),任意输出一个正好含 \(k\) 个loop的数字(loop:就是数字中封闭的区域,例如 \(4\) 有一个 loop,\(1\) 没有 loop,\(8\) 有两个 loop),要求该数字须小于 \(10^{18}\)。

题解

一直觉得这道题应该放在第一题,题目开放性之强,实在让人出乎意料,可以输出的数字很多,对数字几乎没有要求。

当然,如果要求的 loop 数超过了 \(36\) 个(在这种情况下,数字将超过 \(10^{18}\)),注意要输出 \(-1\)。

#include <stdio.h>
using namespace std;
const int loop[]={1,0,0,0,1,0,1,0,2,1};
int main()
{
 int k;
 scanf("%d",&k);
 if(k>36)printf("-1");
 else if(k<=18)
 {
  for(int i=1;i<=k;i++)
   printf("9");
 }
 else
 {
  for(;k>=2;k-=2)
   printf("8");
  if(k)printf("9");
 }
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注