当前位置：网站首页>Codeforces Round ＃699 (Div. 2)

Codeforces Round ＃699 (Div. 2)

2022-08-08 17:40:00 【Here_SDUT】

比赛链接

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

题意

初始位置在（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;
}

原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068393