本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-21 21:08:23

A. 归回

题意

求 $x^2 - y^2 = m$ 的一组非负整数解，或判定无解。

解析

考虑到某个数的平方模四一定为 $0$ 或 $1$，那么两个数的平方差就一定是 $0, 1, 3$ 中其中一个，即不可能是 $2$。因此，$m\equiv 2 \pmod 4$ 时无解。

考虑接下来怎么构造解。首先，原式即 $(x + y)(x - y) = m$，即 $pq = m$，其中 $2\mid p + q$。

当 $2\nmid m$ 时，不难注意到一组合法解 $p = 1, q = n$，对应原始解 $x = (n + 1) / 2, y = (n - 1) / 2$。

当 $2\mid m$，即 $4\mid m$ 时（由前面无解限制），可以构造 $p = 2, q = n / 2$，因为 $2 \mid n / 2$。此时对应原始解 $x = n/4 + 1, y = n / 4 - 1$。

本题是二潘初等数论上搬下来的练习题，也用了一些处理平方的常用技巧（如模 $4$）。

预估难度：黄

标程

#include <iostream>
using namespace std;

int main (void)
{
	int t;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> t;
	while (t--) {
		long long n;
		
		cin >> n;
		if (n % 4 == 2) cout << "-1\n";
		else if (n % 2) cout << (n - 1) \/ 2 << ' ' << (n + 1) \/ 2 << '\n';
		else if (n % 4 == 0) cout << n \/ 4 + 1 << ' ' << n \/ 4 - 1 << '\n';
	}
	return 0;
}

B. 连续

题意

给定一个只包含 $1$ 和 $2$ 的序列，询问一个 $k$，求构造一个区间使得区间和为 $k$。

解析

只有 $1$ 和 $2$ 两个数是核心。若有一个区间和为 $k$ 且 $k\gt 2$，那么一定存在一个区间和为 $k - 2$。这是好构造的。如果这个和为 $k$ 的区间有一个端点值为 $2$，那么删掉它；否则，由于 $k\gt 2$，知两端点值均为 $1$，删掉它俩，得到和为 $k - 2$ 的区间。

于是我们就可以找出和为奇数和和为偶数的最大两区间，然后进行模拟，并预处理出答案。

无解当且仅当 $k$ 大于与 $k$ 奇偶性相同的最大区间和。

标程

#include <iostream>
using namespace std;
const int N = 1e6 + 10, K = 2 * N;
int f[2], z[N], sum[N], l[K], r[K];

void dfs (int x)
{
    if (x <= 2) return;
    if (z[l[x]] == 1 && z[r[x]] == 1) l[x - 2] = l[x] + 1, r[x - 2] = r[x] - 1, dfs (x - 2);
    else if (z[l[x]] == 2) l[x - 2] = l[x] + 1, r[x - 2] = r[x], dfs (x - 2);
    else l[x - 2] = l[x], r[x - 2] = r[x] - 1, dfs (x - 2);
}

int main (void)
{
    int n, q, lfi, rfi;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> z[i];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + z[i];
    for (lfi = 1; lfi <= n && z[lfi] == 2; lfi++);
    for (rfi = n; rfi >= 0 && z[rfi] == 2; rfi--);
    f[sum[n] & 1] = sum[n], l[sum[n]] = 1, r[sum[n]] = n;
    if (sum[n] - sum[lfi] > sum[rfi]) l[f[sum[n] & 1 ^ 1] = sum[n] - sum[lfi]] = lfi + 1, r[f[sum[n] & 1 ^ 1]] = n;
    else l[f[sum[n] & 1 ^ 1] = sum[rfi - 1]] = 1, r[f[sum[n] & 1 ^ 1]] = rfi - 1;
    dfs (f[0]), dfs (f[1]);
    while (q--) {
    	int k;
    	cin >> k;
    	if (k > f[k & 1]) cout << "-1 -1\n";
    	else cout << l[k] << ' ' << r[k] << '\n';
    }
    return 0;
}

C. 平方

题意

对于 $[l, r]$ 上每个数 $x$，求与它最近的完全平方数 $y$。若 $y$ 为奇，答案加上 $x$；否则答案减去 $x$。求最后答案。

解析

首先没有无解情况，因为两个相邻的完全平方数差为奇数。$(n + 1)^2 - n^2 = 2n + 1$。

我们将 $[n^2, (n+1)^2)$ 设做一个大区间。不难发现，$[n, n(n + 1)]$ 是离 $n^2$ 更近的，$(n(n+1), (n+1)^2)$ 是离 $(n+1)^2$ 更近的。如果从 $n = 1$ 开始划分区间，那么 $n^2$ 是奇数，$(n+1)^2$ 是偶数，如此交错。因而 $[n, n(n+1)]$ 区间贡献负，$(n(n+1),(n+1)^2)$ 贡献正。

巧妙之处在于，很难不注意到，每一个大区间的贡献抵消了。

现在我们就知道了怎么 $O(1)$ 算 $[1, x]$ 区间的答案。然后差分即可。

标程

#include <iostream>
#include <cmath>
using namespace std;
using i128 = __int128_t;
const i128 P = 1e9 + 7, i2 = (P + 1) \/ 2;

i128 solve (i128 x)
{
	i128 k = sqrtl (x), d = k * (k + 1), sign = k * k % 2 ? 1 : P - 1, s = min (x, d);
	i128 res = (k * k % P + s) % P * (s - k * k % P + 1) % P * i2 % P * sign % P;
	if (x <= d) return res;
	return (res + P - (d + 1 + x) % P * (x - d) % P * i2 % P * sign % P) % P;
}

signed main (void)
{
	int t;
	long long l, r;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> t;
	while (t--) {
		cin >> l >> r;
		cout << (long long) ((solve (r) + P - solve (l - 1)) % P) << '\n';
	}
	return 0;
}

D. 密码

题意

给定一系列由小写字母构成的字符串。设密钥为一个未知的小写字母的排列，定义加密过程表示在一个字符串上将每个字符替换为密钥中对应位置的字符。现已知每个字符串加密后的字典序排名，求构造一个可能的密钥。

解析

比较板的一道题。我们发现两个字符串字典序偏序，当且仅当其第一个不相同的字符偏序。那么就可以用拓扑排序构造出每个字符之间的关系。

这样建图有 $n^2$ 条边。我们考虑到，图上关系是传递的，因此我们可以只连接两个相邻字符串首个不同字母。

求 LCP 可以用哈希，没卡。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define fi first
#define se second
using namespace std;
using u64 = unsigned long long;
const int N = 1e6, S = 1e7;
const u64 base = 37, P = 1e9 + 7;
vector<u64> z[N];
string s[N];
char res[30];
int p[N], w[N], id[30], deg[30];
vector<int> e[30];

int lcp (int x, int y)
{
	int l = 0, r = min (s[x].length (), s[y].length ()), k = 0;
	while (l <= r) {
		int mid = (l + r) \/ 2;
		if (z[x][mid] == z[y][mid]) l = (k = mid) + 1;
		else r = mid - 1;
	}
	return k;
}

int main (void)
{
	int n, tst = 0;
	queue<int> q;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		int m = s[i].length ();
		z[i].reserve (m + 1);
		for (int j = 1; j <= m; j++) z[i][j] = (z[i][j - 1] * base + s[i][j - 1] - 'a' + 1) % P;
	}
	
	for (int i = 1; i <= n; i++) cin >> w[i], p[i] = i;
	sort (p + 1, p + n + 1, [](int x, int y) { return w[x] < w[y]; });
	for (int i = 2; i <= n; i++) {
		int k = lcp (p[i], p[i - 1]);
		if (k == s[p[i - 1]].length ()) continue;
		int c = s[p[i]][k] - 'a' + 1;
		e[s[p[i - 1]][k] - 'a' + 1].push_back (c), deg[c]++;
	}
	for (int i = 1; i <= 26; i++) if (!deg[i]) q.push (i);
	while (!q.empty ()) {
		int u = q.front (); q.pop ();
		id[++tst] = u;
		for (auto v : e[u]) if (!--deg[v]) q.push (v);
	}
	
	for (int i = 1; i <= 26; i++) res[id[i]] = 'a' + i - 1;
	puts (res + 1);
	return 0;
}