Codeforces Round #700 (Div. 2) 题解(A-D)

一场比一场der了。

A. Yet Another String Game

题意

两个人轮流操作一个字符串,操作后的字母不能和之前相同,一个人想让字典序尽可能大,另一个想让字典序尽可能小,求操作后的字符串

题解

签到题,每次选择最优解。

#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(_--){
      string s;
      cin>>s;
      for(int i=0;i<s.size();i++){
        if(i%2==0){
            if(s[i]=='a') s[i]='b';
            else s[i]='a';
        }
        else{
            if(s[i]=='z') s[i]='y';
            else s[i]='z';
        }
      }
      cout<<s<<endl;
    }

    return 0;

}

B. The Great Hero

题意

一个英雄要打n个怪物,英雄和每个怪物有攻击力和生命值。可以任意选择一个怪物打一回合,之后二者生命值分别扣减对方攻击力,问能否打完全部怪物(打完所有怪物英雄牺牲也算yes)。

题解

主要在于“打完所有怪物英雄牺牲也算yes”,所以我们必须把攻击力最高的放在最后一个打。

#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 A,B,n;
        cin>>A>>B>>n;
        pair<ll,ll> a[n];
        int f=0;
        for(int i=0;i<n;i++) cin>>a[i].first;
        for(int i=0;i<n;i++) cin>>a[i].second;
        for(int i=0;i<n;i++){
            if(a[i].second%A){
                B-=a[i].first*((a[i].second/A)+1);
            }
            else{
                B-=a[i].first*((a[i].second/A));
            }
            if(B<=0&&i==n-1&&B+a[i].first>0) break;
            else if(B<=0)f=1;
        }
        if(f==1) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;

    }

    return 0;

}

C. Searching Local Minimum

题意

一道交互题,给一个1-n的数组变换后的数组,在100次查询内确定区域最小值的位置。

题解

结合数据范围,很容易想到二分查找。因为a[i-1]>a[i]&&a[i+1]>a[i],那么,如果a[mid+1]>a[mid],就在左区间,反则在右区间。

#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>>_;
    int a[_+2];
    memset(a,0,sizeof(a));
    a[0]=imax;
    a[_+1]=imax;
    int l=1;
    int r=_;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid]==0) cout << "? " << mid << endl, cin >> a[mid];
        if (a[mid + 1]==0) cout << "? " << mid + 1 << endl, cin >> a[mid + 1];
        if (a[mid] < a[mid + 1]) r = mid;
        else l = mid + 1;
    }
    cout << "! " << l;
    return 0;
}

D1. Painting the Array I

题意

找一个数组的两个子序列,子序列中不能出现相邻的数,使得两个子序列长度和最大。

题解

施工中。

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

知识共享许可协议
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
小恐龙
花!
上一篇
下一篇