CF1562 Codeforces Round 741

Codeforces Round #741 (Div. 2)

C - Rings

题意

给出一个二进制串 $S$，长度为 $N$，你可以在上面做 $[l, r]$ 的截断，函数 $f(l,r)$ 表示：将 $S$ 中 $[l,r]$ 的截断取出，然后转换为十进制的数。

要求找出两对不同的 $(l_1, r_1), (l_2, r_2)$ 满足以下条件：

• $1\leqslant l_1\leqslant r_1\leqslant n, r_1-l_1+1\geqslant\lfloor\frac{n}{2}\rfloor$

• $1\leqslant l_2\leqslant r_2\leqslant n, r_2-l_2+1\geqslant\lfloor\frac{n}{2}\rfloor$

• $l_1\neq l_2$ 和 $r_1\neq r_2$ 至少有一个满足。

• 存在一个非负整数 $k$，使得 $f(l_1, r_1) = f(l_2, r_2) \cdot k$。

题目保证有解，任意给出一组解即可。

数据范围：$2\leqslant N \leqslant 2\times 10^4$。

思路

不要把 $k$ 想的很复杂，可以就考虑几个简单的，如 $0, 1, 2$ 即可。

这个题就是构造出一种解就完事了，所以进行分类讨论。

• 如果 $S$ 中所有字符都相等，则直接输出 $[1, n-1], [2, n]$ 即可，因为他们直接相等。

由于题目要求取出的串长度大于等于 $\lfloor \frac{n}{2}\rfloor$，所以考虑从 $S$ 串的 $\left\lfloor\frac{n}{2}\right\rfloor$ 位置作为截断，分左右进行讨论。

• 如果 $S$ 的左半部分位置 $x\leqslant \left\lfloor\frac{n}{2}\right\rfloor$ 处为 $0$，则输出 $[x, n], [x+1, n]$，因为前导零去掉后，他们直接相等。

• 如果 $S$ 的右半部分位置 $x > \left\lfloor\frac{n}{2}\right\rfloor$ 处为 $0$，则输出 $[1, x], [1, x-1]$，因为后置零，可以通过 $\times 2$ 得到，$f(1,x)=f(1,x-1)\cdot 2$。

以上就已经讨论完了所有可能情况了，按情况输出即可。

时间复杂度 $O(T\times N)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		string s;
		cin >> n >> s;
		bool fg = 0;
		for (int i = 1; i <= n; i++) {
			if (s[i-1] == '0') {
				if (i <= n/2) {
					cout << i << ' ' << n << ' ' << i + 1 << ' ' << n << '\n';
				} else {
					cout << 1 << ' ' << i << ' ' << 1 << ' ' << i - 1 << '\n';
				}
				fg = 1;
				break;
			}
		}
		if (!fg) cout << 1 << ' ' << n-1 << ' ' << 2 << ' ' << n << '\n';
	}
	return 0;
}

D - Two Hundred Twenty One

题意

给出一个长度为 $N$ 的字符串 $S$ 和 $Q$ 次询问，每次询问一个区间 $[l_i, r_i]$。

对于数列 $a_1, a_2, \ldots, a_n$，定义“不同符号和”(sign-variable)：

$s(\{a_n\}) = a_1-a_2+a_3-a_4+\cdots + (-1)^{n-1}\cdot a_n= \sum_{i=1}^n(-1)^{i-1}\cdot a_i$

现在数列 $a_1, a_2, \ldots, a_n$ 只有 $+1$ 和 $-1$ 构成，通过只含有正负号的字符串 $S$ 给出
如果 $a_i=1\Rightarrow S_i=\texttt{+}$，$a_i=-1\Rightarrow S_i=\texttt{-}$

每次询问给出区间 $[l_i, r_i]$，设字符串 $T = S_{l_i}S_{l_i+1}\cdots S_{r_i}$，求至少要从 $T$ 中删除多少个字符才能使得 $s(T) = 0$，并给出每次删除的字符位置。（第一个问题是D1所要求的，第二个问题是D2所要求的）。

数据范围：$1\leqslant N, Q\leqslant 3\times 10^5$。

思路

我们先不考虑 $S$ 的子串问题，先考虑整个 $S$ 串。

设 $s(l, r) = \sum_{i=l}^r(-1)^{i-1}a_i$，表示 $s(S)$ 中 $[l, r]$ 这一段的不同符号和。

设 $f(i)$ 为去掉 $S$ 串中第 $i$ 个字符后变为 $S'$，整个 $S'$ 的不同符号和，即 $f(i)=s(S')$。

命题1：$|f(i)-f(i+1)| = 0 \text{或} 2$

证明：

不难发现：

$$\begin{aligned} &f(i)= s(1, i-1) - s(i+1, n)\\ &f(i+1)=s(1,i)-s(i+2, n)\\ \Rightarrow & |f(i)-f(i+1)|=|s(i, i)+s(i+1, i+1)|=|a_i-a_{i+1}| \end{aligned}$$

则：

• 当 $a_i=a_{i+1}$ 时，$|f(i)-f(i+1)|=0$。

• 当 $a_i\neq a_{i+1}$ 时，$|f(i)-f(i+1)| = 2$。

QED

下面这个结论不难证明：

命题2：$|S|$ 与 $s(S)$ 同奇偶性，也就是字符串长度和字符串的不同符号和的奇偶性相同。

因为 $+1$ 和 $-1$ 之和会发生抵消，抵消以后字符总数 $-2$ 不影响奇偶性，所以最终的不同符号和奇偶性与开始时的字符总长奇偶性相同。

所以，如果 $s(S) = 0$ 则一定有 $|S|$ 为偶数。

命题3：当 $s(1,n)\neq 0$ 时，$f(1)\cdot f(n) \leqslant 0$。

证明：

命题等价于证明 $f(1)$ 和 $f(n)$ 异号，或者至少有一个为 $0$。

$$\begin{aligned} &f(1)=-s(2, n)=a_1-s(1,n)\\ &f(n)=s(1, n-1)=s(1, n)-a_n\\ \end{aligned}$$

由于 $|s(1, n)| \geqslant 1$，所以 $f(1)$ 和 $f(n)$ 的符号只能取决于 $s(1,n)$ 的符号，$a_1, a_n$ 对它们的影响太小，而 $s(1, n)$ 在 $f(1),f(n)$ 中的符号正好是一正一负，所以 $f(1),f(n)$ 只能异号，或者至少一个为 $0$。

QED

下面给出删除方法：

设 $n=|S|$ 为奇数，则 $f(i)$ 为偶数，因为它从 $S$ 中删除了一个字符。

又通过命题1知，相邻的 $f(i), f(i+1)$ 之间差值为 $0$ 或 $2$，由命题3知，$f(1), f(n)$ 异号，则一定存在 $k$，使得 $f(k)=0$，可以通过反证法证明。（类似于连续函数的零点存在定理）

则说明，对于长度为奇数的串，我们一定可以找到 $f(k)=0$，即将 $a_k$ 从 $S$ 删除即可满足题意。

如果长度为偶数的串，可以先删除 $a_n$ 使得它的长度变为奇数且 $s(1, n-1)$ 不会发生变化，然后再按照奇数的删除方法删除。

综上，最大的删除字符个数不会超过2个。

拓展到任意 $S$ 的子串 $T$ 方法很简单，只需要求出 $s(T)$ 即可，所以可以通过维护函数 $s$ 的前缀和完成。

于是对于长度为 $n$ 的字符串 $S$：

• $s(S) = 0$ 输出 $0$。

• $n$ 为奇数，输出 $1$。

• $n$ 为偶数，输出 $2$。

时间复杂度 $O(N)$。

下面给出 D1(easy version) 的代码：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		string s;
		cin >> n >> m >> s;
		vi sum(n+1);
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i-1] + (s[i-1] == '+' ? 1 : -1) * (i % 2 == 1 ? 1 : -1);
		}
		while (m--) {
			int l, r;
			cin >> l >> r;
			if (sum[r] - sum[l-1] == 0) cout << 0 << '\n';
			else if ((r - l + 1) % 2 == 1) cout << 1 << '\n';
			else cout << 2 << '\n';
		}
	}
	return 0;
}

对于 D2 (hard version) 只需要求出每次奇数长度时删除的位置 $k$ 即可。

我们知道计算函数零点，可以通过二分完成，所以直接二分零点即可。

时间复杂度 $O(N\log N)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		string s;
		cin >> n >> m >> s;
		vi sum(n+1);
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i-1] + (s[i-1] == '+' ? 1 : -1) * (i % 2 == 1 ? 1 : -1);
		}
		while (m--) {
			int l, r;
			cin >> l >> r;
			if (sum[r] - sum[l-1] == 0) cout << 0 << '\n';
			else {
				if ((r - l + 1) % 2 == 0) {
					cout << 2 << '\n' << r << ' ';
					r--;
				}
				else cout << 1 << '\n';
				int L = l, R = r;
				while (l <= r) {
					int mid = (l + r) >> 1, x = mid;
					if ((sum[x-1] - sum[L-1] - sum[R] + sum[x]) * (-sum[R] +sum[L]) <= 0) r = mid - 1;
					else l = mid + 1;
				}
				cout << l << '\n';
			}
		}
	}
	return 0;
}

E - Rescue Niwen!

题意

给出一个长度为 $N$ 的字符串 $S$，以 $S$ 的子串：$S_1, S_{1, 2}, S_{1, 3}, \ldots, S_{1, n}, S_2, S_{2, 3}, S_{2, 4}, \ldots, S_{2, n}, \ldots, S_{n-1}, S_{n-1, n}, S_n$，构成的字符串序列中，最长单调递增子序列长度为多少？（字符串排序方法按照字典序排序，单调在这里是指严格单调）

数据范围：$1\leqslant N \leqslant 5000$。

思路

最开始想先预处理出来所有子串的字典序大小，用字典序大小代替原来的字符串序列，然后直接通过 lower_bound 求最长上升子序列，这样复杂度是 $O(N^2\log N^2)$ 理论上过不了，最终优化到了 3s，实在写不进 2s 了，最后放弃了这种写法，后来看题解发现这道题有很好的性质。

如果字符串 $S_{l_1, r_1}$ 在最长上升子序列中，则 $S_{l_1, n}$ 也一定在其中。

所以如果 $S_{l_2, r_2}$ 考虑从前一个转移，就只用考虑从 $S_{l_1, n}$ 进行转移，保证 $S_{l_2, r_2} > S_{l_1, n}$。

这里可以通过求每个后缀 $S_{l_1, n}, S_{l_2, n}$ 的 lcp（最长公共前缀）完成，设它们的lcp长度为 $k$。

设 $f(i)$ 表示左端点从 $1\sim i$ 的最长上升子序列长度，用贪心的思路进行转移。

则 $f(i) = \max(n-i+1, f(j) + n-i+1-k), j < i$，且保证 $S_{i+k} > S_{j+k}$。

至于两个后缀的lcp可以直接暴力dp得到，这里复杂度也只是 $O(N^2)$。

时间复杂度 $O(N^2)$。

正确代码：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 5000 + 10;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		string s;
		cin >> n >> s;
		vii lcp(n+1, vi(n+1));
		vi dp(n+1);
		for (int i = n-1; i >= 0; i--) {
			for (int j = n-1; j >= 0; j--) {
				if (i == j) lcp[i][j] = n-i;
				else if (s[i] != s[j]) lcp[i][j] = 0;
				else lcp[i][j] = lcp[i+1][j+1] + 1;
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			dp[i] = n-i;
			for (int j = 0; j < i; j++) {
				if (lcp[i][j] < n-i && s[i+lcp[i][j]] > s[j+lcp[i][j]]) {
					dp[i] = max(dp[i], dp[j] + n - i - lcp[i][j]);
				}
			}
			ans = max(ans, dp[i]);
		}
		cout << ans << '\n';
	}
	return 0;
}

尝试后的错误代码，使用SAM求字典序，然后lower_bound求解最长上升子序列：

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 5000 + 10;
struct SAM {
	int tot, last, cnt, mx[N*2], prt[N*2];
	vp rk[N*2];
	map<int, int> ch[N*2];
	SAM() {tot = last = cnt = 1;}
	void clear() {
		for (int i = 1; i <= cnt; i++) {
			mx[i] = prt[i] = 0;
			ch[i].clear();
			rk[i].clear();
		}
		last = cnt = tot = 1;
	}
	void add(int c) {
		int p = last, np = ++cnt;
		last = np;
		mx[np] = mx[p] + 1;
		for (; p && !ch[p][c]; p = prt[p]) ch[p][c] = np;
		if (!p) prt[np] = 1;
		else {
			int q = ch[p][c];
			if (mx[q] == mx[p] + 1) prt[np] = q;
			else {
				int nq = ++cnt;
				mx[nq] = mx[p] + 1;
				prt[nq] = prt[q];
				prt[q] = prt[np] = nq;
				ch[nq] = ch[q];
				//memcpy(ch[nq], ch[q], sizeof(ch[q]));
				for (; ch[p][c] == q; p = prt[p]) ch[p][c] = nq;
			}
		}
	}
	void dfs(int u, int len) {
		rk[u].pb({len, tot++});
		for (auto i : ch[u]) {
			dfs(i.second, len+1);
		}
	}
	void solve() {
		clear();
		int n;
		string s;
		cin >> n >> s;
		for (auto i : s) add(i - 'a');
		dfs(1, 0);
		vi dp;
		for (int i = 1; i <= cnt; i++) sort(rk[i].begin(), rk[i].end());
		for (int i = 0; i < n; i++) {
			int p = 1;
			for (int j = 1; j + i - 1 < n; j++) {
				p = ch[p][s[i+j-1] - 'a'];
				int r = rk[p][j - mx[prt[p]] - 1].second;
				auto it = lower_bound(dp.begin(), dp.end(), r);
				if (it == dp.end()) dp.pb(r);
				else *it = r;
			}
		}
		cout << dp.size() << '\n';
	}
}sam;
signed main(){
#ifdef _DEBUG
	FILE *file = freopen("E.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		sam.solve();
	}
	return 0;
}