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

什么时候能不der?

A. Space Navigation

题意

在二维坐标里面,你要移动到指定的点处,UDLR分别表上向上、下、左、右,你可以去除任意字符,问能否到达这个点。

题解

签到题,分别统计各个字母的个数,因为可以去除任意字符,如果x>0,我们就只需要右移动,即当 x>R的个数 的时候,x轴方向可以到达,其他方向同理。

#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 x,y;
       cin>>x>>y;
       string s;
       cin>>s;
       ll a=0,b=0,c=0,d=0;
       for(ll i=0;i<s.size();i++){
        if(s[i]=='U')a++;
        if(s[i]=='D')b++;
        if(s[i]=='L')c++;
        if(s[i]=='R')d++;
       }
       //cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
       int f=0;
       if(x>0&&d<x)f=1;
       else if(x<0&&c<abs(x))f=1;
       if(y>0&&a<y) f=1;
       else if(y<0&&b<abs(y))f=1;
       if(f==1) cout<<"NO"<<endl;
       else cout<<"YES"<<endl;
    }

    return 0;

}

B. New Colony

题意

你有n座山和k个石头,如果 第i座山的高度>第i+1座山的高度 ,石头可以直接滚过去,否则第i座山的高度+1,问第k个石头留在哪座山上,如果滚出去了,输入-1。

题解

这题一开始想复杂了,就模拟就行,但是别太直接。

#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,k,mi=lmax,mi2=lmax;
       cin>>n>>k;
       ll moun[n];
       ll last=0,re=-1;
       for(int i=0;i<n;i++){
            cin>>moun[i];
            mi=min(mi,moun[i]);
            if(i!=0&&re==-1){
                while(moun[i]>moun[i-1]){
                    mi2=lmax;
                    for(int j=i-1;j>=0;j--){
                        if(moun[j]==mi) {
                            moun[j]++;
                            k--;
                            if(k==0) re=j+1;
                        }
                        mi2=min(mi2,moun[j]);
                    }
                    mi=mi2;
                }

            }
       }
       cout<<re<<endl;

    }

    return 0;

}

C. Fence Painting

题意

你要给栅栏涂色,每个画家按顺序到达,你可以指派他去涂哪个栅栏但是你不能不让他去涂,最终能否把栅栏涂成希望的颜色?

题解

这题一直在der,因为一个小错误WA了好几发。
首先统计出已经有的颜色和需要的颜色,然后倒序遍历画家,如果最后一个画家的颜色不是已经有的颜色或需要的颜色之一,直接no。如果其他的画家出现了没关系,因为会被最后一个画家覆盖掉。
之后就是涂需要的颜色了,到最后如果所有需要涂的颜色都涂了,就是yes,否则no。
坑点:统计需要的颜色的时候要把该颜色从已有颜色中删掉,如果不删掉,可能出现最后一个颜色覆盖已经被涂过的颜色上面。
例如:
3 2
1 2 3
1 2 4
4 3
这个明显no,因为第1个画家必须涂在3上,第二个无处可涂。

#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(_--){
       int n,m;
       cin>>n>>m;
       int num[n];
       int want[n];
       map<int,set<int> > needcolor;
       map<int,set<int> > color;
       for(int i=0;i<n;i++) {
            cin>>num[i];
            color[num[i]].insert(i);
       }
       for(int i=0;i<n;i++) {
            cin>>want[i];
            if(want[i]!=num[i]) {
                needcolor[want[i]].insert(i);
                color[num[i]].erase(i);
                if(color[num[i]].size()==0) color.erase(num[i]);
            }
       }
       int painter[m];
       int re[m];
       int bak,f=0;
       for(int i=0;i<m;i++) cin>>painter[i];
       if(needcolor.size()==0){
          if(color.count(painter[m-1])==0) f=1;
          else{
                for(int i=0;i<m;i++) re[i]=*color[painter[m-1]].begin() ;
          }
       }
       else{
           for(int i=m-1;i>=0;i--){
                //cout<<1<<endl;
               if(needcolor.count(painter[i])!=0){
                    re[i]=*needcolor[painter[i]].begin() ;
                    bak=re[i];
                    needcolor[painter[i]].erase(re[i]);
                    if(needcolor[painter[i]].size()==0) needcolor.erase(painter[i]);
               }
               else if(i==m-1&&color.count(painter[i])!=0){
                    re[i]=*color[painter[i]].begin();
                    bak=re[i];
               }
               else if(i!=m-1){
                    re[i]=bak;
               }
               else {
                    f=1;
                    break;
               }
           }
       }
        if(f==1||needcolor.size()!=0){
            cout<<"NO"<<endl;
        }
        else{
            cout<<"YES"<<endl;
            for(int i=0;i<m;i++) cout<<re[i]+1<<" ";
            cout<<endl;
        }
    }

    return 0;

}

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

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