【题解】牛客小白月赛62

出题人发成了博客，我在这边重新发一遍原博客链接：https://blog.nowcoder.net/n/899c42c0093340da806279bc1ecc8cb6

A

本题数据范围较小，可以直接枚举每一天每一棵树的变化。

坑点：求第 $m$ 天中午的状态实际上是进行了 $m - 1$ 次变化（生长和剪切）。

时间复杂度： $O(T \times n\times m)$ 。

B

注意到 $x$ 的取值不超过区间中数的个数，这说明区间中的数模 $x$ 的余数必然可以得到： $0, 1, \dots, x - 1 0,1,…,x-1$ ，中的任意一个，这意味着答案只能是 1 或者是 0，下面给出证明。

假设区间中数的和为 $s u m$ 那么必然存在一个数 $y\ \ (l \leq y \leq r)$ 使得： $sum\ \%\ x = y\ \%\ x$ 成立。故可以通过同时选择除 $y$ 以外的所有数将它们消去，最后判断 $y\ \%\ x = 0$ （等价于 $sum\ \%\ x = 0$ ）是否成立即可确定答案是 1 还是 0。

坑点：求 $s u m$ 需使用等差序列求和公式 $(l + r) \times (r - l + 1)\ /\ 2$ 加速。

时间复杂度： $O(T\times m)$ 。

C

考虑判断两个数组是否不互相独立，两个数组不互相独立等价于存在一个数 $x$ （不为 1）使得其在两个数组中都能找到倍数。

注意到数组中数的取值区间是 $[1, 1 0^{6}]$ ，所以可以像质数筛法一样直接枚举 $[2, 1 0^{6}]$ 中的每一个数，然后统计其倍数是否在两个数组中都出现过即可。

时间复杂度： $O(M\times \log M)$ （这里 $M = 1 0^{6}$ ）。

D

通过观察树的形态我们可以得知：以 $x$ 结点为根结点的子树中任意一层的结点编号都是连续的。

当 $k = 1$ 时答案即为： $n - x$ 。

当 $k > 1$ 时：注意到树的高度是 $\log_kn$ 所以可以直接递推每一层的编号最左和最右的结点即可得到最终的答案。

坑点：分类讨论。编号为 $n$ 的结点是不存在的，注意边界条件。

时间复杂度： $O(T\times m\times \log_kn)$ 。（ $k > 1$ ）

E

本题的第三种操作可以转化成第一种操作，第四种操作可以转化成第一种和第三种操作，所以接下来我们只讨论怎么计算操作一和操作三对答案的影响。

将两种操作分开考虑，可以发现对于第一种操作可以直接利用 dfs 进入递归之前收集然后将影响传递给儿子结点，对于第三种操作可以在 dfs 函数返回结点的时候收集儿子结点对当前结点的影响即可。

上述解决方案的时间复杂度是 $O (n)$ 的。

F

让我们考虑一个简单的 dp ：定义 $d p [i] [x] [y]$ 代表当前遍历到了第 $i$ 个字符，以第 $i$ 个字符结尾的子串中含有 $x$ 个 "a" 子序列， $y$ 个 "ac" 子序列的方案数。其转移方程为： 1、若 $s [i]$ 是字符 'a' ： $dp[i][x + 1][y] = dp[i - 1][x][y]\$ ，特别的： $\ dp[i][1][0] = dp[i - 1][0][0] + 1$ 。 2、若 $s [i]$ 是字符 'c' ： $dp[i][x][y + x] = dp[i - 1][x][y]\$ ，特别的： $\ dp[i][0][0] = dp[i-1][0][0] + 1$ 。 3、若 $s [i]$ 不是字符 'a' 或 'c' ： $dp[i][x][y] = dp[i - 1][x][y]\$ ，特别的： $\ dp[i][0][0] = dp[i-1][0][0] + 1$ 。

上述这个 dp 的时空复杂度是 $O ((s . l e n g t h)^{4})$ 的，但是注意到题面要求的方案数仅是区间中包含偶数个子序列，所以我们可以直接将上述 dp 方程中的 $x, y$ 压缩成 0 1 两种状态（其中 0 代表偶数，1 代表奇数）仍旧是可以转移的，但是如果这么标记我们在统计答案时将无法区分子串中不含 "ac" 子序列和含有偶数个 "ac" 子序列的方案，于是考虑额外添加一维具有三种状态 0 1 2 （其中 0 代表子串中不含子序列 "a" 和子序列 "ac"，1 代表子串中含有子序列 "a" 不含子序列 "ac"，2 代表子串中含有子序列 "ac"），其转移方程与上述转移方程类似，至此整个过程可以转移出最终的答案。

时间复杂度： $O (s . l e n g t h)$ 。

参考代码：

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

void solved() {
	int n;  cin >> n;
	vector<int> ve(n);
	for(int &x: ve) cin >> x;
	int a, k, b;
	cin >> a >> k >> b;
	int m;  cin >> m;
	for(int j = 2; j <= m; j ++) {
		for(int &x: ve) {
			x += a;
			if(x > k) x = b;
		}
	}
	for(int x: ve) cout << x << ' ';
	cout << endl;
}
int main() {
	int ttx;  cin >> ttx;
	while(ttx --) {
		solved();
	}
	return 0;
}

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

void solved() {
	int l, r;  cin >> l >> r;
	int m;  cin >> m;
	long long sum = 1ll * (l + r) * (r - l + 1) / 2;
	int x;
	while(m --) {
		cin >> x;
		if(sum % x == 0) puts("0");
		else puts("1");
	}
}
int main() {
	int ttx;  cin >> ttx;
	while(ttx --) solved();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1000009;

bool a[N], b[N];
bool ans = true;

int main() {
	int n;  cin >> n;
	int x;
	for(int i = 0; i < n; i ++) {
		cin >> x;
		a[x] = true;
	}
	for(int i = 0; i < n; i ++) {
		cin >> x;
		b[x] = true;
	}
	for(int i = 2; i <= 1000000; i ++) {
		int f = 0;
		for(int j = i; j <= 1000000; j += i) {
			if(a[j]) f |= 1;
			if(b[j]) f |= 2;
		}
		if(f == 3) ans = false;
	}
	if(ans) puts("Yes");
	else puts("No");
	return 0;
}

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

void solved() {
	ll n;  cin >> n;
	int k, m;  cin >> k >> m;
	while(m --) {
		ll x;  cin >> x;
		ll l = x, r = x, ans = 0;
		if(k == 1) ans = n - x, l = n;
		while(true) {
			if(l >= n) break;
			if(r >= n) {
				ans += n - l;
				break;
			} 
			ans += r - l + 1;
			l = k * l + 1, r = k * r + k;
		}
		cout << ans << endl;
	}
}
int main() {
	int ttx;  cin >> ttx;  while(ttx --)
	solved();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 10000009, M = 500009;

int n;
int rt[N][2];
int cnt[M];

int dfs(int x, int sum) {
	if(x > n) return 0;
	sum += rt[x][0];
	int ans = sum, add = rt[x][1];
	add += dfs(2 * x, sum);
	add += dfs(2 * x + 1, sum);
	cnt[ans + add] ++;
	return add;
}
int main() {
	int m;  cin >> n >> m;
	int op, x;
	for(int i = 0; i < m; i ++) {
		cin >> op >> x;
		if(op == 1) {
			rt[x][0] ++;
		} else if(op == 2) {
			rt[x][0] --;
			rt[1][0] ++;
		} else if(op == 3) {
			rt[x][1] ++;
		} else {
			rt[x][1] --;
			rt[1][0] ++;
		}
	}
	dfs(1, 0);
	for(int i = 0; i <= m; i ++) cout << cnt[i] << ' ';
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 500009;
#define ll long long 

ll f[N][3][2][2];  /// 有效区域：000,100,110,200,201,210,211

char s[N];
int main() {
	scanf("%s", s + 1);
	ll ans = 0;
	for(int i = 1; i <= strlen(s + 1); i ++) {
		if(s[i] == 'a') {
			f[i][0][0][0] = 0;
			f[i][1][0][0] = f[i - 1][1][1][0];
			f[i][1][1][0] = f[i - 1][1][0][0] + f[i - 1][0][0][0] + 1;
			f[i][2][0][0] = f[i - 1][2][1][0];
			f[i][2][0][1] = f[i - 1][2][1][1];
			f[i][2][1][0] = f[i - 1][2][0][0];
			f[i][2][1][1] = f[i - 1][2][0][1];
		} else if(s[i] == 'c') {
			f[i][0][0][0] = f[i - 1][0][0][0] + 1;
			f[i][1][0][0] = 0;
			f[i][1][1][0] = 0;
			f[i][2][0][0] = f[i - 1][1][0][0] + f[i - 1][2][0][0];
			f[i][2][0][1] = f[i - 1][2][0][1];
			f[i][2][1][0] = f[i - 1][2][1][1];
			f[i][2][1][1] = f[i - 1][1][1][0] + f[i - 1][2][1][0];
		} else {
			f[i][0][0][0] = f[i - 1][0][0][0] + 1;
			f[i][1][0][0] = f[i - 1][1][0][0];
			f[i][1][1][0] = f[i - 1][1][1][0];
			f[i][2][0][0] = f[i - 1][2][0][0];
			f[i][2][0][1] = f[i - 1][2][0][1];
			f[i][2][1][0] = f[i - 1][2][1][0];
			f[i][2][1][1] = f[i - 1][2][1][1];
		}
		ans += f[i][2][1][0] + f[i][2][0][0];
	}
	cout << ans;
	return 0;
}