2021牛客暑期多校训练营10
2021/8/19 23:06:54
本文主要是介绍2021牛客暑期多校训练营10,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021牛客暑期多校训练营10_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
F-Train Wreck
本题题意有些复杂,转换下题意就是给你一棵树,以及不同的颜色数,现在让你对这棵树进行染色,要求每个节点的儿子节点颜色互不相同。
很容易看出来,我们可以贪心地达到目的,每次先使用最多的颜色去染色即可,那么本题的重点就是如何建出这棵树,具体如下:
依次遍历给定的括号序列并维护一个栈,保证下一个遍历到的左括号的父亲是栈顶:
\(\bullet\) 如果是左括号\((\),我们按顺序给他们编号,并让它入栈。
\(\bullet\) 如果是右括号\()\),我们弹出栈顶。
这样做之后会发现有一个问题,如果是\(()()()\)这样的序列那么我们接下来的程序会认为\(1~1~1\)也是合法的,所以我们可以在最开始先在栈中添加一个虚拟节点\(0\)。
那么样例二根据括号序列建出来的树就是这样的 \(\downarrow \downarrow \downarrow\)
接下来只要贪心地染色就行了,具体地,我们可以用一个优先队列存储每个颜色的个数和编号并且让个数多的优先出队,然后依次枚举每个节点即\(0 \cdots n\),再枚举它的所有儿子节点,并且依次让队列元素出队并记录颜色,那么不能染色的条件就是当前队列颜色个数\(<\)当前节点儿子个数。
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e6 + 5; struct Color { int col, cnt; bool operator <(const Color &oth) const { return cnt < oth.cnt; } }; char s[MAXN]; int n, M[MAXN]; vector<int> e[MAXN]; void build() { stack<int> S; S.push(0); // 虚拟节点, 永远在栈中 int idx = 0; // 每个左括号(的编号 for (int i = 1; i <= 2 * n; ++i) { if (s[i] == '(') { e[S.top()].push_back(++idx); S.push(idx); } else { S.pop(); } } } int ans[MAXN]; void solve() { priority_queue<Color> Q; for (int i = 1; i <= n; ++i) { if (M[i]) { Q.push({i, M[i]}); } } for (int u = 0; u <= n; ++u) { // 如果 队列里的颜色 < 儿子个数 if (Q.size() < e[u].size()) { cout << "NO" << '\n'; return ; } // 因为要保证儿子节点颜色各不相同 // 所以我们在出队后先保存下来 // 等全部染色后再入队 // 这样就保证了颜色不同 vector<Color> V; for (int v: e[u]) { auto [col, cnt] = Q.top(); Q.pop(); ans[v] = col; // 如果当前颜色-1之后为0就不用再次入队了 if (cnt > 1) { V.push_back({col, cnt - 1}); } } // 用过的颜色重新入队 for (auto [x, y]: V) { Q.push({x, y}); } } cout << "YES" << '\n'; for (int i = 1; i <= n; ++i) { cout << ans[i] << " \n"[i == n]; } } int main(int argc, char *argv[]) { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> s + 1; for (int i = 1; i <= n; ++i) { int x; cin >> x; ++M[x]; // 记录这个颜色个数 } build(); // 根据括号序列建树 solve(); // 贪心 system("pause"); return 0; }
这篇关于2021牛客暑期多校训练营10的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南