Codeforces Round #554 (Div. 2)

官方题解

Neko Finds Grapes

#include <bits/stdc++.h>
using namespace std;
int n, m, a[2], b[2];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, t; i < n; ++i)
		scanf("%d", &t), ++a[t & 1];
	for (int i = 0, t; i < m; ++i)
		scanf("%d", &t), ++b[t & 1];
	printf("%d", min(a[0], b[1]) + min(a[1], b[0]));
}

Neko Performs Cat Furrier Transform

每次把最高位异或掉即可。

#include <bits/stdc++.h>
using namespace std;
int x, c, b[30], ans[40], *p;
int main()
{
	for (int i = 0; i < 30; ++i)
		b[i] = (1 << i) - 1;
	for (scanf("%d", &x); p = lower_bound(b, b + 30, x), *p != x; ++c)
	{
		if (c & 1)
			++x;
		else
			x ^= *p, ans[c] = p - b;
	}
	printf("%d\n", c);
	for (int i = 0; i < c; i += 2)
		printf("%d ", ans[i]);
}

Neko does Maths

题意:找到最小的非负整数$k$,使得$(k+a)/\gcd(k+a,k+b)\times(k+b)$最小。

解:不妨$a\ge b$,考虑$\gcd(a,b)=\gcd(a,a-b)$,用$c=a-b$代入原式,即要最小化$(k+a)/\gcd(k+a,k+a-c)\times(k+a-c)=(k+a)/\gcd(k+a,c)\times(k+a-c)$。由于$\gcd(k+a,c)$一定是$c$的因子,枚举$c$的所有因子$j$,要求$j$也是$k+a$的因子,满足的$k$在$[0,j)$内存在且唯一,此时回代判断即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b;
int main()
{
	scanf("%lld%lld", &a, &b);
	if (a < b)
		swap(a, b);
	pair<ll, ll> ans(a / __gcd(a, b) * b, 0);
	for (ll i = 1, c = a - b; i * i <= c; ++i)
		if (c % i == 0)
			for (auto j : {i, c / i})
			{
				ll k = ((-a) % j + j) % j;
				ans = min(ans, {(k + a) / j * (k + a - c), k});
			}
	printf("%lld", ans.second);
}

Neko and Aki’s Prank

题意:有一个 trie 是从一个括号序列建立的,求这个 trie 的最大匹配是多少。

解:现场已经看出这个题是树的 DP,我还是太菜了啊。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll a, ll b) const { return a += b, a < M ? a : a - M; }			//假如a和b都已经在同余系内,就不必取模了,取模运算耗时很高
	ll add(ll a, ll b) const { return a = (a + b) % M, a < 0 ? a + M : a; } //考虑a和b不在同余系内甚至为负数的情况
	ll mul(ll a, ll b) const { return add(a * b, 0); }
	/*
	ll mul(ll x, ll y) const //无循环快速计算同余乘法,根据a*b是否爆ll替换a*b%m
	{
		ll a = x / SM, b = x % SM,
		   c = y / SM, d = y % SM,
		   e = SM * SM - M, //可能为负
			f = ((a * d + b * c) % M + a * c / SM * e) % M;
		return add(((a * c % SM + f / SM) * e % M + f % SM * SM) % M, b * d);
	}
	*/
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		for (a = add(a, 0LL); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	ll inv(ll a) const { return pow(a, M - 2); } //return pow(a, phi(M) - 1);
	/*
	ll inv(ll a) const //模m下a的乘法逆元,不存在返回-1(m为素数时a不为0必有逆元)
	{
		ll x, y, d = gcd(a, m, x, y);
		return d == 1 ? (x + m) % m : -1;
	}
	*/
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
	/*
	vector<ll> sol(ll a, ll b) const //解同余方程,返回ax=b(mod M)循环节内所有解
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back((b / d) % (M / d) * (x = (x % M + M) % M));
		for (ll i = 1; i < d; ++i)
			ans.push_back((ans.back() + M / d) % M);
		return ans;
	}
	*/
} M(1e9 + 7);
const ll N = 2047;
ll n, f[N][N][2];
int main()
{
	memset(f, -0x3f, sizeof(f));
	f[0][0][0] = 0;
	for (int i = 1; i + 1 < N; ++i)
	{
		f[i][0][0] = max(f[i - 1][1][0], f[i - 1][1][1]);
		f[i][0][1] = M.qadd(f[i - 1][1][0], 1);
		for (int j = 1; j <= i; ++j)
		{
			f[i][j][0] = M.qadd(
				max(0LL, max(f[i - 1][j - 1][0], f[i - 1][j - 1][1])),
				max(0LL, max(f[i - 1][j + 1][0], f[i - 1][j + 1][1])));
			f[i][j][1] = max(
							 f[i - 1][j - 1][0] + 1 + max(0LL, max(f[i - 1][j + 1][1], f[i - 1][j + 1][0])),
							 f[i - 1][j + 1][0] + 1 + max(0LL, max(f[i - 1][j - 1][0], f[i - 1][j - 1][1]))) %
						 M.M;
		}
	}
	scanf("%lld", &n);
	printf("%lld", max(f[2 * n][0][0], f[2 * n][0][1]));
}

Neko and Flashback

欧拉路。详见官方题解。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, b[N], c[N];
struct Ranker : vector<int>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(int x) { return lower_bound(begin(), end(), x) - begin(); }
} rk;
struct Graph
{
	struct Vertex
	{
		vector<int> i;
	};
	typedef pair<int, int> Edge;
	vector<Vertex> v;
	vector<Edge> e;
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
};
struct Fleury : Graph
{
	vector<int> vis, cur, p;
	Fleury(int n) : Graph(n) {}
	void dfs(int u)
	{
		for (int &i = cur[u], k; i < v[u].i.size(); ++i)
			if (k = v[u].i[i], !vis[k] && !vis[k ^ 1])
				vis[k] = 1, dfs(e[k].first), p.push_back(k);
	}
	void ask()
	{
		int cnt = 0;
		for (int i = 0; i < v.size(); ++i)
			if (v[i].i.size() % 2)
				++cnt;
		if (cnt > 2)
			return;
		vis.assign(e.size(), 0), cur.assign(v.size(), 0), p.clear();
		for (int i = 0; i < v.size(); ++i)
			if (v[i].i.size() % 2)
				return dfs(i);
		dfs(0);
	}
};
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i)
		scanf("%d", &b[i]), rk.push_back(b[i]);
	for (int i = 0; i < n - 1; ++i)
		scanf("%d", &c[i]), rk.push_back(c[i]);
	rk.init();
	Fleury g(rk.size());
	for (int i = 0; i < n - 1; ++i)
	{
		if (b[i] > c[i])
			return printf("-1"), 0;
		g.add({b[i] = rk.ask(b[i]), c[i] = rk.ask(c[i])}), g.add({c[i], b[i]});
	}
	g.ask();
	if (g.p.size() < n - 1)
		return printf("-1"), 0;
	for (int i = 0; i < n - 1; ++i)
		printf("%d ", rk[g.e[g.p[i]].first]);
	printf("%d ", rk[g.e[g.p[n - 2]].second]);
}

Neko Rules the Catniverse (Small Version)

状压 DP,用$f[i][j][mask]$来表示正在考虑第 i 个,已经考虑了第$j$个,后$m$个的选择状态是二进制位集$mask$。

这里可以滚动数组。

#include <bits/stdc++.h>
using namespace std;
void add(int &a, long long b, int M = 1e9 + 7) { a = (a + b) % M; }
int n, k, m;
int main()
{
	scanf("%d%d%d", &n, &k, &m);
	vector<vector<int>> f(k + 1, vector<int>(1 << m, 0));
	f[0][0] = 1;
	for (int i = 0; i < n; ++i)
	{
		vector<vector<int>> g(k + 1, vector<int>(1 << m, 0));
		for (int j = 0; j < f.size(); ++j)
			for (int mask = 0; mask < f[j].size(); ++mask)
			{
				int newMask = (mask << 1) % f[j].size();
				add(g[j][newMask], f[j][mask]);
				if (j < k)
					add(g[j + 1][newMask | 1], (1LL + __builtin_popcount(mask)) * f[j][mask]);
			}
		f.swap(g);
	}
	for (int mask = m = 0; mask < f[k].size(); ++mask)
		add(m, f[k][mask]);
	printf("%d", m);
}

Neko Rules the Catniverse (Large Version)

注意到状态只在相邻的两位转移,这里可以用矩阵加速 DP。

下面这段代码跑了 5070ms,官方还有一个跑了 156ms 的解法,暂时没看懂…也太强了吧。

#include <bits/stdc++.h>
using namespace std;
int n, k, m;
void add(int &a, long long b, int M = 1e9 + 7) { a = (a + b) % M; }
int toId(int j, int mask) { return j << m | mask; }
struct Matrix
{
	vector<vector<int>> a;
	int n;
	Matrix(int n) : n(n), a(n, vector<int>(n)) {}
	friend Matrix operator*(const Matrix &a, const Matrix &b)
	{
		Matrix c(a.n);
		for (int i = 0; i < a.n; ++i)
			for (int j = 0; j < a.n; ++j)
				for (int k = 0; k < a.n; ++k)
					add(c.a[i][j], 1LL * a.a[i][k] * b.a[k][j]);
		return c;
	}
	friend Matrix pow(Matrix a, int b)
	{
		Matrix r(a.n);
		for (int i = 0; i < a.n; ++i)
			r.a[i][i] = 1;
		for (; b; b >>= 1, a = a * a)
			if (b & 1)
				r = a * r;
		return r;
	}
};
int main()
{
	scanf("%d%d%d", &n, &k, &m);
	Matrix dp(toId(k + 1, 0)), f(dp);
	for (int j = 0; j <= k; ++j)
		for (int mask = 0; mask < (1 << m); ++mask)
		{
			int newMask = (mask << 1) % (1 << m);
			f.a[toId(j, newMask)][toId(j, mask)] = 1;
			if (j < k)
				f.a[toId(j + 1, newMask | 1)][toId(j, mask)] = 1 + __builtin_popcount(mask);
		}
	dp.a[0][0] = 1, dp = pow(f, n) * dp;
	int ans = 0;
	for (int mask = 0; mask < (1 << m); ++mask)
		add(ans, dp.a[toId(k, mask)][0]);
	printf("%d", ans);
}