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