[CF987X]Codeforces Round #485 (Div. 2)

一句话评价这次比赛：时间真的好晚啊，题也BT的要死。

在Announcement的最后写道，Oh, and if there will be no bad things, round will be rated. I hope.

结果比赛最后半个小时果真出锅了…

题目链接

http://codeforces.com/contest/987

A. Infinity Gauntlet

大意

给出宝石的颜色，求出灭霸的无尽手套究竟少了哪几种宝石。

题解

打这道题真累…

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
string s;
int a[15];
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  cin>>s;
  if(s=="purple")a[1]++;
  if(s=="green")a[2]++;
  if(s=="blue")a[3]++;
  if(s=="orange")a[4]++;
  if(s=="red")a[5]++;
  if(s=="yellow")a[6]++;
 }
 cout<<6-n<<endl;
 for(int i=1;i<=6-n;i++)
 {
  if(!a[1])cout<<"Power",a[1]++;
  else if(!a[2])cout<<"Time",a[2]++; 
  else if(!a[3])cout<<"Space",a[3]++;
  else if(!a[4])cout<<"Soul",a[4]++;
  else if(!a[5])cout<<"Reality",a[5]++;
  else if(!a[6])cout<<"Mind",a[6]++;
  puts("");
 }
 return 0;
}

B. High School: Become Human

大意

给出 \(x\) 和 \(y\)，判断 \(x^y\) 大还是 \(y^x\) 大。

题解

一道纯正的数学题，解法如下：

先在两边取对数，就变成比较 \(\ln (x^y)\) 和 \(\ln (y^x)\) 的大小，

也就是比较 \(y * \ln x\) 和 \(x * \ln y\) 的大小了。

两边同时除以 \(xy\)，\( y * \ln x= \ln x / x\)，\(x * \ln y= \ln y / y\)。

这就是结论了。

PS：\(f(x)= \ln x / x\) 的图像事实上是长这样的。

事实上，当 \(x<e\) 时，函数是单调递增的，\(x=e\) 时函数有最大值，\(x>e\) 时函数单调递减。

#include <stdio.h>
#include <math.h>
#define e 2.71828182845 
int x,y;
int main()
{
 scanf("%d%d",&x,&y);
 long double ans1=log(x)/x,ans2=log(y)/y;
 if(ans1==ans2)puts("=");
 else if(ans1>ans2)puts(">");
 else puts("<");
 return 0;
}

C. Three displays

大意

有一个序列，序列中的每个数字都有一个费用，现在要找一个长度为 \(3\) 的严格上升子序列，使得这三个数字的费用和最小。

题解

其实跟LIS并没有什么太大关系…

可以每次枚举一个点，向两边扩散，寻找左边较小的数字中的最低费用，右边较大数字中的最低费用，就可以解决这道题了。

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define maxn 5005
using namespace std;
int n,f[5005],a[5005],ans,c[5005];
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 for(int i=1;i<=n;i++)
  scanf("%d",&c[i]);
 int ansc=1000000000;
 for(int i=2;i<=n-1;i++)
 {
  int lmin=1000000000,rmin=1000000000;
  for(int j=i-1;j>=1;j--)
   if(a[j]<a[i])lmin=min(lmin,c[j]);
  for(int j=i+1;j<=n;j++)
   if(a[j]>a[i])rmin=min(rmin,c[j]);
  ansc=min(ansc,c[i]+lmin+rmin);
 }
 if(ansc!=1000000000)printf("%d",ansc);
 else printf("-1");
 return 0;
}