2021牛客暑假训练营总结

第十场

H题

• 思路

相邻的全部涂成不同的就好了。

• 代码

奇数个1，涂0；偶数个1，涂1。

F题

• 思路
  出栈入栈可以搞成一棵树，只要树每层颜色不同就可以，所以贪心的放让每层的都不一样。
• 代码

/*
 * @Author: Kurisu
 */

#include<bits/stdc++.h>

const int N = 1e6 + 5;
const int mod = 998244353;

std::vector<int> G[N];
int vis[N], ans[N];

void solve() {
	int n; std::cin >> n;
	std::string s; std::cin >> s;
	int cnt = 0; // 初始深度为0
	std::vector<int> record;
	record.emplace_back(0);
	for (int i = 0; i < 2 * n; i++) {
		if (s[i] == '(') { 
            ++cnt;// 节点编号加1
			G[record.back()].emplace_back(cnt);
			record.emplace_back(cnt);
		} else {
			record.pop_back(); // 回到上一个节点
		}
	}
	for (int i = 1; i <= n; i++) {
		int x; std::cin >> x;
		++vis[x];
	}
	std::priority_queue<std::pair<int, int> > que;
	for (int i = 1; i <= n; i++) {
		if (vis[i]) {
			que.push({vis[i], i});
		}
	}
	for (int i = 0; i <= n; i++) {
		if (G[i].size() > que.size()) {
			std::cout << "NO\n"; return ;
		}
		std::vector<std::pair<int, int> > buffer; // 暂时缓存
		for (auto v : G[i]) { // 这一层放不同的数字
			ans[v] = que.top().second;
			buffer.emplace_back(que.top());
			que.pop();
		}
		for (auto v : buffer) {
			if (v.first - 1 > 0) {
				que.push({v.first - 1, v.second});
			}
		}
	}
	std::cout << "YES\n";
	for (int i = 1; i <= n; i++) {
		std::cout << ans[i] << " \n"[i == n];
	}
}


int main() {
	std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
	int T = 1; //std::cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}