牛客小白月赛52（重现赛）
前言：
能够学到不少东西的一场比赛
A
第一题主要是要看一些细节，细节样例其实都给了。
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
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int cnt_1=0;
int cnt_2=0;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
if(s[0]=='8'&&s[2]=='0'&&s[3]<='5'&&s[3]>'0')
{
cnt_1++;
}
else if(s[0]<'8'||s[0]=='8'&&s[2]=='0'&&s[3]=='0')
{
}
else
{
cnt_2++;
}
}
cout<<cnt_1<<" "<<cnt_2<<'\n';
}
}
|
B
第二题有一个贪心的点就是第一次去找尽可能靠前的数字大于或等于5，然后往前是4的去更新，注释见代码。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n=s.length();
s="0"+s;
int flag=0;
for(int i=1;i<=n;i++)
{
if(s[i]>='5')
{
flag=i;
break;
}
}
if(!flag)
{
for(int i=1;i<=n;i++)
{
cout<<s[i];
}
cout<<'\n';
}
else
{
int x=flag;
if(x==1)
{
s[0]='1';
cout<<s[0];
for(int i=1;i<=n;i++)
{
cout<<0;
}
cout<<'\n';
continue;
}
else
{
for(int i=flag-1;i>=1;i--)
{
if(s[i]=='4')
{
x=i;
}
else
{
break;
}
}
if(x==1)
{
s[0]='1';
cout<<s[0];
for(int i=1;i<=n;i++)
{
cout<<0;
}
cout<<'\n';
continue;
}
else
{
s[x-1]+=1;
for(int i=1;i<=x-1;i++)
{
cout<<s[i];
}
for(int i=x;i<=n;i++)
{
cout<<0;
}
cout<<'\n';
}
}
}
}
}
|
C
C题再经历了几分钟线段的抽象思路后，发现就是个差分，抬头看了眼数据范围，更是差分加前缀和即可。
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
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int a[N];
int b[N];
int sum[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int opt;
cin>>opt;
if(opt==1)
{
int x,y;
cin>>x>>y;
a[x]++;
a[y+1]--;
}
else if(opt==2)
{
int x;
cin>>x;
a[x]++;
}
else
{
int x;
cin>>x;
a[1]++;
a[x+1]--;
}
}
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
int ans=0;
sort(sum+1,sum+1+n);
for(int i=1;i<=n;i++)
{
if(sum[i]==sum[1])
{
ans++;
}
else
{
break;
}
}
cout<<m-sum[1]<<' '<<ans;
}
|
D
详细讲解一下D的思路。
本题需要用到滑动窗口，断环成链，以及维护区间最大值
为什么需要滑动窗口，因为如果已经满足条件的话，右窗口再继续往后滑动一定是不优秀的，但左窗口往后滑动可能会产生优秀的答案。
为什么需要断环成链，因为他是一个环，*2变成链会更加方便进行滑动窗口。
为什么需要维护区间最大值，因为题目有说，怎么维护，直接用map进行维护，map默认是以第一维的pair进行排序的，只需要右移加进来，左移如果等于0删去，然后每次取rbegin.first即可
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
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4e5+100;
ll a[N];
ll b[N];
ll sum;
map<ll,ll >mp;
int main()
{
ll n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
sum+=a[i];
}
if(sum<s)
{
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
b[i+n]=b[i];
}
ll ans=1e18;
ll r=1;
sum=a[1];
mp[b[1]]++;
for(int i=1;i<=2*n;i++)
{
while(r<2*n&&sum<s)
{
r++;
mp[b[r]]++;
sum+=a[r];
}
if(sum<s)
{
continue;
}
ans=min(ans,mp.rbegin()->first);
mp[b[i]]--;
if(mp[b[i]]==0)
{
mp.erase(b[i]);
}
sum-=a[i];
}
cout<<ans;
}
|
这里也有一种二分加ST表的维护
二分主要是向后取找到第一个能够满足条件的，因此和滑动窗口性质是一样的，至于ST表则是直接进行一个区间的维护，实际上也是完全没问题的。
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
55
56
57
58
59
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std ;
using ll = long long ;
const int N = 4e5 + 100,M = 20 ;
int n,m ;
int a[N],b[N] ;
ll s[N] ;
int f[N][M] ;
void init(){
for(int len = 0 ; len < M ; len ++){
for(int i = 1; i + (1 << len) - 1 <= 2 * n ; i++){
if(!len) f[i][len] = b[i] ;
else{
f[i][len] = max(f[i][len-1] , f[i + (1 << len - 1)][len - 1]) ;
}
}
}
}
int query(int l,int r){
int len = r - l + 1;
int k = log(len) / log(2) ;
return max(f[l][k],f[r - (1 << k) + 1 ][k]) ;
}
int main(){
scanf("%d%d",&n,&m) ;
for(int i = 1; i <= n ; i ++)
scanf("%d",&a[i]),a[i+n] = a[i] ;
for(int i = 1 ;i <= 2 * n ; i ++) s[i] = s[i-1] + a[i] ;
for(int i = 1 ; i <= n ; i ++)
scanf("%d",&b[i]),b[i+n] = b[i] ;
init() ;
int ans = 0x3f3f3f3f ;
for(int i = 1 ; i <= n ; i ++){
int id = lower_bound(s+i,s+i+n,s[i-1] + m) - s ;
if(s[id] - s[i-1] >= m && id - i + 1 <= n){
ans = min(ans,query(i,id)) ;
}
}
if(s[n] < m) ans = -1 ;
printf("%d\n",ans) ;
return 0 ;
}
|
E
E题其实就是查每一个数字前面有哪些数字比他小，感觉树状数组大材小用，两个二分应该可以秒了。
不过这个树状数组求逆序对的板子还是可以介绍一下，先离散化去重，不过不是和逆序对一样一边求一边放，而是全部先放进去，然后每次减去自己，再进行求解，感觉还是二分更直观的。
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
int lowbit(int i)
{
return i&(-i);
}
const int N=1e6+109;
int a[N];
const int mod=998244353;
int cnt=0;
void update(int p,ll x)
{
while(p<=cnt)
{
a[p]+=x;
p+=lowbit(p);
}
}
ll query(int p)
{
ll res=0;
while(p)
{
res+=a[p];
p-=lowbit(p);
}
return res;
}
ll query(int l,int r)
{
return query(r)-query(l-1);
}
int n,k;
vector<ll>b[N];
ll e[N];
unordered_map<ll,int>f;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
while(x--)
{
int y;
cin>>y;
b[i].push_back(y);
e[++cnt]=y;
}
}
sort(e+1,e+1+cnt);
cnt=unique(e+1,e+1+cnt)-e-1;
for(int i=1;i<=cnt;i++)
{
f[e[i]]=i;
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int x:b[i])
{
update(f[x],1);
}
}
for(int i=1;i<=n;i++)
{
for(int x:b[i])
{
update(f[x],-1);
}
for(int x:b[i])
{
int y=max(0,k-x);
int pos=lower_bound(e+1,e+1+cnt,y)-e;
ans=(ans+query(pos,cnt))%mod;
}
}
cout<<ans%mod;
}
|
直接全部放进一个数组里进行lower_bound，注意/2
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
const int M=998244353;
vector<int> q[N];
vector<int> e;
int n,k,ans=0;
inline int calcu(int x){
int pp=lower_bound(e.begin(),e.end(),x)-e.begin();
return e.size()-pp;
}
inline int calcu1(int x,int y){
int pp=lower_bound(q[x].begin(),q[x].end(),y)-q[x].begin();
return q[x].size()-pp;
}
signed main(){
int x,y;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i){
scanf("%lld",&x);
for(int j=1;j<=x;++j){
scanf("%lld",&y);
q[i].push_back(y);
e.push_back(y);
}
sort(q[i].begin(),q[i].end());
}
sort(e.begin(),e.end());
for(int i=1;i<=n;++i){
x=q[i].size();
for(int j=0;j<x;++j){
y=q[i][j];
ans=(ans+calcu(k-y)-calcu1(i,k-y))%M;
}
}
ans=ans%M;
printf("%lld\n",ans/2);
return 0;
}
|
F
1
| dp[i]表示这个骑士，能量消耗为i时候的最大伤害值，求出这个是相当于把每个骑士限制为了要么出这个新技能要么不出,这个实际上只是一个01背包
|
1
| dp[i][j]表示到第i个骑士时候造成j伤害的方案数，不过由于伤害很大，但大于或等于m的实际上可以看成m，这样就避免了数组爆了
|
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
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=998244353;
const int N=3e3+10;
int a[N],b[N];
int dp[N];
ll dpp[N][N];
int main(){
dpp[0][0]=1;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int s;
cin>>s;
for(int j=1;j<=s;j++)
{
cin>>a[j];
}
int sum=0;
for(int j=1;j<=s;j++)
{
cin>>b[j];
sum+=b[j];
}
for(int j=0;j<N;j++) dp[j]=-1;
dp[0]=0;
for(int j=1;j<=s;j++)
{
for(int k=sum;k>=0;k--)
{
if(dp[k]>=0){
dp[k+b[j]]=max(dp[k+b[j]],dp[k]+a[j]);
}
}
}
for(int j=0;j<=sum;j++)
{
if(dp[j]==-1) continue;
for(int k=m;k>=0;k--)
{
int x=min(k+dp[j],m);
dpp[i][x]=(dpp[i][x]+dpp[i-1][k])%mod;
}
}
}
cout<<dpp[n][m];
return 0;
}
|
