Codeforces Round #695 (Div. 2) 题解(A-C)

此次一定给出A-C,视心情去做D题D题鸽了。

A Wizard of Orz

题意

给出n个模10计数器从左到右排列,都同时从0开始,我们可以选择在任意时间停止其中一个,与停止的计数器相邻的计时器会在下一秒停止。全部停止之后,将计数器上所有数字从左到右排列可以成为一个数,求这个数的最大值。

题解

当只有一个计时器时,这个数字是9.
两个的时候,就是98。
从第三个开始,就是989012345678901234567890……。
很明显可以推出规律。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f 
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        ll n,re=9;
        cin>>n;
        if(n==1) cout<<9;
        else if(n==2) cout<<98;
        else{
            cout<<98;
            for(int i=0;i<n-2;i++){
                cout<<re;
                re++;
                if(re==10) re=0;
            }
        }
        cout<<endl;
    }
}

B Hills And Valleys

题意

给出n个数的数组,如果a_i>a_{i+1}\&\&a_i>a_{i-1}是山,如果a_i<a_{i+1}\&\&a_i<a_{i-1}是谷。危险值为山和谷数量的和,你可以任意改变其中一个点,使得最终危险值最小。

题解

令a[i]=a[i-1]和a[i]=a[i+1],枚举最小情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
ll n[300010],t;
int hillorvalley(int i){
    if(i==0||i==t-1) return 0;
    else if((n[i]>n[i-1]&&n[i]>n[i+1])||(n[i]<n[i-1]&&n[i]<n[i+1])) return 1;
    return 0;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        cin>>t;
        for(ll i=0;i<t;i++){
            cin>>n[i];
        }
        if(t<3){
            cout<<0<<endl;
            continue;
        }

        int wei=0;
        for(int i=1;i<t-1;i++){
            if((n[i]>n[i-1]&&n[i]>n[i+1])||(n[i]<n[i-1]&&n[i]<n[i+1])) wei++;
        }
        int re=wei;
        for(int i=1;i<t-1;i++){
            ll test=wei-hillorvalley(i-1)-hillorvalley(i)-hillorvalley(i+1);
            ll swa=n[i];
            n[i]=n[i-1];
            int test1=hillorvalley(i-1)+hillorvalley(i)+hillorvalley(i+1);
            n[i]=n[i+1];
            int test2=hillorvalley(i-1)+hillorvalley(i)+hillorvalley(i+1);
            re=min(re,test+min(test1,test2));
            n[i]=swa;
        }
        cout<<re<<endl;
    }

}

C Three Bags

题意

有三个袋子,每次操作我们可以分别从两个非空袋子中各选择一个任意的元素a,b,然后删除b并将a替换为a-b。操作可以进行任意次,求最终得到的最大结果。

题解

一个贪心思维。我们保留三个袋子的三个最小值,然后把第二个和第三个袋子中其余的值都和第一个袋子中的最小值操作。这时候,我们把第一个袋子中其他值和第二个袋子中的最小值操作,这时候有两种情况:
1.第二个和第一个进行操作(这时候第三个最小值没有变化过,其他都是负数),然后和第三个进行操作。
2.第三个和其他两个进行操作。
依题意,取二者最大值即可。其中,三个袋子可能是任意排列组合,同样求出最优解即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll a,b,c,s;
    cin>>a>>b>>c;
    ll b1=0,b2=0,b3=0;
    vector<ll> bag1;
    vector<ll> bag2;
    vector<ll> bag3;
    for(int i=0;i<a;i++){
        cin>>s;
        bag1.push_back(s);
        b1+=s;
    }
    for(int i=0;i<b;i++){
        cin>>s;
        bag2.push_back(s);
        b2+=s;
    }
    for(int i=0;i<c;i++){
        cin>>s;
        bag3.push_back(s);
        b3+=s;
    }
    sort(bag1.begin(),bag1.end());
    sort(bag2.begin(),bag2.end());
    sort(bag3.begin(),bag3.end());
    cout<<max(b1+b2+b3-min(2*b1,min(2*b2,2*b3)),b1+b2+b3-2*min(bag1.front()+bag2.front(),min(bag3.front()+bag2.front(),bag1.front()+bag3.front())))<<endl;

}

题目来源于https://codeforces.com/contest/1467

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇