Codeforces Round #738 (Div. 2)

A - Mocha and Math

签到。显然可以构造出来所有的与。

#include<bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

inline void work() {
	int n = rd(), ans = rd();
	for (int i = 2; i <= n; ++i) ans = (ans & rd());
	printf("%d\n", ans);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

B - Mocha and Red and Blue

两侧的问号显然可以处理成无相邻重复，中间的问号都依照左侧交替放就行。显然没有相邻重复更少的构造。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 1007

char s[N];

inline void work() {
	int n = rd();
	scanf("%s", s + 1); 
	int l = 1, r = n;
	while (s[l] == '?' && l <= n) ++l;
	if (l == n + 1) {
		for (int i = 1; i <= n; ++i) putchar((i & 1) ? 'B' : 'R');
		puts(""); return;
	}
	for (int i = l - 1; i; --i) s[i] = (s[i + 1] == 'R' ? 'B' : 'R');
	while (s[r] == '?' && r) --r;
	for (int i = r + 1; i <= n; ++i) s[i] = (s[i - 1] == 'R' ? 'B' : 'R');
	for (int i = l; i <= r; ++i) 
		if (s[i] == '?') s[i] = (s[i - 1] == 'R' ? 'B' : 'R');
	puts(s + 1);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

C - Mocha and Hiking

如果 \(a[1]=1\) 有 \(n+1\to 1\to 2\to \cdots\to n\) 。

如果 \(a[n]=0\) 有 \(1\to 2\to \cdots\to n\to n+1\) 。

否则 \(a[1] = 0,a[n] = 1\) ，一定有一个位置 \(a[i] = 0, a[i + 1] = 1\) ，有 \(1\to \cdots \to i\to n+1\to i+1\to \cdots\to n\) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 10007

int a[N];

inline void work() {
	int n = rd();
	for (int i = 1; i <= n; ++i) a[i] = rd();
	if (a[1] == 1) {
		printf("%d ", n + 1);
		for (int i = 1; i <= n; ++i) printf("%d ", i); 
		puts(""); return;
	}
	if (a[n] == 0) {
		for (int i = 1; i <= n; ++i) printf("%d ", i); 
		printf("%d\n", n + 1); return;
	}
	for (int i = 1; i <= n; ++i)
		if (a[i] == 0 && a[i + 1] == 1) {
			for (int j = 1; j <= i; ++j) printf("%d ", j);
			printf("%d ", n + 1);
			for (int j = i + 1; j <= n; ++j) printf("%d ", j);
			puts(""); return;
		}
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

D - Mocha and Diana

给定两个森林 \(A,B\) ，节点标号都是 \(1\sim n\) 。

一次操作选择一个 \((u,v)\) ，使得边 \((u,v)\) 加入两幅图后，两幅图依旧都是森林。

问最多能操作多少次，并输出方案。

容易发现每次成功的操作之后，\(A,B\) 的连通块数都 \(-1\) 。

如果不能操作了，且 \(A\)连通块数不唯一，那么考虑：

\(\forall 1\le i,j\le n\) ， \(i\) 和 \(j\) 在 \(A\) 中不连通，则 \(i\) 和 \(j\) 在 \(B\) 中连通。
\(\forall 1\le i,j\le n\) ， \(i\) 和 \(j\) 在 \(A\) 中连通，则 \(\exists 1\le k\le n\) ，\(k\) 在 \(A\) 中与 \(i\) 和 \(j\) 均不连通。

结合两条可以得到所有点在 \(B\)中均连通，即 \(B\) 是一棵树。

所以最多操作次数是 \(\min (n-1-|E_A|,n-1-|E_B|)\) ，且每次随便找一个可操作的操作都是对的。

那么现在问题是怎么快速找出可供选择的点对，方法很多，记录一个比较有意思的构造性方法：

先尝试操作 \(1\) 号点和所有点的组合（即能和 \(1\) 连通的都连通）。
令 \(A,B\) 中与 \(1\) 号点不连通的集合分别为 \(S_A,S_B\) ，由定义 \(S_A\cap S_B=\emptyset\) （否则一定可以操作 \(1\) 和交中的点）。
每次从 \(S_A,S_B\) 中各找出一个点，操作这两个点（由上结论两个图中两点一定不连通），按定义更新 \(S_A,S_B\) 。

首先 \(S_A, S_B\) 显然是可操作的最大范围了，所以正确性没问题。

考虑实现方法，其实懒惰删除法就好了，每次取点的时候判断下是否合法即可。并查集实现复杂度 \(O(n\alpha(n))\) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 100007

struct DSU {
	int f[N];
	inline void reset(int n) {for (int i = 1; i <= n; ++i) f[i] = i;}
	int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
	inline bool merge(int x, int y) {
		x = find(x); y = find(y);
		return x == y ? false : (f[x] = y, true);
	}
} A, B;

vector<int> sA, sB;

vector<pii> res;

int main() {
	int n = rd(), m1 = rd(), m2 = rd(); 
	A.reset(n); B.reset(n); 
	while (m1--) A.merge(rd(), rd());
	while (m2--) B.merge(rd(), rd());
	for (int j = 1; j <= n; ++j) 
		if (A.find(1) != A.find(j) && B.find(1) != B.find(j)) {
			res.push_back(make_pair(1, j)); A.merge(1, j); B.merge(1, j);
		} 
	for (int i = 1; i <= n; ++i) {
		if (A.find(1) != A.find(i)) sA.push_back(i);
		if (B.find(1) != B.find(i)) sB.push_back(i);
	}
	while (!sA.empty() && !sB.empty()) {
		int u = sA.back(), v = sB.back(); sA.pop_back(); sB.pop_back(); 
		res.push_back(make_pair(u, v)); A.merge(u, v); B.merge(u, v);
		while (!sA.empty() && A.find(1) == A.find(sA.back())) sA.pop_back();
		while (!sB.empty() && B.find(1) == B.find(sB.back())) sB.pop_back();
	}
	printf("%d\n", (int)res.size());
	for (auto [u, v] : res) printf("%d %d\n", u, v);
	return 0;
}

E - Mocha and Stars

给定 \(n\le 50,m\le 10^5\) ，计数 \((a_1,a_2,\cdots,a_n)\) 的个数，满足：

\(\forall 1\le i\le n, a_i\in \left[l_i, r_i\right]\cap \mathbb{Z}\)

\(\sum_{i=1}^n a_i \leq m\)

\(\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)=1\)

法一：对 \(\text{gcd}\) 容斥，设 \(f(d)\) 表示 \(d|\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)\) 的方案数，\(g(d)\) 表示 \(d=\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)\) 的方案数。

显然有 \(g(d)=f(d)-\sum_{k=2}^\infty g(kd)\) ，又由于 \(\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)\) 最大取到 \(\lfloor\frac{m}{n}\rfloor\) ，可以倒推。

求 \(f(d)\) 考虑要求每个数字都要是 \(d\) 的倍数，不妨设 \(a_i=b_id\) ，有：

\(l_i\le a_i=b_id\le r_i\) ，有 \(\lceil\frac{l_i}{d}\rceil\le b_i\le \lfloor\frac{r_i}{d}\rfloor\)
\(\sum a_i = \sum b_id\le m\) ，有 \(\sum b_i\le \lfloor\frac{m}{d}\rfloor\)

这样转化成了 \((n,\lfloor\frac{m}{d}\rfloor)\) 规模的问题。

设 \(cnt[i][j]\) 表示前 \(i\) 个数字和是 \(j\) 的方案数，前缀和优化 dp 复杂度 \(O(n\lfloor\frac{m}{d}\rfloor)\) ， \(f(d)=\sum_{k=0}^{\lfloor\frac{m}{d}\rfloor} cnt[n][k]\) 。

总复杂度为 \(O(\sum_{d=1}^{\lfloor\frac{m}{n}\rfloor} n\big\lfloor\frac{m}{d}\rfloor)=O(nm\ln m)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 51
#define M 100007
#define mod 998244353

int l[N], r[N], f[N][M], sum[N][M], ans[M];

int main() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) {l[i] = rd(); r[i] = rd();}
		
	for (int j = 0; j <= m; ++j) sum[0][j] = 1;
	auto mo = [&](int x) {return x >= mod ? x - mod : x;};
	auto dp = [&](int t, int d) {	
		for (int i = 1; i <= n; ++i) {
			int L = (l[i] + d - 1) / d, R = r[i] / d;
			for (int j = 1; j <= t; ++j) f[i][j] = 0;
			for (int j = L; j <= t; ++j) 
				f[i][j] = mo(mod + sum[i - 1][j - L] - (j - R - 1 >= 0 ? sum[i - 1][j - R - 1] : 0));
			for (int j = 1; j <= t; ++j) sum[i][j] = mo(sum[i][j - 1] + f[i][j]);
		}
		return sum[n][t];
	};
	int lim = m / n;
	for (int d = lim; d; --d) {
		ans[d] = dp(m / d, d);
		for (int i = d * 2; i <= lim; i += d) ans[d] = mo(ans[d] + mod - ans[i]);
	}
	printf("%d\n", ans[1]);
	return 0;
}

法二：直接莫比乌斯反演求容斥的系数，定义 \(\operatorname{valid}(a_1,a_2,\dots,a_n)\) 表示这个方案是否符合前两个要求。 \[ \begin{aligned} &\ \ \ \ \ \sum_{a_1=l_1}^{r_1} \sum_{a_2=l_2}^{r_2} \ldots \sum_{a_n=l_n}^{r_n}\operatorname{valid}\left(a_1, a_2, \ldots, a_n\right)\left[\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)=1\right] \\ &=\sum_{a_1=l_1}^{r_1} \sum_{a_2=l_2}^{r_2} \ldots \sum_{a_n=l_n}^{r_n} \operatorname{valid}\left(a_1, a_2, \ldots, a_n\right) \sum_{d \mid \operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)} \mu(d) \\ &=\sum_{a 1}^{r_1} \sum_{a_2=l_2}^{r_2} \cdots \sum_{a_n=l_n}^{r_n} \operatorname{valid}\left(a_1, a_2, \ldots, a_n\right) \sum_{d\left|a_1, d\right| a_2, \ldots, d \mid a_n} \mu(d) \\ &=\sum_{d=1}^m \mu(d) \sum_{a_1=\left\lceil\frac{l_1}{d}\right\rceil}^{\left\lfloor\frac{r_1}{d}\right\rfloor} \sum_{a_2=\left\lceil\frac{l_2}{d}\right\rceil}^{\left\lfloor\frac{r_2}{d}\right\rfloor} \cdots \sum_{a_n=\left\lceil\frac{l_n}{d}\right\rceil}^{\left\lfloor\frac{r_n}{d}\right\rfloor} \operatorname{valid}\left(a_1 d, a_2 d, \ldots, a_n d\right) \\ \end{aligned} \] 考虑最后一行 \(\mu(d)\) 后面的部分，可以用法一同样的 \(dp\) 计数，因此复杂度 \(O(m+\sum_{d=1}^m n\big\lfloor\frac{m}{d}\rfloor)=O(nm\ln m)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 51
#define M 100007
#define mod 998244353

int l[N], r[N], f[N][M], sum[N][M];

int prm[M], mnd[M], mu[M] = {0, 1};

int main() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) {l[i] = rd(); r[i] = rd();}
	for (int i = 2; i <= m; ++i) {
	    if (!mnd[i]) {prm[++prm[0]] = mnd[i] = i; mu[i] = mod - 1;}
	    for (int j = 1, p = prm[1], prod; j <= prm[0]; p = prm[++j]) {
	        if ((prod = i * p) > m) break;
	        mnd[prod] = p;
	        if (p == mnd[i]) {mu[prod] = 0; break;} 
	        mu[prod] = 1ll * mu[i] * mu[p] % mod;
	    }
	}

	for (int j = 0; j <= m; ++j) sum[0][j] = 1;
	auto mo = [&](int x) {return x >= mod ? x - mod : x;};
	auto dp = [&](int t, int d) {	
		for (int i = 1; i <= n; ++i) {
			int L = (l[i] + d - 1) / d, R = r[i] / d;
			for (int j = 1; j <= t; ++j) f[i][j] = 0;
			for (int j = L; j <= t; ++j) 
				f[i][j] = mo(mod + sum[i - 1][j - L] - (j - R - 1 >= 0 ? sum[i - 1][j - R - 1] : 0));
			for (int j = 1; j <= t; ++j) sum[i][j] = mo(sum[i][j - 1] + f[i][j]);
		}
		return sum[n][t];
	};
	int ans = 0;
	for (int d = 1; d <= m / n; ++d) ans = (ans + 1ll * mu[d] * dp(m / d, d)) % mod;
	printf("%d\n", ans);
	return 0;
}

Codeforces Codeforces Round

Constructive Algorithm Number Theory Counting

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

AtCoder Beginner Contest 216 Previous

AtCoder Beginner Contest 214 Next