Codeforces Hello 2023题解A-C

2023/1/4 算法竞赛 题解 C++ Codeforces Hello 2023

第一次熬夜打比赛:D

A. Hall of Fame

题面

思路比较明显，只用关注最左边的R和最右边的L的位置

AC代码： 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
char ch[N];
int main() {
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        bool flagl=false,flagr=false;
        int l,r;
        for(int i=1;i<=n;i++)
        {
            cin>>ch[i];
            if(!flagr&&ch[i]=='R')
                r=i,flagr=true;
        }
        for(int i=n;i>=1;i--)
        {
            if(!flagl&&ch[i]=='L')
            {
                l=i,flagl=true;
                break;
            }
        }
        if(!flagl||!flagr)
        {
            cout<<-1<<'\n';
        }
        else
        {
            if(l+1<r)
                cout<<-1<<'\n';
            else if(l<r)
                cout<<l<<'\n';
            else
                cout<<0<<'\n';
        }
    }
    return 0;
}

B. MKnez’s ConstructiveForces Task

题面

一道数学题 若2 ∣ n 则 时可构造 时任意构造和相同

若2 ∤ n 同理 有 ∵∀i = 1, 2...n, si ≠ 0 ∴ 若n = 1或n = 3, 无解 若且可令则

AC代码： 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if(n==1||n==3)
            cout<<"NO"<<'\n';
        else
        {
            cout<<"YES"<<'\n';
            if(n%2==0)
            {
                for(int i=1;i<=n;i++)
                {
                    if(i%2==0)
                        cout<<1<<" ";
                    else
                        cout<<-1<<" ";
                }
            }
            else
            {
                for(int i=1;i<=n;i++)
                {
                    if(i%2==0)
                        cout<<(n-1)/2<<" ";
                    else
                        cout<<(3-n)/2<<" ";
                }
            }
            cout<<'\n';
        }
    }
    return 0;
}

C. Least Prefix Sum

题面

要保证m项的前缀和最小，只需在m前总体是降的，在m后总体是增的，可以想到用从m开始的前缀和刻画。

将新的前缀和与0作比较，如果与预习不符就将经过的一个最优值取反，可以用优先队列保存最优值。

AC代码： 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
int main() {
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int ans=0;
        priority_queue<int> s1,s2;
        ll sum=0;
        for(int i=m;i>1;i--)
        {
            sum+=a[i];
            if(a[i]>0)
                s1.push(a[i]);
            while(sum>0)
            {
                sum-=2*s1.top();
                s1.pop();
                ans++;
            }
        }
        sum=0;
        for(int i=m+1;i<=n;i++)
        {
            sum+=a[i];
            if(a[i]<0)
                s2.push(-a[i]);
            while(sum<0)
            {
                sum+=2*s2.top();
                s2.pop();
                ans++;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}
img_show