Fork me on GitHub

Codeforces Round 72 题解报告

qwq

A.

第一眼看上去貌似是个找规律$O(1)$题,实际看了一下,确实是找规律$O(1)$题.所以就开始愉快的找规律,于是就有了以下的提交记录:

TIM截图20190906182428.png

emmm….

[_PWH%XYB$@_KDI[A3)]2]J.jpg

QAQ然后我们考虑一下正解.

我们设原来我们有$str in exp$,我们设我们分给$str x$点的$exp$,分给$in y$点的$exp$,那么显然有:

发现上边的这个方程,通过将$y$用$exp-x$代替之后,我们可以解出$x$的具体范围.而且我们可以发现:所有$x$的取值范围一共只有$exp + 1$种,所以就可以愉快的求出答案了.

最后别忘了判断$exp$为$0$的情况.

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
int str,in,exp;
cin>>str>>in>>exp;
if (exp==0){
if(str>in)
cout<<"1"<<endl;
else
cout<<"0"<<endl;
continue;
}
if(in+exp-str<0){
cout<<exp+1<<endl;
continue;
}
int ans=min(exp+1,(exp+1)-max(0ll,((in+exp-str)/2+1)));
if ( ans < 0 )
ans = 0;
cout<<ans<<endl;
}
return 0;
}

B.

这么可爱的怪兽我怎么可能忍心去打它呢

我们看到题,首先想到,如果我们砍一刀,这个怪兽不死,那么它如果长出来的头大于我们我们这次砍掉的头.那么我们这次的操作显然没用.所以,在前几刀砍不死怪兽的情况下,我们需要最大化每一次砍头时的$d_i-h_i$,同时我们发现.在某一次砍头中,如果这次的$d_j$非常大,大到一下子可以把怪兽剩下的头砍完.我们就可以不用管这次砍头的副作用$h_j$了.

所以我们维护两个最大值,即$d_i-h_i$的最大值以及$d_i$的最大值,然后直接找题意做即可.

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
int maxs=-1e16;
int Damage=-1e16;
cin>>n>>x;
for(int i=1;i<=n;i++) {
int tx,ty;
cin>>tx>>ty;
maxs=max(maxs,tx);
Damage=max(Damage,tx-ty);
}
if ( x <= maxs ) {
cout << "1" << endl;
continue;
}

if(Damage<=0){
cout<<"-1"<<endl;
continue;
}

int now = ( x - maxs ) / Damage;
if ( now * Damage < x - maxs )
now+=2;
else
now++;
cout<<now<<endl;
}
return 0;
}

C.

通过读题,我们可以发现一个很重要的东西:$\sum_{i=1}^t len_i<=2*10^5$.

通过这个性质,我们可以发现,我们在枚举每一次的区间时,这个区间的最长长度为$log_2len$.

然后就做完了??

我们枚举一下每个区间的左/右端点,然后直接暴力统计答案就好了.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 200000 + 10;
int t,nex[N];
char s[N];
int main() {
scanf("%d",&t);
while(t--) {
scanf("%s",s+1);
int n=strlen(s+1);
nex[n+1]=n+1;
for(int i=n;i>=1;i--) {
if(s[i]=='0') nex[i]=nex[i+1];
else nex[i]=i;
}
int ans=0;
for(int i=1;i<=n;i++){
int now=0;
for(int j=nex[i];j<=min(n,nex[i]+20);j++){
now=now*2+s[j]-'0';
if(now==j-i+1) ans++;
}
}
printf("%d\n", ans);
}
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Codeforces Round 72 题解报告

文章作者:KRrrrrrrrr

发布时间:2019年09月11日 - 18:09

最后更新:2019年11月05日 - 08:11

原始链接:http://krrrr.xyz/2019/09/11/题解报告/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。