初次打codeforces

今天凌晨开始了的第一把CF(并不是TC的CF),第一次做全英文的题目,第一次在国外的的平台上比赛,还是有一些鸡冻的。昨天大致的看了看codeforces,感觉确实比国内的一些平台做得好(在比赛中的体验也确实是这样),特别是看到传说中的tourist大神,看到他的rating曲线,感觉好牛逼啊。。。。。。


看了看题目,前面两道题的确是大水题,注意数据范围基本上可以一次性AC。

因为是全英文的理解题意还是需要一段时间的(原谅我这个英语渣渣),前面两道题花了40分钟,感觉应该再快一点的(第一次打这个比赛总是小心翼翼的)。
到了第三题,光看懂题目的意思我就花了二十多分钟差不多半个小时,看懂题目以后觉得是一个贪心题,然后找各种优化,但是总是超时,然后继续找办法优化,然后就一直一直卡在这里了(当我意识可以看看后面有没有题可以的时候,就只有十分钟左右了),就这样我的第一次CF就这样结束了。。。。。


只A了两题,第一次比赛以后我的状态是这样的

今天早上起来看了看官方的题解,发现昨天的C题我的思路是对的,但是我忽视了一个两个单词:not decreasing 他还特别设置为粗体,但是我就是没看到,求英语不好的我心理阴影面积有多大。。。
下面贴上我C题的题解吧:

题目大意

安东正在玩一个非常有趣的电脑游戏,但现在他被困在一个级别。要传递到下一个级别,他必须准备n药水。

安东有一个特殊的水壶,可以在x秒内准备一瓶药水。此外,他知道两种类型的法术,可以更快的准备药水的过程。

  • 这种类型的法术加速了一个药水的准备时间。有这种类型的m个咒语,其中的第i个成本bi manapoints和改变每个药水的准备时间为ai而不是x。
  • 这种类型的法术会立即准备一些魔药。有这样的法术,第i个成本di manapoints和立即创建ci药剂。

安东可以使用不超过一个第一类型的法术,不超过一个第二类型的法术,并且使用的manapoint的总数不应超过s。考虑到所有的法术都在瞬间使用,在安东开始准备魔药之前。

输入

输入的第一行包含三个整数n,m,k(1≤n≤2·109,1≤m,k≤2·105) - Anton必须生成的药剂数量,第一类型和第二类型的法术的数量。

输入的第二行包含两个整数x和s(2≤x≤2·109,1≤s≤2·109) - 准备一个部分所需的初始秒数和Anton可以使用的manapoint数。

第三行包含m个整数ai(1≤ai<x) - 如果使用第一类型的第i个法术,则准备一个药剂所需的秒数。

第四行包含m个整数bi(1≤bi≤2·109) - 使用第一类型第i个咒语的manapoints数量。

在第五行中有k个整数ci(1≤ci≤n) - 如果使用第二类型的第i个咒语,将立即创建的药剂数。保证ci不减小,即如果i <j,则ci≤cj。

第六行包含k个整数di(1≤di≤2·109) - 使用第二个类型的第i个咒语所需的manapoint数量。保证di不减小,即如果i <j,则di≤dj。

输出

打印一个整数 - 为了准备n个药水,花费的最少时间。

解题思路

  • 因为后面给的第二种类型的法术是递增的(包括获得的药水数量和消耗的体力),这样我们就可以使用二分查找(upper_bound函数)找到,进行第一种类型的法术选择以后的第二种的最优策略,这样时间复杂度就是O(m*logk)了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstring>
#include<algorithm>
#include<utility>

using namespace std;
#define MAXSIZE 200005
#define in(a) scanf("%d",&a)

long long n,m,k,x,s;
long long a[MAXSIZE],b[MAXSIZE],c[MAXSIZE],d[MAXSIZE];

void solve()
{
long long i;
while(cin>>n>>m>>k)
{
cin>>x>>s; //数据输入
for(i=0;i<m;i++)
cin>>a[i];
for(i=0;i<m;i++)
cin>>b[i];
for(i=0;i<k;i++)
cin>>c[i];
for(i=0;i<k;i++)
cin>>d[i];

a[m]=x;
b[m]=0;
long long imin,o,e;
imin=n*x;
for(i=0;i<=m;i++)
{
o=s-b[i];
if(o<0)
continue;
e=upper_bound(d,d+k,o)-d;
if(e)
imin=min(a[i]*(n-c[e-1]),imin);
else //注意不进行第二次选择的情况
imin=min(a[i]*n,imin);
}
cout<<imin<<endl;
}
}

int main()
{
solve();
return 0;
}

吐槽

  • 在cf的比赛中,比赛时提交的程序只进行一部分测试点的测试,比赛结束以后重新验证测试点会多好多
  • 初始rating积分是1500,我竟然少了几十分。。。。听说这个积分的计算用到的是一个叫Elo rating system的东西,看起来好高大上的样子。(维基的解释