C/C++教程

codeforces1484C

本文主要是介绍codeforces1484C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://codeforces.com/contest/1481/problem/C

题意:

有n个物品,分别有各自的颜色a,还有预期颜色b,有m个人来涂色,每个人可以涂一个物品,问最后能不能全部变成预期颜色

思路:

因为颜色都是由最后一次涂改决定,可以选择倒着跑,遇到需要改变的就存下索引,如果有多余的放在上一次涂改的索引下面即可,最后肯定会被覆盖

题解:

#include <bits/stdc++.h>
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define all(v) begin(v),end(v)
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
const int N = 100010;
vector<int> g[N], h[N];
int a[N], b[N], c[N], d[N];
void solve() {
    int n, m;
    cin >> n >> m;
    memset(d, 0, sizeof d);
    for (int i = 1; i <= n; i++) cin >> a[i], g[i].clear(), h[i].clear();
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= m; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) {
            h[b[i]].eb(i);
        } else g[b[i]].eb(i);
    }
    int lst = 0;
    for (int i = m; i >= 1; i--) {
        int x = c[i];
        if (h[x].size()) {
            d[i] = h[x].back();
            h[x].pop_back();
            lst = d[i];
        } else if (g[x].size()) {
            d[i] = g[x].back();
            g[x].pop_back();
            lst = d[i];
        } else {
            d[i] = lst;
        }
    }
    for (int i = 1; i <= m; i++) {
        a[d[i]] = c[i];
    }
    for (int i = 1; i <= m; i++) {
        if (!d[i]) {
            cout << "No" << endl;
            return;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] != b[i]) {
            cout << "No" << endl;
            return ;
        }
    }
    cout << "Yes" << endl;
    for (int i = 1; i <= m; i++) cout << d[i] << ' ';
    cout << endl;
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int _; cin >> _; while (_--)
        solve();
    return 0;
}
这篇关于codeforces1484C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!