Codeforces Round #699 (Div. 2)

比赛链接

这次div2前三题其实都不难,全是暴力模拟,但是C有个点没考虑 一直wa2 浪费很多时间,D也没时间看,队友48min解决的C也没搞出来D,估计有点难度,有时间补一下。

A Space Navigation

题意

初始位置在(0,0),有一串操作序列LRUD(代表上下左右移动),问你是否可以删去部分操作后使得移动到(x,y)

分析

用一个桶存 L R U D 分别有几个,然后看数量是否分别大等于 x, y 即可,注意判断负数坐标。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int tong[200];
int main(int argc, char const *argv[]) {
    string s;
    int t;
    cin >>t;
    while(t--) {
        int x, y;
        cin >> x >> y;
        cin >> s;
        memset(tong, 0, sizeof tong);
        for(int i = 0; i < s.size(); i++) tong[s[i]]++;
        int flag = -1;
        if(x < 0) {
            if(tong['L'] >= -x) flag ++;
        }
        else {
            if(tong['R'] >= x) flag ++;
        }
        if(y < 0) {
            if(tong['D'] >= -y) flag ++;
        }
        else {
            if(tong['U'] >= y) flag ++;
        }
        if(flag == 1) puts("YES");
        else puts("NO");
    }
    return 0;
}

B. New Colony

题意

有 $k$ 个石头,从第一座山滚下去,遇到第 $i$ 座山满足高度 $h_i<h_{i+1}$,则让 $h_i+1$,表示石头停留在第 $i$ 座山上。问你第 $k$ 个石头最后停在哪座山上,如果滑出所有的山则输出-1。

分析

虽然石头数量一个有 1e9,但是每座山最高100,最多100座山,那么其实最多使用的石头数量也就1e4级别(极限情况每座山高度最多都到达了100,则直接输出-1即可),所以直接暴力模拟一遍就可以了。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int h[110];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        for(int i = 0; i < n; i++) scanf("%d",&h[i]);

        int ans;
        while(k--) {
            int flag = 0;
            for(int i = 0; i < n - 1; i++) {
                if(h[i] < h[i+1]) {
                    h[i] ++;
                    flag = 1;
                    ans = i+1;
                    break;
                }
            }
            if(flag == 0) {
                ans = -1;
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

C. Fence Painting

题意

有n个篱笆,给你a数组表示每个篱笆初始的颜色,b数组表示最终每个篱笆染成什么颜色,有m个粉刷匠,c数组表示每个粉刷匠有那种颜料,每个粉刷匠必须染一次篱笆且只能染一次,且要按照1-m的顺序去染。

分析

用一个vector数组 cha[ ] 记录每个需要染的颜色对应的位置,ans数组存每个粉刷匠刷的篱笆,遍历一遍c数组,如果cha中对应的颜色还有需要染的位置,则将粉刷匠分配过去。有些粉刷匠的颜料是多余的,那么我们可以让他刷在下一次即将要被刷的篱笆上,这样就能将其覆盖掉了。首先看最后一个粉刷匠,由于他最后粉刷,所以他不会被覆盖掉,那么他只能刷在已经存在的颜色上,如果存在则将其分配过去,否则输出NO。接着倒着遍历一遍ans,将所有ans为0的赋值为当前粉刷匠后面即将粉刷的位置即可(具体看代码,不好表述)

比赛的时候一直wa2因为没判断一种情况:所有粉刷匠都分配了篱笆,但是有些篱笆并未符合b的颜色,应该输出NO,但是我的代码实现过程让他输出了YES,然后由于调试改数据大小,最后慌忙又RE了一发,思路和实现一开始就是对的,很可惜!

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn], b[maxn], c[maxn], ans[maxn];
vector<int> cha[maxn];
int main(int argc, char const *argv[]) {
    int t;
    cin >> t;
    while(t--) {
        int ed = 0, ne = 0;//ed表示已经修改的篱笆数,ne表示需要修改的篱笆数
        memset(ans, 0, sizeof ans);
        unordered_map<int,int> id;
        int n, m;
        cin >> n >> m;
        for(int i = 0; i <= n; i++) cha[i].clear();
        for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
        for(int i = 1; i <= n; i++) {
            scanf("%d",&b[i]);
            id[b[i]] = i;
            if(a[i] != b[i]) {cha[b[i]].push_back(i);ne++;}// 存入需要修改的颜色对应的下标
        }
        for(int i = 1; i <= m; i++) scanf("%d",&c[i]);

        for(int i = 1; i <= m; i++) {
            if(cha[c[i]].size()!=0) {
            //如果当前粉刷匠的颜色属于需要修改的颜色则直接分配他去修改
                ans[i] = cha[c[i]].back();
                cha[c[i]].pop_back();
                ed++;
            }
        }
        //最后一个粉刷匠刷完篱笆后不能被覆盖,所以只能修改现有的篱笆
        if(ans[m] == 0 && id.find(c[m]) != id.end()) {
            ans[m] = id[c[m]];
        }
        int now = -1;
        for(int i = m; i >= 1; i--) {
            if(ans[i] != 0) {now = ans[i];continue;}
            if(now != -1 && ans[i] == 0) {
                //如果当前未被修改,则改成他后面的离他最近的那个已经被修改的篱笆,这样到时候就可以被覆盖掉了
                ans[i] = now;
            } 
        }
        //如果最后一个被分配了并且全部需要修改的都修改了则输出yes,当时就是没加第二个条件wa2
        if(ans[m] != 0 && ne == ed) {
            puts("YES");
            for (int i = 1; i <= m; i++) {
                printf("%d%c",ans[i], i == m ? '\n' : ' ');
            }
        }
        else puts("NO");
    }
    return 0;
}
暂无评论

发送评论 编辑评论


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