1928D - Lonely Mountain Dungeons

题意：

有 \(n\) 个种族，第 \(i\) 个种族 \(c_i\) 个生物，现在要将这些生物分成若干组，每一对不在同一组但是同一种族的生物会对这种分组的价值贡献 \(b\)，如果分了 \(k\) 组，则价值要减去 \((k-1)x\)，求最大价值。

\(n \le 10^5，\sum c_i \le 10^5\)

思路：

对每种生物单独考虑。

假设已知分了 \(k\) 组，显然对于 \(c_i\)，分成若干个 \(\frac{c_i}{k}\) 最优。

具体的，设 \(d = \lfloor\frac{c_i}{k}\rfloor,r = c_i \bmod k\)，则我们分 \(r\) 组 \(d + 1\) 个，分 \(k-r\) 组 \(d\) 个，总共有 \(\binom{c_i}{2}-r\binom{d+1}{2}-(k-r)\binom{d}{2}\)。

总贡献应该是个是个单峰函数。

于是我们可以三分，当然二分会更好些一点，每次判断 \(f(mid)\) 与 \(f(mid+1)\) 的关系判断最大值在哪个区间即可。

时间复杂度 \(O(n \log \max c_i)\)。

考虑到生物总数比较少，我们也可以直接对每个生物枚举 \(k = 1 \sim c_i\)，这样做就不用管他单不单峰了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;

int n, b, x;
int c[N] = {0};

long long cmb(int m) {
	return 1ll * m * (m - 1) / 2;
}

long long chk(int k) {
	long long ans = 0ll;
	for (int i = 1; i <= n; i++) {
		long long d = c[i] / k;
		long long m = c[i] % k;
		ans += cmb(c[i]);
		if (c[i] >= k)
			ans -= m * cmb(d + 1) + (k - m) * cmb(d);
	}
	return ans * b - 1ll * (k - 1) * x;
}

void slv() {
	cin >> n >> b >> x;
	int mx = 0;
	for (int i = 1; i <= n; i++)
		cin >> c[i], mx = max(mx, c[i]);
	int l = 1, r = mx + 1;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		if (chk(mid - 1) <= chk(mid))
			l = mid;
		else
			r = mid;
	}
	//cout << l << endl;
	cout << chk(l) << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--)
		slv();
	return 0;
}

1928E - Modular Sequence

题意：

\(n\) 长度序列 \(a\) 满足： \(a_i = a_{i - 1} \bmod y\) 或 \(a_i = a_{i-1} + y\)，\(1 < i \le n\)。现在给定 \(x, y, S\)，求出一个序列 \(a\) 满足上述性质，第一个数为 \(x\) 且所有数之和为 \(S\)。

\(n \le 2 \times 10^5, S \le 2 \times 10^5\)

思路：

显然最终答案是 \(x, x + 1, \dots, x + k_1\) 和若干个 \(x \bmod y, x \bmod y + 1, \dots, x \bmod y + k_i\) 的形式。

先将所有 \(x \bmod y\) 减去，再将所有数除以 \(y\)，记 \(b = \frac{x - x \bmod y}{y}\)。

现在答案就是 \(b * k_1\) 加上若干个 \(0, 1, 2, \dots, k_i\)。

可以枚举 \(k_1\)，现在判断能否有若干个等差序列和为 \(sum\)。

值域不大，考虑 \(dp\)。设 \(dp[i]\) 表示和为 \(i\)，所有等差序列至少几个元素。假设最少 \(k\) 个，则比 \(k\) 大的都可以通过补 \(0\) 实现。

直接正着转移，等差序列的和是平方级别的，所有总时间复杂度是 \(O(s\sqrt s)\)。

于是就完事儿了，输出方案倒着推一遍即可。