Educational Codeforces Round 90 (Rated for Div. 2)(ABCD题解)

63 阅读 0 评论 42 点赞

我是靠谱客的博主背后苗条，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 90 (Rated for Div. 2)(ABCD题解)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

题目大意：
有两个麦甜甜圈的店铺，第一个只单卖，价格是 $a$ 元一个，第二个店铺是整箱卖，一箱 $b$ 个 $c$ 元，只能整箱卖，问你在第一个店铺买多少甜甜圈比第二个店铺便宜，如果不能输出-1，问你在第二个店铺买多少甜甜圈比第一个店铺便宜，如果不能输出-1。
思路：
如果 $a < c :$ 说明第一个店铺单价低于第二个店铺输出数量 $1$ 即可，否则 $- 1$ 。
如果 $c / b < a$ :说明第二个店铺单价低于第一个店铺，把 $b$ 移过去，就是 $a * b$ 也就是数量 $b$ 个 $a$ ，输出 $b$ 即可，否则输出 $- 1$ 。
代码：

#include<iostream>
using namespace std;

typedef long long int ll;
void solved(){
    ll a,b,c;cin>>a>>b>>c;
    if(a < c){
        cout<<"1"<<" ";
    }else {
        cout<<"-1"<<" ";
    }
    if(c >= a * b){
        cout<<"-1"<<endl;
    }else{
        cout<<b<<endl;
    }
}
int main(){
    int t;cin>>t;
    while(t--)solved();
    return 0;
}

在这里插入图片描述

题目大意：
给你一个只包含 $01$ 的字符串，然后相邻的不同的字符可以被消除比如 $01, 10$ ，然后Alica先手，Bob后手，问你最终谁能赢。
思路：
注意到这个字符串 $01$ 消除没有策略可言，只要能消除就一直消除，记录一下消除的次数，如果是奇数说明先手赢，偶数说明后手赢，消除的时候用栈维护一下就好了。
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<string>
using namespace std;

void solved(){
    string s;cin>>s;
    stack<char>st;
    int cnt = 0;
    for(int i = 0; i < s.size(); i++){
        if(st.empty()){
            st.push(s[i]);
        }else{
            if(s[i] == '1'){
                if(st.top() == '0'){
                    cnt++;st.pop();
                }else{
                    st.push(s[i]);
                }
            }else{
                if(st.top() == '1'){
                    cnt++;st.pop();
                }else{
                    st.push(s[i]);
                }
            }
        }
    }
    if(cnt & 1)cout<<"DA"<<endl;
    else cout<<"NET"<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)solved();
    return 0;
}

在这里插入图片描述

题目大意：

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

模拟这个程序。
思路：
直接模拟肯定会超时，注意到它每次都是从 $1$ 开始，那么肯定重复计算了很多次，我们可以直接 $O (n)$ 把要计算的全部加上来，最后再加上整个字符串长度就好了，每个 $c u r < 0$ 的地方加一下长度然后 $i n i t + + 转化为 c u r = 0$ 这样就行了。
代码：

/*
 * Author:  zixi
 * Created Time:  2020/7/11 16:40:00
 */
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
/*
3
--+-
---
++--+-
*/
typedef long long int ll;
void solved(){
    string s;cin>>s;
    ll res = 0;
    ll cur = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '+')cur++;
        else cur--;
        if(cur < 0){
            res += (i + 1);
            cur = 0;
        }
    }
    res += s.size();
    cout<<res<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)solved();
    return 0;
}

在这里插入图片描述

题目大意：
给你一个数组，你可以选择任意一个子数组进行翻转，求 $m a x (Σ (a i)) ， i 为偶数$ 。
思路：看到这个题目如果能想到最大子段和就可以秒了这题，事实上这就是一个最大字段和的变种，对于每个偶数位置的值，他只能前后翻转，然后我们可以预处理前后翻转的增量，然后做一个最大字段和，然后偶数位置的和+ $m a x (d e l t a 1, d e l t a 2)$ 就是答案了。最大子段和就是一个子数组翻转的结果。
代码：

#include<iostream>
#include<algorithm>
using namespace std;
/*
3
5
17 6 4 4 4
7
19 5 13 11 12 13 5
1
213567876
*/
const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn];
ll dp1[maxn],dp2[maxn];
void solved(){
    int n;cin>>n;
    ll sum = 0;
    for(int i = 0; i < n; i++){
        cin>>a[i];
        if(i % 2 == 0)sum += a[i];
    }    
    for(int i = 0; i < n; i++){
        if(i + 1 < n && i & 1){
            dp1[i] = a[i] - a[i + 1];
        }else if(i + 1 < n){
            dp2[i] = a[i + 1] - a[i];
        }
    }
    ll s = 0;
    ll delta1 = 0;
    for(int i = 0; i < n; i++){
        if(s < 0){s = dp2[i];continue;}
        s += dp2[i];
        delta1 = max(delta1,s);
    }
    s = 0;
    ll delta2 = 0;
    for(int i = 0; i < n; i++){
        if(s < 0){s = dp1[i];continue;}
        s += dp1[i];
        delta2 = max(delta2,s);
    }
    cout<<sum + max(delta1,delta2)<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)solved();
    return 0;
}