[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,于是这样的程序就蒙混过关了。

其实早在被hacked之前,本蒟蒻就意识到自己那个错误版本的问题,但我还是锁了题,然后疯狂地hack其他人的程序,结果效果极好,get 5个 Successful hacking attempt。

所以现在还是庆幸那个数据被删掉了,不然自己的rating就麻烦了。

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;
}

发表评论

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