首页 > 其他分享 >AtCoder Regular Contest 143 E Reversi

AtCoder Regular Contest 143 E Reversi

时间:2022-12-14 18:56:27浏览次数:64  
标签:AtCoder typedef int Reversi long pb Regular maxn define

AtCoder 传送门

洛谷传送门

翻转一个点会把它相邻的点全部翻转,因此先从叶子开始自下而上考虑。不难发现,如果这个叶子是白色,那么它一定比它的父亲先翻转(否则它就翻不了了);而对于黑色的叶子,它一定比它的父亲后翻转。经过一波操作,我们得到了所有叶子的父亲的颜色。此时就可以把它们当作叶子处理,因为那些还没被删的叶子暂时影响不了它们。

经过模拟我们得到了树根的颜色。显然如果此时树根是黑点就无解,否则就自上而下操作。

这样我们发现父子之间的操作顺序可以确定,并且它们是充要的。建出 DAG 后跑拓扑排序即可求出字典序最小的解。

code
/*

p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy

*/

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, a[maxn], ind[maxn];
char s[maxn];
vector<int> G[maxn], T[maxn];

void dfs(int u, int fa) {
	a[u] = (s[u] == 'W');
	for (int v : G[u]) {
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		a[u] ^= a[v];
		if (a[v]) {
			T[v].pb(u);
			++ind[u];
		} else {
			T[u].pb(v);
			++ind[v];
		}
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		G[u].pb(v);
		G[v].pb(u);
	}
	scanf("%s", s + 1);
	dfs(1, -1);
	if (!a[1]) {
		puts("-1");
		return;
	}
	priority_queue< int, vector<int>, greater<int> > pq;
	for (int i = 1; i <= n; ++i) {
		if (!ind[i]) {
			pq.push(i);
		}
	}
	while (pq.size()) {
		int u = pq.top();
		pq.pop();
		printf("%d ", u);
		for (int v : T[u]) {
			if (!(--ind[v])) {
				pq.push(v);
			}
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:AtCoder,typedef,int,Reversi,long,pb,Regular,maxn,define
From: https://www.cnblogs.com/zltzlt-blog/p/16982953.html

相关文章

  • AtCoder Regular Contest 150 F Constant Sum Subsequence
    AtCoder传送门洛谷传送门定义\(\mathrm{nxt}(i,x)\)为最小的\(j\)满足\(a_j=x\)且\(j>i\),\(\mathrm{pre}(i,x)\)为最大的\(j\)满足\(a_j=x\)且\(j<......
  • atcoder beginner 281 DEFG 题解
    比赛链接:https://atcoder.jp/contests/abc281题解:D\(dp[i][j][k]\)表示考虑到第i个数,集合加入了\(k\)个数,余数为\(j\)的答案转移即可//bySkyRainWind#inclu......
  • PCRE Perl Compatible Regular Expressions Learning
    PCREPerlCompatibleRegularExpressionsLearningcatalog1.PCREIntroduction2.pcre2api3.pcre2jit4.PCREPrograming 1.PCREIntroductio......
  • AtCoder Beginner Contest 281
    A-CountDown(abc281a)题目大意给定\(n\),输出\(n\)到\(1\)。解题思路直接输出即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=l......
  • atcoder beginner contest 144 Gluttony(二分答案)
    题目大意:有an,bn,我们找到an和bn每个元素的一种一一对应关系。使得min(max(ai*bi))。已知我们可以进行操作让an中的任一个元素减少1。操作数最大为k,问我们怎么操作,可以min(......
  • atcoder ABC 281(A-C)
    A要求你从N开始,一直打印到0。NN-1......3210简单#include<iostream>usingnamespacestd;intn;intmain(){ cin>>n; for(inti=n;i>=0;i--)cout<<i<<en......
  • AtCoder 问题乱做集1
    AGC014D BlackandWhiteTree*2266题目大意:两个人在$n$个节点的树上交替染色,先手染白色,后手染黑色。若染完之后有白点不与黑点相邻则先手胜,反之后手胜。求这棵树......
  • AtCoder Beginner Contest 242 F Black and White Rooks
    洛谷传送门AtCoder传送门不错的组合计数题。因为黑车和白车不能在同一行或者同一列,所以可以考虑枚举黑车有\(i\)行\(k\)列的位置放,白车有\(j\)行\(l\)列的位置......
  • AtCoder Beginner Contest 281
    \(\mathtt{rank:1119th}\)\(\mathtt{problem}\)\(\mathtt{A}\)\(\mathtt{B}\)\(\mathtt{C}\)\(\mathtt{D}\)\(\mathtt{E}\)\(\mathtt{F}\)\(\mathtt{G}\)\(\ma......
  • AtCoder Beginner Contest 281
    https://atcoder.jp/contests/abc281A-CountDown原题链接题意给出一个数\(n\),按降序输出所有小于或等于\(n\)的非负整数。分析签到题,循环并输出从\(n\)到\(......