AtCoder Beginner Contest 215 - ABC215

AtCoder Beginner Contest 215

E - Chain Contestant

题意

给出一个由 $10$ 种大写字母 $A\sim J$ 组成的字符串 $S$，长度为 $N$，求 $S$ 有多少个下标序列满足下列条件：

令下标序列所对应的 $S$ 的子序列为 $T$，满足同一种字母在 $T$ 中都是连续出现的，如：AAABBCCC 满足条件，但 AABBACCC 就不满足条件，因为字母 A 不连续。

数据范围：$N\leqslant 1000$

思路

看到字母的类型只有10种，而且每一个状态下要保证之前没有出现过该数字，所以可以用dp的一维保存之前出现过的数字，由于最后一位是可以连续的，所以dp还有一维存储最后一位的数字。

先将字母对应成数字 $0\sim9$。

设 $f(i, j, U)$，表示前 $i$ 个字符组成的子序列中，最后一位为 $j$，且使用子序列中包含了集合 $U$ 中的数字。

设 $S_i=x$，则有如下转移：

• $f(i, j, U) = f(i-1, j, U)$ 代表第 $i$ 位不取。

• $f(i, x, U) += f(i-1, x, U)$ 代表取第 $i$ 位，且是上一位取值也是 $x$。

• $f(i, x, V\cup\{x\}) += f(i-1, j, V), (x\not\in V)$ 代表取第 $i$ 位，且是第一次取 $x$。

• $f(i, x, \{x\}) += 1$ 代表只取第 $i$ 位。

则，$\displaystyle \text{ANS} = \sum_{\forall j, U} f(N, j, U)$。

总复杂度 $O(10\times2^{10}\times N)$。

由于dp的第一维可以滚掉，所以就少开了一维。

点击显/隐代码

#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 = 1e3 + 10;
int f[10][1<<10], tmp[10][1<<10];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 0; i < n; i++) {
		int x = s[i] - 'A';
		memcpy(tmp, f, sizeof(f));
		for (int k = 0; k < (1<<10); k++) {
			f[x][k] = (f[x][k] + tmp[x][k]) % P;
			if ((k >> x & 1) == 0) {
				for (int j = 0; j < 10; j++) {
					f[x][k | (1<<x)] = (f[x][k | (1<<x)] + tmp[j][k]) % P;
				}
			}
		}
		f[x][1<<x] = (f[x][1<<x] + 1) % P;
	}
	int ans = 0;
	for (int j = 0; j < 10; j++) {
		for (int k = 0; k < (1<<10); k++) {
			ans = (ans + f[j][k]) % P;
		}
	}
	cout << ans << '\n';
	return 0;
}

F - Dist Max 2

题意

给出 $N$ 个二维坐标 $(x_i, y_i)$，定义两个点 $i, j$ 的距离为 $\min(|x_i-x_j|, |y_i-y_j|)$。

（切比雪夫距离是取 $\max$）

找到这 $N$ 个点中两个点的距离的最大值。

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

思路

求最大化最小值，考虑二分答案的方法，由于每个点有 $x, y$ 两个参数，故可以先对 $x$ 从小到大排序。

设答案为 $M$，则一定存在 $i > j$ 使得，$x_i-x_j \geqslant M$ 并且 $|y_i-y_j| \geqslant M$，

由于当前 $x$ 有序，则可以从小到大顺次枚举，对于当前枚举到的 $i$，如果 $j$ 满足 $x_i-x_j\geqslant M$，则有 $\forall k \leqslant j, x_i-x_k\geqslant M$，故 $1\sim j$ 这些元素的 $x$ 值都已经满足条件，只需找到满足条件的 $y$ 值，由于满足条件的值一定是边界值，也就是最大或最小值，于是再维护 $1\sim j$ 对应 $y$ 坐标的最大值和最小值，最终判断是否有满足条件的 $y$ 值即可。

总复杂度 $O(NlogN)$。

点击显/隐代码

#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 << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	int n;
	scanf("%d", &n);
	vp a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i].first, &a[i].second);
	}
	sort(a.begin(), a.end());
	int l = 0, r = 1e9;
	while (l <= r) {
		int mid = (l + r) >> 1;
		int fg = 0, mx = 0, mn = 1e9;
		queue<pii> q;
		for (auto p : a) {
			while (!q.empty()) {
				if (p.first - q.front().first < mid) break;
				mx = max(mx, q.front().second);
				mn = min(mn, q.front().second);
				q.pop();
			}
			if (p.second - mn >= mid || mx - p.second >= mid) {
				fg = 1;
				break;
			}
			q.push(p);
		}
		if (fg) l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n", r);
	return 0;
}