题解 | 牛客周赛 Round 107

牛客周赛 Round 107

萌新终于第一次 ak 牛客周赛了，有点激动 qwq，终于能写一篇包含所有题目的题解了（

题解是个人题解，是纯粹的个人思路，不一定是最优的解法，但是还是希望能帮到你 qwq

A 小红打怪

最优情况下，就是伤害取到最大的情况下，就是让伤害取 ，此时的答案为 。（小技巧：）

void solve() {
	int a, l, r;
	std::cin >> a >> l >> r;
	
	std::cout << (a + r - 1) / r << "\n";
}

B 小红砍怪

题目保证了 每种血量的怪物各两只，那么我们只需要提前处理好每种血量怪物的第一次出现和最后一次出现的位置，然后枚举血量，对答案取大即可。

void solve() {
	int n;
	std::cin >> n;
	
	std::vector<int> a(2 * n);
	for (int i = 0; i < 2 * n; i++) {
		std::cin >> a[i];
		a[i]--; // 个人习惯 0 - index，这里转 0 - index
	}
	
	std::vector<int> l(n, -1), r(n, -1);
	for (int i = 0; i < 2 * n; i++) {
		if (l[a[i]] == -1) { // 如果左端点还没取到就是左端点
			l[a[i]] = i;
		} else { // 否则是右端点
			r[a[i]] = i;
		}
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++) { // 枚举血量，对答案取大
		ans = std::max(ans, r[i] - l[i] + 1);
	}
	
	std::cout << ans << "\n";
}

C 小红加强打怪

因为每次攻击不同的怪物伤害会重置为 ，所以要追求最小次数我们肯定先对着一只怪物打，打死了再换另一只，而且通过伤害会重置这一点，我们可以认为打这些怪物所需要的次数是独立计算的，也就是怪物之间击杀所需的次数互不影响。

而对于一只怪物，打出的伤害序列是 ，那么攻击 次能造成的总伤害就是 ，我们可以二分出击杀第 只怪物需要的最小次数，也就是找到最小的 使得 ，这个可以通过二分轻松解决，注意 的范围是 ，要开 。

void solve() {
	int n;
	std::cin >> n;
	
	std::vector<i64> a(n);
	for (int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	
	auto cal = [&](i64 x) -> i64 { // 找到最小的 res，使得 res * (res + 1) / 2 >= x
		i64 l = 1, r = 1E9, res;
		while (l <= r) {
			i64 mid = (l + r) / 2;
			if (mid * (mid + 1) / 2 >= x) {
				res = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		
		return res;
	};
	
	i64 ans = 0;
	for (int i = 0; i < n; i++) { // 每只怪物独立计算，对次数求和
		ans += cal(a[i]);
	}
	
	std::cout << ans << "\n";
}

D 小红走迷宫

图论题。题目相当于是说： 个点， 条边，有 个点不能经过，从 号节点开始能到达哪些点，我们只需要模拟即可，这里使用 解决。提前开好一个 数组，从 号节点开始，遇到 过的节点或者有陷阱的节点直接 ，最终看哪些房间被 数组标记了即可。

void solve() {
	int n, m, x;
	std::cin >> n >> m >> x;
	
	std::vector<bool> f(n, false); // 记录哪些房间不能去
	for (int i = 0; i < x; i++) {
		int y;
		std::cin >> y;
		y--; // 个人习惯 0 - index，这里转 0 - index
		
		f[y] = true;
	}
	
	std::vector<std::vector<int>> adj(n); // 存图
	for (int i = 0; i < m; i++) {
		int u, v;
		std::cin >> u >> v;
		u--; // 同上
		v--;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	std::vector<bool> vis(n, false);
	std::queue<int> q; // 队列实现 bfs
	q.push(0);// 起点放进去
	
	while (q.size()) {
		auto u = q.front();
		q.pop();
		
		if (vis[u] || f[u]) { // 如果访问过了或者该节点有陷阱，就不访问了
			continue;
		} else {
			vis[u] = true; // 标记来过了
			for (auto v : adj[u]) { // 访问所有子节点
				q.push(v);
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			std::cout << i + 1 << " \n"[i == n - 1]; // 访问过的输出编号
		}
	}
}

E 小苯的刷怪笼

构造题。因为讨论的主体需要 的条件，所以我们先分类讨论一下，如果 ，那么只有 这一种赋值方式，此时小红的攻击次数固定为 ，我们只需要判断 是否成立即可。

否则 ，注意题目说小红会以最优操作进行攻击，我们先来考虑一下能让小红攻击次数最大化和最小化的次数分别是多少，以及如何计算。

要让小红攻击次数最大化，那肯定要让一次攻击一个的这种情况最多，而每只怪物的血量至少要为 ，我们不难想到先让所有怪物血量都为 ，然后剩下的全部堆到最后一个怪物身上的方案。此时小红的攻击次数为 ，前半部分是因为先要把所有怪物血量都减 ，这样能一定最优，因为我们可以进行最多的一次打两只怪物的攻击，而 为奇数的时候只能浪费一次攻击一次打一只；后半部分是因为血量已经减少了共计 点，剩下的血量都在最后一只怪身上，只能一次一次打。

要让小红攻击次数最小化，那肯定要让一次攻击两个的这种情况最多，这种怎么堆都可以，但是为了简便我们选择在最后两只身上堆，因为要让一次打两个的次数最多，如果 和 奇偶性相同，那么让所有怪物全部为 后剩下的血量一定是偶数，我们直接平均分给最后两只怪物即可；如果 和 奇偶性不同，那么按奇偶性相同的堆法我们最后一定会剩一个，如果 是偶数，这种放最后两只哪只上面都可以，但是为了下面计算的简便，我们选择放最后一只上面，具体见下文；如果 是奇数，这种只能放倒数第二只上面，因为这样在击杀倒数第三只的时候能顺带打到倒数第二只，刚好能把最后两只的血量削成一样的！这样一定是最小的。而分别计算两种最小的次数，我们可以简化出 这个式子。

综上所述，能让小红行动恰好 次的充分必要条件是 ，在此之外的 都无法构造出可行的解。

这样，我们只需考虑从最小一个一个往上加就好了，在上文的合理构造下，我们每次只需一个一个从倒数第二只拿一个到最后一只身上，拿一个就能让次数从区间左端点开始加 。于是我们计算 ，（其中 是上面 所属区间的左端点）表示我们距离我们需要构造的 还要拿多少个，直接计算即可。

补充：上文 为偶数的时候放在倒数第一只的原因是，如果放在倒数第二只，第一次从倒数第二只拿一个到倒数第一只上时最优的次数不变，所以为了计算简便我们放在最后一只上。

void solve() {
	int n, a, k;
	std::cin >> n >> a >> k;

	if (n == 1) { // 特判 n == 1 的情况
		if (a == k) {
			std::cout << a << "\n";
		} else {
			std::cout << -1 << "\n";
		}
		return;
	}
	
	int l = (a + 1) / 2, r = (n + 1) / 2 + a - n; // 计算能让 k 可行的左右端点
	if (k < l || k > r) { // 在范围外则不可行
		std::cout << -1 << "\n";
	} else {
		int dif = k - l; // 还需要补多少次，-dif 表示拿走多少个，+dif 表示拿来多少个
		for (int i = 0; i < n - 2; i++) { // 前面都是 1
			std::cout << 1 << " ";
		}
		if (n % 2 == a % 2) { // 如果奇偶性相同，那么平均分配在最后两只上即可
			std::cout << (a - n + 2) / 2 - dif << " " << (a - n + 2) / 2 + dif << "\n";
		} else { // 否则根据 n 的奇偶性分配多出的那一个的位置
			if (n & 1) {
				std::cout << (a - n + 2) / 2 + 1 - dif << " " << (a - n + 2) / 2 + dif << "\n";
			} else {
				std::cout << (a - n + 2) / 2 - dif << " " << (a - n + 2) / 2 + 1 + dif << "\n";
			}
		}
	}
}

F 毒苯

计算一下暴力的复杂度肯定是会 的，我们想一下怎么优化。我们仔细思考一下，你会发现随着 的增大，能探索到的格子一定是单调不减的，也就是说，小的 能探索到的，大的 一定能探索到。那么我们不妨考虑一下按值域顺序一个个算每个 能摸到多少格子，但是我们发现 的值域太大了，不是很好枚举，但是我们又发现 的种类是不大的，因为 的种类数被 限制了，最多只有 种，而且加上表格里可能出现的 种也才 种，而且我们也只需要知道大小关系，所以我们不妨考虑离散化一下，把所有可能出现的，会进行比较的值都丢进离散化数组里离散化一下，然后对离散化之后的数组进行原来的操作，而我们不难发现我们每次是修改一整个后缀，我们不妨进行差分操作来优化复杂度。

这样，我们只需要一次 就能算出所有我们需要的 能达到多少格子，这里使用 来实现，每个节点维护三个信息：被之前遍历过的格子限制的能到达这里的最小 （下面记为 ），以及这个格子的行列信息（分别记为 ，），维护 是因为前面遍历过的格子如果很大，后面就不能统计小的 了，每次访问新的格子的时候要将 和当前格子的 取大，这样每次访问到一个新节点就让答案数组大于等于取完大的 的所有位置全部加一， 按照之前访问过的最小 使用小根堆，因为对于同一个格子，可能被访问多次，但是如果之前被很大的 限制了，这个格子能做的贡献就会缺失一部分。最后对答案数组前缀和就能算出答案了。

void solve() {
	int n, m, q;
	std::cin >> n >> m >> q;
	
	std::vector<std::vector<int>> a(n, std::vector<int>(m));
	std::vector<int> b;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> a[i][j];
			b.push_back(a[i][j]); // 这里的值参与比较，也要丢进去离散化
		}
	}
	
	std::vector<int> x(q);
	for (int i = 0; i < q; i++) {
		std::cin >> x[i];
		b.push_back(x[i]); // 询问的值参与比较，丢进去离散化
	}
	
	std::sort(b.begin(), b.end());
	b.erase(std::unique(b.begin(), b.end()), b.end()); // 离散化
	
	auto f = [&](int x) -> int { // 计算离散化数组中的排名
		return std::lower_bound(b.begin(), b.end(), x) - b.begin();
	};
	
    // 常规 bfs 操作
	std::vector<std::vector<bool>> vis(n, std::vector<bool>(m, false));
	std::vector<int> dr = {0, 0, 1, -1}, dc = {1, -1, 0, 0};
	std::priority_queue<std::array<int, 3>, std::vector<std::array<int, 3>>, std::greater<std::array<int, 3>>> pq;
	for (int i = 0; i < m; i++) {
		pq.push({a[0][i], 0, i});
	}
	
	std::vector<int> ans(b.size()); // 答案数组，目前是差分形态的
	while (pq.size()) {
		auto [lst, r, c] = pq.top();
		pq.pop();
		
		if (r < 0 || r >= n || c < 0 || c >= m || vis[r][c]) {
			continue;
		} else {
			vis[r][c] = true;
			lst = std::max(lst, a[r][c]); // lst 和 a[r][c] 取大，表示小的值走不到这个格子
  			ans[f(lst)]++; // lst 之后的所有值都加一，这里是差分，所以这一格加一就可以了
			for (int i = 0; i < 4; i++) {
				pq.push({lst, r + dr[i], c + dc[i]});
			}
		}
	}
	
	for (int i = 1; i < b.size(); i++) { // 前缀和回来
		ans[i] = ans[i] + ans[i - 1];
	}
	
	for (int i = 0; i < q; i++) {
		std::cout << ans[f(x[i])] << "\n";
	}
}