题解 | 牛客小白月赛120

牛客小白月赛120

努力开了 A ~ E， F还是太难了 qwq，但是尽力码了 A ~ E 的题解，希望能帮到你 qwq

A 牛牛的串串

可以不用排序，直接用 记录下所有出现了的字母的数量（但是好像 的自动排序也是排序（ ），然后开一个 变量，记录上一个访问的字母的数量，然后一个个判断就可以了。

void solve() {
	int n;
	std::cin >> n;
	
	std::string s;
	std::cin >> s;

	std::map<char, int> cnt;
	for (int i = 0; i < n; i++) {
		cnt[s[i]]++;
	}
	
	int lst = 0;
	bool ok = true;
	for (auto [_, x] : cnt) {
		if (lst == 0) { // 第一次跳过
			lst = x;
			continue;
		} else {
			if (x != lst + 1) { // 如果次数 +1 了就继续
				ok = false;
				break;
			} else { // 否则退出
				lst = x;
			}
		}
	}
	
	if (ok) {
		std::cout << "YES\n";
	} else {
		std::cout << "NO\n";
	}
}

B 牛牛的合数

构造题。由于大于 的偶数一定是合数，我们不妨按奇偶分类讨论一下：

1. 如果 是奇数，那么一般来说， 一定是偶数，我们只需要排除异或完是 的情况，也就是 和 ，对于 ，手动推一下可以知道也是无解的；

2. 如果 是偶数，那么我们只要不动二进制的最低位，怎么异或都是偶数，只需要判断二进制最高位是不是第二位即可，也就是 是不是 ，如果 是 ，那么手推一下可以知道是无解的，如果大于 了，我们只要每次都异或一个 ，结果一定还是偶数且不是 。

void solve() {
	int x;
	std::cin >> x;
	
	if (x & 1) {
		if (x == 1 || x == 3) {
			std::cout << -1 << "\n";
		} else {
			std::cout << 1 << "\n";
		}
	} else {
		if (x == 2) {
			std::cout << -1 << "\n";
		} else {
			std::cout << 2 << "\n";
		}
	}
}

C 牛牛的排列

我们考虑顺序的排列： ，这个排列相邻元素的 之和一定是 ，因为数轴上相邻的两个正整数一定是互质的。这样当 为奇数的时候，要求的和一定是偶数，直接输出完全顺序的排列即可；

当 为偶数的时候，要求的和一定是奇数，考虑一下怎么才能让要求的和偏移 ，我们可以交换 的位置，这样 的 是 ，能让最终的和 ，而 ，和原来这个位置的贡献相比不变。

void solve() {
	int n;
	std::cin >> n;
	
	if (n & 1) {
		for (int i = 1; i <= n; i++) {
			std::cout << i << " \n"[i == n];
		}
	} else {
		if (n == 2) {
			std::cout << -1 << "\n";
		} else {
			for (int i = 1; i <= n; i++) {
				if (i == 2) {
					std::cout << 3 << " ";
				} else if (i == 3) {
					std::cout << 2 << " ";
				} else {
					std::cout << i << " \n"[i == n];
				}
			}
		}
	}
}

D 牛牛的子序列

由于后面的分析需要用到 的条件，这里我们先按 的大小情况分类讨论一下：如果 ，那么一定是不合法的，因为数组的长度不会变小，无解；

否则 ，我们有如下的分析：

这里使用双指针。开两个指针 ，分别在数组 中扫，每次扫一段数值相同的位置，首先如果这一段的元素种类都不同，那么可以直接判断无解，否则分别记 扫过的长度为 ，那么如果 ，可以直接判断无解，因为操作不会使这样一段的长度变小；否则 ，我们就按这样的规则扫完，而如果 都扫完了， 还有一边的指针在数组内，说明元素多了，这种情况也是无解的。

然后我们想一下最少需要多少次，首先，一次能选择一段子序列，那么我们肯定是同时进行最好，那么我们就可以把每一段的增长过程看作独立的，最终对每段的操作次数取大就可以了，然后我们再考虑每一段怎么能使操作次数最小：其实只要让增长速度最快就好了，就相当于每次都是全选这段区间，相当于长度 ，这样的话，我们的问题就变为了：求得最小的 ，使得 ，而这个是可以通过二分解决的。

总时间复杂度 。

void solve() {
	int n, m;
	std::cin >> n >> m;
	
	std::vector<int> a(n), b(m);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		std::cin >> b[i];
	}
	
	if (m < n) {
		std::cout << -1 << "\n";
	} else { // m >= n
		auto cal = [&](int x, int y) -> int { // 求最小的 res，使得 x * (2 ^ res) >= y
			int l = 0, r = 32, res;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (1LL * x * (1LL << mid) >= y) {
					res = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			
			return res;
		};
	
		int i = 0, j = 0, ans = 0; // 双指针
		while (j < m) {
			if (a[i] != b[j]) { // 如果元素都不同，可以直接判断无解了
				std::cout << -1 << "\n";
				return;
			}
			
			int lsti = i, lstj = j; // 移动元素相同的一段距离
			while (i < n - 1 && a[i] == a[i + 1]) {
				i++;
			}
			while (j < m - 1 && b[j] == b[j + 1]) {
				j++;
			}
			
			if (j - lstj < i - lsti) { // 如果 leni > lenj，直接判断无解，因为操作不会使得一段的长度变小
				std::cout << -1 << "\n";
				return;
			}
			
			ans = std::max(ans, cal(i - lsti + 1, j - lstj + 1)); // 这一段的次数和答案取大
			i++, j++; // 移动到下一段
			
			if (i >= n && j < m) { // 如果一边扫完了，另一边还在数组内，那就是元素多了，也可以直接判断无解
				std::cout << -1 << "\n";
				return;
			}
		}
		
		std::cout << ans << "\n";
	}
}

E 牛牛的约数

题目要求 ，我们不妨先另开一个数组（记为 ）排个序，然后在 数组中进行我们的操作，这里我们采用双指针。

开两个指针 （这里的 不是 题目里的 ）我们用 遍历整个 数组，用 表示当前筛选到哪个数了， 正常遍历，每遍历到一个新的位置，先让 把所有 小于等于 的数全部标记为 （标记的数组记为 ），然后再对更大的数直接判断是否满足 ，是的话标记为 ，否则不用管，继续遍历。

但是会不会存在一种情况，使得 扫到一个值退出了，但是后面还有一个值不是 的倍数，且这个数被忽略掉呢？

可以证明是不会忽略掉的，假设三个数 ，对应上面的情况，有 ，此时 的因子一定包含 ，而 的因子一定不包含 ，所以就算不会被 筛掉，那也一定会被 筛掉的，因为 的因子根本就不包含 ， 也就一定不会是 的一个因子了。

这样我们最终就会得到所有在 数组中出现的数的其中一个因子在 数组中的位置（否则是 ），然后我们新开一个 数组记录 数组中的数在 数组中对应的位置，这里用 即可。

然后回答的时候遍历原数组，答案先对应到 数组里，再转到 数组，再转到 数组 ，时间复杂度 。

void solve() {
	int n;
	std::cin >> n;
	
	std::vector<i64> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	
	std::vector<i64> f = a;
	std::sort(f.begin(), f.end());

	std::vector<int> g(n); // g[i] 表示 f[i] 的一个因子在 f 数组的位置
	int j = 0;
	for (int i = 0; i < n; i++) {
		while (j < n && f[j] <= f[i]) { // 如果 f[j] <= f[i] 了还没被统计，那永远都不会被统计了
			g[j] = -1;
			j++;
		}
		while (j < n && f[j] % f[i] != 0) { // 如果能整除，就记录下因子在 f 数组中的位置
			g[j] = i;
			j++;
		}
	}
	
	std::vector<int> pos(n); // pos[i] 表示 f[i] 在 a 数组中出现的其中一个位置（这么写的话是最后一个）
	for (int i = 0; i < n; i++) {
		pos[std::lower_bound(f.begin(), f.end(), a[i]) - f.begin()] = i;
	}
	
	for (int i = 0; i < n; i++) {
		int p = g[std::lower_bound(f.begin(), f.end(), a[i]) - f.begin()];
        // p 是 a[i] 对应到 f 数组中的数的一个因子在 f 数组中的位置
        
		if (p == -1) { // 如果是 -1，答案也是 -1
			std::cout << -1 << " \n"[i == n - 1];
		} else { // 否则答案是 f[p] 在 a 数组中的位置，也就是 pos[p]
			std::cout << pos[p] + 1 << " \n"[i == n - 1];
		}
	}
}