【LGR-069】洛谷 2 月月赛 II & EE Round 2 Div. 2 题解

【LGR-069】洛谷 2 月月赛 II & EE Round 2 Div. 2

出言不逊

贪心，找到出现次数最多的字符一直加就行了，注意数据范围很大，最好开 __int128。

const int N = 1e6 + 7;
int n, ans, k;
char s[N];
__int128 l, m, x;

int main() {
	rds(s, n), rd(l), m = n;
	map<char, int> c;
	for (int i = 1; i <= n; i++) ++c[s[i]];
	for (auto o : c) k = max(k, o.se);
	x = k;
	while (m < l) m += x, x *= 2, ++ans;
	print(ans); 
	return 0;
}

谔运算

每一位是独立的，按位考虑即可，取模直接自然溢出。

const ui N = 5e5 + 7, M = 32;
ui n, a[N], ans;

int main() {
	rd(n);
	for (ui i = 1; i <= n; i++) rd(a[i]);
	for (ui i = 0; i < M; i++) {
		ui c = 0;
		for (ui j = 1; j <= n; j++) c += (a[j] >> i) & 1;
		ans += ((n * n - (n - c) * (n - c)) * (n * n - c * c) + (n - c) * (n - c) * c * c) * (1u << i);
	}
	print(ans);
	return 0;
}

直接自然溢出啥事没有

考虑递推，设 $f_i$ 表示长度为 $i$ 的「程序片段」，有 $f_0 = 1$ 。

注意到，「程序片段」只能是「程序片段」 $+$ 「语句」，若设 $c_i$ 表示长度为 $i$ 的「语句」个数，则有 $f_{i} = \sum_{j=0}^{i-1} f_jc_{i-j}$ ，则可以 $\mathcal O(n^2)$ 递推。

考虑什么东西能当「语句」。

首先，; 为一个「语句」，因此有 $f_i \leftarrow f_{i-1}$ 。

除此之外，「语句」都必须由另外一个「程序片段」生成。

我们枚举这个「程序片段」的长度 $j$ ，设其为 A，则 A 的个数为 $f_j$ 。

它会生成 {A}「语句块」和 {A}「语句」，此时出现了「语句」，则有 $f_i \leftarrow f_{i-j-2} \times f_{j}$ 。

如果此时我们还想生成「语句」，那么只能走这样一条路：「语句」 $\to$ 「函数」 $\to$ 「值」 $\to$ 「语句」。

然后就无法再生成更多的「语句」了。

「语句」 $\to$ 「函数」的过程实际上就是长度 $+2$ 或 $+4$ 。

「值」 $\to$ 「语句」的过程实际上就是长度 $+1$ 。

我们只需要考虑「函数」 $\to$ 「值」的过程，这也是最复杂的一个过程。

对于一个长度为 $l$ 的「函数」A，它会变成：

一个长度为 $l$ 的值 A；
两个长度为 $l+2$ 的值 (A),A()；
三个长度为 $l+4$ 的值 ((A)),(A()),(A)()；
四个长度为 $l+6$ 的值 (((A))),((A())),((A)()),((A))()；
$\cdots$
$n$ 个长度为 $l+(n-1)\times 2$ 的值。

考虑到「语句」 $\to$ 「函数」的过程长度 $+2$ 或 $+4$ ，「值」 $\to$ 「语句」的过程长度 $+1$ 。

将这些信息整合起来可以得到 $f_i \leftarrow f_j \sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$ 。

于是我们可以写出下面这个 $\mathcal O(n^3)$ 的程序：

const int N = 1e4 + 7;
int n;
ul f[N];

int main() {
	rd(n), f[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i-1];
		for (int j = 0; i - j - 2 >= 0; j++) {
			ul o = f[i-j-2];
			for (int k = 1; i - j - k - 4 >= 0; k += 2)
				o += f[i-j-k-4] * k;
			f[i] += o * f[j];
		}
	}
	print(f[n]);
	return 0;
}

然而，数据范围要求我们在 $\mathcal O(n^2)$ 的时间复杂度内解决。

考虑优化，注意到 $\sum_{k=1}^{i-j-4} [k \bmod 2 = 1]k \cdot f_{i-j-4}$ 这玩意儿可以前缀和优化 $\mathcal O(1)$ 得到，于是时间复杂度降为 $\mathcal O(n^2)$ 。

至于对 $2^{64}$ 取模，题目名已经告诉我们怎么做了。

const int N = 1e4 + 7;
int n;
ul f[N], g[N];

int main() {
	rd(n), f[0] = g[1] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i-1];
		for (int j = 0; i - j - 2 >= 0; j++)
			f[i] += f[i-j-2] * f[j];
		for (int j = 0; i - j - 4 >= 0; j++)
			f[i] += g[i-j-4] * f[j]; 
		for (int j = 1; i + 1 - j >= 0; j += 2)
			g[i+1] += f[i+1-j] * j;
	}
	print(f[n]);
	return 0;
}

相同的数字

最后那个相同的数只可能是 $m = \max_{i=1}^{n} a_i$ 或者 $\ge m$ 的最小质数，每次算两种的答案然后取 $\min$ 即可。

算答案的时候，将每个数加到目标值的过程按照质数划分成若干段，可以差分实现。对于长度为 $k$ 的一段，选择用 $c_1$ 还是 $c_2$ 取决于 $kc_1$ 和 $c_2$ 哪个大，显然这玩意儿是单调的，那么前缀和一下即可。

注意如果目标值是 $m$ 且 $m$ 不为质数，每个数加到 $m$ 的最后一段可能只能使用 $c_1$ 。

总时间复杂度 $\mathcal O(n + m + q)$ 。

const int N = 1e5 + 7, M = 1 << 17 | 1, P = 1e7 + 20;
int n, m, q, o, a[N], v[P], f[P], c1, c2;
vi p;
vector<ll> c[2], e[2];
ll g[2], ans;

inline void add(int o, int x, int k) {
	if (!x) return;
	if ((int)c[o].size() < x + 1) c[o].resize(x + 1);
	c[o][x] += k;
}

inline void prework(int o, int m) {
	vi d(p.size());
	for (int i = 1; i <= n; i++) {
		int x = a[i];
		if (v[x] == v[m]) add(o, m - x, 1);
		else {
			add(o, v[x] - x, 1);
			if (m == v[m]) add(o, m - p[f[v[m]]-1], 1);
			else g[o] += m - p[f[v[m]]-1];
			++d[f[v[x]]];
		}
	}
	for (ui i = 0; p[i+1] < v[m]; i++) {
		if (i) d[i] += d[i-1];
		add(o, p[i+1] - p[i], d[i]);
	}
	e[o].resize(c[o].size());
	for (ui i = 0; i < c[o].size(); i++) {
		e[o][i] = c[o][i] * i;
		if (i) e[o][i] += e[o][i-1], c[o][i] += c[o][i-1];
	}
}

inline ll solve(int o) {
	int k = min((int)1.0 * c2 / c1, (int)c[o].size() - 1);
	return (e[o][k] + g[o]) * c1 + (c[o].back() - c[o][k]) * c2;
}

int main() {
	for (int i = 2; i < P; i++) {
		if (!v[i]) p.pb(v[i] = i), f[i] = p.size() - 1;
		for (ui j = 0; j < p.size() && i * p[j] < P && p[j] <= v[i]; j++)
			v[i*p[j]] = p[j];
	}
	for (int i = P - 1; i; i--) if (v[i] != i) v[i] = v[i+1];
	rd(n), rd(q), rd(o);
	for (int i = 1; i <= n; i++) rd(a[i]), m = max(m, a[i]);
	prework(0, m), prework(1, v[m]);
	for (int i = 1; i <= q; i++) {
		rd(c1), rd(c2), c1 ^= o * ans, c2 ^= o * ans;
		print(ans = min(solve(0), solve(1)));
		ans &= M - 2;
	}
	return 0;
}

出言不逊

谔运算

直接自然溢出啥事没有

相同的数字

评论