Codeforces Round #647 (Div. 1) – Thanks, Algo Muse! 题解

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse!

Johnny and Contribution

傻逼模拟题，用 stable_sort 排序一下，然后判一下无解。

const int N = 5e5 + 7;
int n, m, a[N], p[N], q[N];
vi e[N];

int main() {
	rd(n, m);
	for (int i = 1, x, y; i <= m; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	rda(a, n);
	for (int i = 1; i <= n; i++) p[i] = i;
	stable_sort(p + 1, p + n + 1, [&](int i, int j) {
		return a[i] < a[j];
	});
	for (int i = 1; i <= n; i++) q[p[i]] = i;
	for (int x = 1; x <= n; x++) {
		map<int, bool> v;
		for (int y : e[p[x]])
			if (q[y] < x) v[a[y]] = 1;
		int t = 1;
		while (v[t]) ++t;
		if (t != a[p[x]]) return print(-1), 0;
	}
	printa(p, n);
	return 0;
}

Johnny and Grandmaster

从大到小贪心，每次往少的里面放。

其实是好题，只不过细节很多。

const int N = 1e6 + 7;
int n, p, a[N];

inline void solve() {
	rd(n, p), rda(a, n);
	if (p == 1) return print(n & 1);
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	modint ans = (modint)p ^ a[1];
	ll c = 1;
	int k = a[1], w = log(n) / log(p) + 1;
	for (int i = 2; i <= n; i++) {
		if (k - a[i] > w) {
			if (c > 0) c = n;
			else if (c < 0) c = -n;
			k = a[i];
		} else while (k > a[i]) {
			--k;
			c *= p;
			if (c > n) {
				c = n;
				break;
			}
			if (c < -n) {
				c = -n;
				break;
			}
		}
		if (c <= 0) {
			ans += (modint)p ^ a[i];
			++c;
		} else {
			ans -= (modint)p ^ a[i];
			--c;
		}
	}
	print(ans);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Johnny and Megan's Necklace

枚举所有答案，找到答案之后跑个欧拉回路即可。

注意：欧拉回路的路径方案必须在 dfs 之后放入答案，否则是错的！！！！！！

const int N = 2e6 + 7;
int n, a[N], b[N];

int d[N];
vi e[N];
bool v[N];

void dfs(int x) {
	v[x] = 1;
	for (int y : e[x])
		if (!v[y]) dfs(y);
}

inline bool pd(int t) {
	t = (1 << t) - 1;
	for (int i = 0; i <= t; i++)
		d[i] = 0, e[i].clear(), v[i] = 0;
	for (int i = 1; i <= n; i++)
		e[a[i]&t].pb(b[i] & t), e[b[i]&t].pb(a[i] & t),
		++d[a[i]&t], ++d[b[i]&t];
	for (int i = 0; i <= t; i++)
		if (d[i] & 1) return 0;
	dfs(a[1] & t);
	for (int i = 0; i <= t; i++)
		if (d[i] && !v[i]) return 0;
	return 1;
}

namespace Euler {
	int h[N], e[N], t[N], tot = 1;
	bool v[N];
	vi ans;
	
	inline void add(int x, int y, int o = 1) {
		e[++tot] = y, t[tot] = h[x], h[x] = tot;
		if (o) add(y, x, 0);
	}
	
	void dfs(int x) {
		for (int &i = h[x]; i; i = t[i]) {
			if (v[i]) continue;
			v[i] = v[i^1] = 1;
			int y = e[i], j = i ^ 1;
			dfs(y);
			ans.pb(j);
		}
	}
	
	inline void main(int t) {
		t = (1 << t) - 1;
		for (int i = 1; i <= n; i++)
			add(a[i] & t, b[i] & t);
		dfs(a[1] & t);
		for (int x : ans) print(x - 1, ' '), print((x ^ 1) - 1, ' ');
	}
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i], b[i]);
	int t = 0;
	while (t < 20)
		if (pd(t + 1)) ++t;
		else break;
	print(t);
	Euler::main(t);
	return 0;
}

Johnny and James

咕

James and the Chase

咕

Johnny and New Toy

咕