Bluesky

EducationalCodeforcesRound90(Div.2)

Educational Codeforces Round 90 (Rated for Div. 2)

1373A - Donut Shops

题目大意：有两家相互竞争的甜甜圈店。
第一家商店零售甜甜圈：每个甜甜圈售价 a 美元。
第二家商店只批量出售甜甜圈：一盒 b 个甜甜圈售价 c 美元。
如果你想买 x 个甜甜圈用最少的钱
你能买多少个甜甜圈，这样第一家店的甜甜圈绝对比第二家店便宜？
你能买多少个甜甜圈，这样在第二家店比第一家店便宜？

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

const long long MAXN=1e9;
int main(){
    int t;
    std::cin>>t;
    while(t--){
        long long a,b,c;
        std::cin>>a>>b>>c;
        if(a*b<=c) std::cout<<"1 -1"<<"\n";
        else if(a>=c){
            std::cout<<"-1 "<<b<<"\n";
        }else{
            std::cout<<"1 "<<MAXN/b*b<<"\n";
        }
    }
    return 0;
}

1373B - 01 Game

题目大意：有一由01组成的字符串，Alice和Bob轮流删除两个不同的相邻字符删除，Alice是先手，如果有一个人无法删除他就输了，两个同学都会最佳发挥，如何确定Alice是否能赢，如果Alice赢了输出”DA”，输了输出”NET”。

解题思路：分别统计0的个数1的个数，较小值为偶数则Alice输了，若较小值为奇数则Alice赢了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

int main(){
    int t;
    std::cin>>t;
    while(t--){
        std::string a;
        std::cin>>a;
        int sum0=0,sum1=0;
        for(int i=0;i<a.lenght();i++){
            if(a[i]=='0') sum0++;
            if(a[i]=='1') sum1++;
        }
        int minn=std::min(sum0,sum1);
        if(minn&1) std::cout<<"DA"<<"\n";
        else std::cout<<"NET"<<"\n";
    }
}

1373C - Pluses and Minuses

题目大意：给一个只含$”+””-“$的字符串 $s$ ，按如下伪代码操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
res = 0
for init = 0 to inf
    cur = init
    ok = true
    for i = 1 to |s|
        res = res + 1
        if s[i] == '+'
            cur = cur + 1
        else
            cur = cur - 1
        if cur < 0
            ok = false
            break
    if ok
        break

输出最后的 $res$ 值。

解题思路：我们来注释一下每一句代码的意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
res = 0 //初始值
for init = 0 to inf 
    cur = init //cur的基础值会不断的+1 以达到循环终止条件
    ok = true //for循环终止条件
    for i = 1 to |s| //遍历字符串长度
        res = res + 1 //记录经历了的字符个数
        if s[i] == '+'
            cur = cur + 1 
        else
            cur = cur - 1
        if cur < 0 //如果串前部分减号多余加号就跳出内循环
            ok = false
            break
    if ok
        break

直接按照题目意思提交会TLE，可以优化循环次数的地方在于每次结束时cur=-1内循环后cur会+1，则下次内循环至此处时会是cur=0，直接从这里开始就行，res加上原来循环过的长度。

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>

const int INF=0x3f3f3f3f;

int main(){
    int t;
    std::cin>>t;
    while(t--){
        std::string s;
        std::cin>>s;
        long long res=0;
        long long temp=0;
        for(int i=0;i<=INF;i++){
            long long cur=0;
            bool ok=1;
            for(int j=temp;j<s.length();j++){
                res++;
                if(s[j]=='+') cur++;
                else cur--;
                if(cur<0){
                    ok=0;
                    res+=(j+1);
                    temp=j+1;
                    break;
                }
            }
            if(ok) break;
        }
        std::cout<<res<<"\n";
    }
    return 0;
}

1373D - Maximum Sum on Even Positions

题目大意：一组下标从0开始的数组，仅通过一次子数组反转，使得偶数位上的和最大

解题思路：对于一个偶数位来说只有与他的前一位交换或者与他的后一位交换，所以对于整体的反转也只有两种情况，我们需要找出与前一位交换对与偶数位和贡献最大的子串和与后一位交换对偶数位和贡献最大的子串，比较一下贡献值，从下标1开始和前一个数交换贡献值为 $a[i]-a[i-1]$ 从下标2开始和前一个数交换交换的贡献值为 $a[i-1]-a[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
#include <bits/stdc++.h>
 
int main(){
    int t;
    std::cin>>t;
    while(t--){
        int n;
        std::cin>>n;
        long long a[200009],ans=0;
        for(int i=0;i<n;i++){
            std::cin>>a[i];
            if(i%2==0) ans+=a[i];
        }
        long long sum1=0,maxn=0,sum2=0;
        for(int i=1;i<n;i+=2){
            sum1=std::max((long long)0,a[i]-a[i-1]+sum1);
            maxn=std::max(maxn,sum1);
        }
        for(int i=2;i<n;i+=2){
            sum2=std::max((long long)0,a[i-1]-a[i]+sum2);
            maxn=std::max(maxn,sum2);
        }
        std::cout<<ans+maxn<<"\n";
    }
    return 0;
}