codeforces1484C
2021/10/14 23:14:46
本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享