AtCoder Grand Contest 035 简要题解

从这里开始

Problem A XOR Circle

　　你发现，权值的循环节为 $a_0, a_1, a_0\oplus a_1$，然后暴力即可。

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 1e5 + 5;

int n;

int a[N], b[N];

void quitif(boolean condition, const char* vert = "No") {

	if (condition) {

		puts(vert);

		exit(0);

	}

}

boolean check(int x, int y) {

	b[0] = x, b[1] = y;

	for (int i = 2; i < n; i++)

		b[i] = b[i - 1] ^ b[i - 2];

	if (b[n - 2] ^ b[n - 1] ^ x)

		return false;

	if (b[n - 1] ^ b[0] ^ y)

		return false;

	sort(b, b + n);

	for (int i = 0; i < n; i++)

		if (b[i] ^ a[i])

			return false;

	return true;

}

int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {

		scanf("%d", a + i);

	}

	sort(a, a + n);

	int cnt = 1;

	for (int i = 1; i < n; i++) {

		cnt += (a[i] != a[i - 1]);

	}

	quitif(cnt > 3);

	if (cnt == 1) {

		if (check(0, 0)) {

			puts("Yes");

		} else {

			puts("No");

		}

	} else if (cnt == 2) {

		if (check(a[0], a[n - 1])) {

			puts("Yes");

		} else {

			puts("No");

		}

	} else {

		vector<int> qaq {a[0]};

		for (int i = 1; i < n; i++) {

			if (a[i] ^ a[i - 1]) {

				qaq.push_back(a[i]);

			}

		}

		if (check(qaq[0], qaq[1]) || check(qaq[0], qaq[2]) || check(qaq[1], qaq[2])) {

			puts("Yes");

		} else {

			puts("No");

		}

	}

	return 0;

}

Problem B Even Degrees

　　如果边数是奇数，显然无解。

　　如果是一棵树，那么从叶节点开始构造，每次选择当前点到父节点的那条边，使得子树内所有点的出度都是偶数。不是树的话，非树边随便选。

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 1e5 + 5;

int n, m;

int uf[N];

int d[N];

vector<int> G[N];

int find(int x) {

	return uf[x] == x ? x : (uf[x] = find(uf[x]));

}

void dfs(int p, int fa) {

	for (auto e : G[p]) {

		if (e ^ fa) {

			dfs(e, p);

		}

	}

	if (!fa)

		return;

	if (d[p]) {

		d[p] ^= 1;

		printf("%d %d\n", p, fa);

	} else {

		d[fa] ^= 1;

		printf("%d %d\n", fa, p);

	}

}

int main() {

	scanf("%d%d", &n, &m);

	if (m & 1) {

		puts("-1");

		return 0;

	}

	for (int i = 1; i <= n; i++)

		uf[i] = i;

	for (int i = 1, u, v; i <= m; i++) {

		scanf("%d%d", &u, &v);

		if (find(u) ^ find(v)) {

			uf[find(u)] = find(v);

			G[u].push_back(v);

			G[v].push_back(u);

		} else {

			printf("%d %d\n", u, v);

			d[u] ^= 1;

		}

	}

	dfs(1, 0);

	assert(!d[1]);

	return 0;

}

Problem C Skolem XOR Tree

　　讲一个垃圾做法。

　　如果 $n = 2^k\ (k\geqslant 0)$，显然无解。

　　如果 $n$ 为奇数，那么首先可以造出 $1 - 2 - 3 - 1' - 2' - 3'$。然后 $i - (i +1) - [i \oplus (i + 1)]- i' - (i + 1)' \ (2 | i)$。因为它们最高位相同，所以 $i \oplus (i + 1)$ 总是小于 $i$。

　　如果 $n$ 为偶数，设 $2^k < n < 2^{k + 1}$, 设 $n$ 的lowbit 为 $x$，考虑 $i \oplus (i - 1) < 2^k$，因为 $k > 1$，所以 $1 \oplus 2 \oplus \cdots \oplus (2^k - 1) = 0$，可以把它们按一定顺序排列来构造。把 $n, n - 1, x, x - 1$ 按某种顺序排列可以轻松构造出 $n - x$，这样大于等于 $2^k$ 的数还有偶数个没有加到树上，把它们两两配对，然后按奇数的后半部分构造就可以了。

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 1e5 + 5;

int n;

void O(int x, int y) {

	printf("%d %d\n", x, y);

}

int main() {

	scanf("%d", &n);

	if (!(n - (n & (-n)))) {

		puts("No");

		return 0;

	}

	puts("Yes");

	if (n & 1) {

		O(1, 2);

		O(2, 3);

		O(3, 1 + n);

		O(1 + n, 2 + n);

		O(2 + n, 3 + n);

		for (int i = 4; i < n; i += 2) {

			int v = i ^ (i + 1);

			O(i, i + 1);

			O(i + 1, v);

			O(v, i + n);

			O(i + n, i + n + 1);

		}

	} else {

		int x = (n & (-n)) - 1;

		int y = x + 1;

		assert(!(x ^ y ^ (n - 1) ^ n));

		O(y, x);

		O(x, n - 1);

		O(n - 1, n);

		O(n, y + n);

		O(y + n, x + n);

		O(x + n, n + n - 1);

		O(n + n - 1, n + n);

		int hig = 1;

		while ((hig << 1) < n)

			hig <<= 1;

		vector<int> a;

		for (int i = 1; i < hig; i++) {

			a.push_back(i);

		}

		a.erase(find(a.begin(), a.end(), x));

		a.erase(find(a.begin(), a.end(), y));

		for (int i = 1; i < (signed) a.size(); i++)

			O(a[i - 1], a[i]);

		O(a.back(), x);

		O(y, a[0] + n);

		for (int i = 1; i < (signed) a.size(); i++)

			O(a[i - 1] + n, a[i] + n);

		a.clear();

		int z = x ^ (n - 1);

		O(z, x);

		O(n - 1, z + n);

		for (int i = hig; i < n - 1; i++)

			a.push_back(i);

		a.erase(find(a.begin(), a.end(), z));

		assert(!(a.size() & 1));

		for (int i = 1; i < (signed) a.size(); i += 2) {

			int v = a[i - 1] ^ a[i];

			O(a[i - 1], a[i]);

			O(a[i], v);

			O(v, a[i - 1] + n);

			O(a[i - 1] + n, a[i] + n);

		}

	}

	return 0;

}

Problem D Add and Remove

　　不难发现，一个数的贡献系数并不多。

　　设 $f_{l, r, cl, cr}$ 表示，消除 $l, r$ 中的数，对左边的贡献为 $cl$ ，对右边的贡献为 $cr$。

　　转移考虑枚举最后删掉的数，那么它左侧的贡献系数变为 $(cl, cl + cr)$，右侧的贡献系数为 $cl + cr, cr)$。

　　粗略分析可得一个上界 $O(n^3 2^n)$。

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

typedef class Status {

	public:

		int l, r, cl, cr;

		Status() {	}

		Status(int l, int r, int cl, int cr) : l(l), r(r), cl(cl), cr(cr) {	}

		boolean operator < (Status b) const {

			if (l ^ b.l)

				return l < b.l;

			if (r ^ b.r)

				return r < b.r;

			if (cl ^ b.cl)

				return cl < b.cl;

			return cr < b.cr;

		}

} Status;

#define ll long long

int n;

int a[20];

map<Status, ll> F;

ll dp(int l, int r, int cl, int cr) {

	if (l > r)

		return 0;

	if (l == r)

		return 1ll * a[l] * (cl + cr);

	Status scur (l, r, cl, cr);

	if (F.count(scur))

		return F[scur];

	ll rt = 1e18;

	for (int k = l; k <= r; k++) {

		ll cost = a[k] * 1ll * (cl + cr);

		cost += dp(l, k - 1, cl, cl + cr);

		cost += dp(k + 1, r, cl + cr, cr);

		rt = min(rt, cost);

	}

	return F[scur] = rt;

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%d", a + i);

	}

	if (n == 2) {

		printf("%d", a[1] + a[2]);

		return 0;

	}

	ll ans = dp(2, n - 1, 1, 1) + a[1] + a[n];

	printf("%lld\n", ans);

	return 0;

}

Problem E Develop

　　考虑 $x$ 向 $x - 2$ 以及 $x + K$ 连一条有向边。存在方案当且仅当不存在环。充分性考虑不存在环意味着存在拓扑序，按拓扑序操作即可。必要性考虑如果存在环，并且能够操作，那么考虑在这个环上的最后一次操作会使得环上出现一个数，这会和最后一次操作矛盾。

　　如果 $K$ 是偶数，那么奇数位和偶数位是独立的，不存在环当且仅当在奇数位置或偶数位置中没有不选长度超过 $K / 2$ 的段。

　　如果 $K$ 是奇数，不难发现如果存在环，一定存在大小为 $K + 2$ 的环。考虑把所有数分成两列，第一列是所有奇数，第二列是所有偶数，如果存在从左边向下和向右的长度为 $K + 2$ 的路径，那么一定存在长度为 $K + 2$ 的环，考虑左边从 $x$ 走到了 $x - 2l$，然后走到了 $x - 2l + K$，然后走到 $x - 2l + K - 2(K - l) = x - K$ 此时它加上 $K$ 等于 $x$。

　　考虑让偶数 $x$ 和 $x - K$ 对齐，设 $f_{i, j, k}$ 表示考虑前 $i$ 行，右边连续不选了 $j$ 个数，从左侧最后一个点开始只能下或向右走的最长的长度为 $k$。转移讨论一下两边选不选。

　　时间复杂度 $O(n^3)$

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 155;

#define ll long long

int n, K, K2, Mod;

template <typename T>

void fix(T& x) {

	(x >= Mod) && (x -= Mod);

}

namespace subtask1 {

	int f[N][N];

	void solve() {

		int lim = (n + 1) >> 1;

		f[0][0] = 1;

		for (int i = 1; i <= lim; i++) {

			for (int j = 0; j < i && j <= K2; j++) {

				fix(f[i][j + 1] += f[i - 1][j]);

				fix(f[i][0] += f[i - 1][j]);

			}

		}

		int ans0 = 0, ans1 = 0;

		for (int i = 0; i <= K2; i++)

			fix(ans0 += f[n >> 1][i]);

		for (int i = 0; i <= K2; i++)

			fix(ans1 += f[lim][i]);

		ans0 = 1ll * ans0 * ans1 % Mod;

		printf("%d\n", ans0);

	}

}

namespace subtask2 {

	int f[N][N][N];

	void solve() {

		f[0][0][0] = 1;

		for (int i = 1; i <= n + 1; i++) {

			int r = i << 1, l = r - K;

			boolean have_r = (r >= 1 && r <= n), have_l = (l >= 1 && l <= n);

			for (int j = 0; j < i; j++) {

				for (int k = 0; k <= K + 1; k++) {

					int v = f[i - 1][j][k];

					if (!v)

						continue;

#define F(nj, nk) ((nk) <= K + 1) && (fix(f[i][nj][(nk)] += v), 0)

					fix(f[i][0][0] += v);

					if (have_r)

						fix(f[i][j + 1][0] += v);

					if (have_l)

						F(0, (k ? k + 1 : 0));

					if (have_l && have_r)

						F(j + 1, max(j + 2, k + 1));

				}

			}

		}

		printf("%d\n", f[n + 1][0][0]);

	}

}

int main() {

	scanf("%d%d%d", &n, &K, &Mod);

	K2 = K >> 1;

	if (K & 1) {

		subtask2::solve();

	} else {

		subtask1::solve();

	}

	return 0;

}

Problem F Two Histograms

　　定义一个局面是基本局面当且仅当不存在 $(i, j)$，使得 $k_i + 1 = j, l_j = i$，出现这样的情况可以变成 $k_i + 1, l_j - 1$。不难证明对于每种局面可以转化到至少一个基本局面。

　　可以发现，任意两个基本局面都是不同的。

　　假设存在连两个基本局面 $(k_1, k_2, \cdots, k_n, l_1, \cdots, l_m)$ 和 $(k'_1, \cdots, k'_2, l'_1, \cdots, l'_m)$ 相同。设 $j$ 是最小的使得 $l_j \neq l'_j$ 的整数，不妨设 $l_j < l'_j$。因为它们产生的网格相同，那么有：

如果 $j = 1$，那么有 $A_{l'_1, 1} = 1$，那么 $k'_{l'_1} + 1 = 1$，矛盾。
如果 $j > 1$，那么有 $A_{l'_j, j} = 1$，那么有 $k_{l'_j} < j, k_{l'_j} \geqslant j$，如果 $k_{l'_j} = j - 1$，那么矛盾，否则 $A_{l'_j, j - 1}$ 不可能相等，矛盾。

　　因此只用对基础局面进行计数，这个容斥即可。

Code

#include <bits/stdc++.h>

using namespace std;

typedef bool boolean;

const int N = 5e5 + 5;

#define ll long long

void exgcd(int a, int b, int& x, int& y) {

	if (!b) {

		x = 1, y = 0;

	} else {

		exgcd(b, a % b, y, x);

		y -= (a / b) * x;

	}

}

int inv(int a, int n) {

	int x, y;

	exgcd(a, n, x, y);

	return (x < 0) ? (x + n) : (x);

}

const int Mod = 998244353;

template <const int Mod = :: Mod>

class Z {

	public:

		int v;

		Z() : v(0) {	}

		Z(int x) : v(x){	}

		Z(ll x) : v(x % Mod) {	}

		friend Z operator + (const Z& a, const Z& b) {

			int x;

			return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));

		}

		friend Z operator - (const Z& a, const Z& b) {

			int x;

			return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));

		}

		friend Z operator * (const Z& a, const Z& b) {

			return Z(a.v * 1ll * b.v);

		}

		friend Z operator ~(const Z& a) {

			return inv(a.v, Mod);

		}

		friend Z operator - (const Z& a) {

			return Z(0) - a;

		}

		Z& operator += (Z b) {

			return *this = *this + b;

		}

		Z& operator -= (Z b) {

			return *this = *this - b;

		}

		Z& operator *= (Z b) {

			return *this = *this * b;

		}

		friend boolean operator == (const Z& a, const Z& b) {

			return a.v == b.v;

		}

};

Z<> qpow(Z<> a, int p) {

	Z<> rt = Z<>(1), pa = a;

	for ( ; p; p >>= 1, pa = pa * pa) {

		if (p & 1) {

			rt = rt * pa;

		}

	}

	return rt;

}

typedef Z<> Zi;

int n, m;

Zi fac[N], _fac[N];

void init_fac(int n) {

	fac[0] = 1;

	for (int i = 1; i <= n; i++) {

		fac[i] = fac[i - 1] * i;

	}

	_fac[n] = ~fac[n];

	for (int i = n; i; i--) {

		_fac[i - 1] = _fac[i] * i;

	}

}

Zi comb(int n, int m) {

	return fac[n] * _fac[m] * _fac[n - m];

}

Zi pwn[N], pwm[N];

int main() {

	scanf("%d%d", &n, &m);

	init_fac(max(n, m));

	pwn[0] = 1;

	for (int i = 1; i <= m; i++)

		pwn[i] = pwn[i - 1] * (n + 1);

	pwm[0] = 1;

	for (int i = 1; i <= n; i++)

		pwm[i] = pwm[i - 1] * (m + 1);

	Zi ans = 0;

	for (int i = 0; i <= n && i <= m; i++) {

		Zi tmp = comb(n, i) * comb(m, i) * fac[i] * pwn[m - i] * pwm[n - i];

		if (i & 1) {

			ans -= tmp;

		} else {

			ans += tmp;

		}

	}

	printf("%d\n", ans.v);

	return 0;

}

巴特西

AtCoder Grand Contest 035 简要题解

从这里开始

Problem A XOR Circle

Code

Problem B Even Degrees

Code

Problem C Skolem XOR Tree

Code

Problem D Add and Remove

Code

Problem E Develop

Code

Problem F Two Histograms

Code

最新文章

热门文章