AtCoder Beginner Contest 215
AtCoder Beginner Contest 215
菜的本质暴露的一览无余（
一场 ABC 一场 ARC 排名都 1k+，直接掉了 200 多分 QwQ
H 是比较神仙的数数题，所以锅了。
\(A\sim D\)
\(A\sim C\) 就简单模拟，\(D\) 简单筛一下。
\(E\)
给定字符串序列，只包含前 \(10\) 个大写字母 \(A\sim J\)，求合法的子序列个数。
一个子序列是合法的，当且仅当它当中的相同字符都是连续的，例如
AABCD合法，但ABCDA不合法。
真·考场降智，认为 \(2^{10}\) 超级大，根本不可能状压/fad
显然就简单状压 DP，设 \(f(i,S,x)\) 表示 \(1\sim i\) 中，出现过的字符集合为 \(S\)，最后一个字符为 \(x\) 的子序列个数。
简单转移即可。
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 1010;
const LL MOD = 998244353;
int n; char str[N];
LL f[N][1 << 10][10];
void P(LL &x, LL y) {x = (x + y) % MOD;}
int main() {
scanf("%d %s", &n, str + 1);
for(int i = 1; i <= n; i ++) {
int c = str[i] - 'A';
for(int s = 0; s < (1 << 10); s ++)
for(int t = 0; t < 10; t ++) if(f[i - 1][s][t]) {
P(f[i][s][t], f[i - 1][s][t]);
if(!(s >> c & 1) || (t == c))
P(f[i][s | (1 << c)][c], f[i - 1][s][t]);
}
P(f[i][1 << c][c], 1);
}
LL ans = 0;
for(int s = 0; s < (1 << 10); s ++)
for(int t = 0; t < 10; t ++) P(ans, f[n][s][t]);
printf("%lld\n", ans);
return 0;
}
\(F\)
求平面最远点对，其中两点 \((x_1,y_1),(x_2,y_2)\) 距离定义为 \(\min(|x_1-x_2|,|y_1-y_2|)\)。
因为没想出来 E 所以比赛后期思维挺乱的，跳到这道题之后一直想着分治做法。
实际上是简单的二分答案，将点按 \(x\) 升序排序，然后双指针扫描一遍。
得到里当前点 \(x\) 的差距最小的，\(x\) 维上的距离 \(\geq mid\) 的点，预处理一个 \(y\) 的后缀 \(\min,\max\) 即可简单判断。
#include
#include
#include
using namespace std;
const int N = 2e5 + 10;
int n, Mx[N], Mn[N];
struct Node{int x, y;} a[N];
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
bool cmp(Node a, Node b) {return a.x < b.x;}
int Abs(int x) {return x < 0 ? - x : x;}
bool Chck(int mid) {
int r = 1;
for(int l = 1; l <= n; l ++) {
while(r <= n && a[r].x - a[l].x < mid) r ++;
if(r > n) return false;
if(r <= n) {
if(Abs(a[l].y - Mx[r]) >= mid) return true;
if(Abs(a[l].y - Mn[r]) >= mid) return true;
}
}
return false;
}
int main() {
n = read();
for(int i = 1; i <= n; i ++) a[i].x = read(), a[i].y = read();
sort(a + 1, a + n + 1, cmp);
Mx[n] = Mn[n] = a[n].y;
for(int i = n - 1; i >= 1; i --)
Mx[i] = max(Mx[i + 1], a[i].y),
Mn[i] = min(Mn[i + 1], a[i].y);
int L = 0, R = Mx[1] - Mn[1];
while(L < R) {
int mid = (L + R + 1) >> 1;
if(Chck(mid)) L = mid; else R = mid - 1;
}
printf("%d\n", L);
return 0;
}
\(G\)
给定长度为 \(N\) 的序列，每个点有颜色 \(c_i\)，对于每个 \(1\leq K\leq N\)，求随机选出 \(K\) 个点的期望不同颜色个数。
根据期望的线性性质，可以将问题变为每种颜色选或不选，形式化一点：
设 \(X(i)\) 表示是否出现了颜色 \(i\)，出现了为 \(1\) 否则为 \(0\)。
\[Ans=E(\sum\limits_{i=1}^c X(i))=\sum\limits_{i=1}^cE(X(i)) \]每个 \(E(X(i))\) 相当于颜色 \(i\) 在随机选的 \(K\) 个点中至少出现一次的概率，设颜色 \(i\) 的出现次数为 \(n_i\)，那么：
\[E(X(i))=(\binom{N}{K}-\binom{N-n_i}{K})/\binom{N}{K} \]那么每次的就有：
\[Ans=\frac{\sum\limits_{i=1}^c (\binom{N}{K}-\binom{N-n_i}{K})}{\binom{N}{K}} \]对于每个 \(K\)，都需要 \(O(c)\) 的时间计算，时间复杂度最劣为 \(O(n^2)\)。
继续分析性质，不难发现 \(\sum\) 里的值在 \(K\) 确定的情况下，只和 \(n_i\) 的值有关。
那么考虑将 \(n_i\) 相等的颜色缩为同种颜色，同时计算，设最后剩下 \(C\) 种颜色，第 \(i\) 种颜色都由原本的 \(a_i\) 种缩成。
那么有：
\[Ans=\frac{\sum\limits_{i=1}^C a_i(\binom{N}{K}-\binom{N-n_i}{K})}{\binom{N}{K}} \]这个看上去没啥用，但是严谨分析一下 \(C\) 的数量级别。
对于 \(n_i>\sqrt N\) 的颜色，显然至多有 \(\sqrt N\) 种，否则总个数就 \(>N\) 了，显然不可能。
对于 \(n_i\leq \sqrt N\) 的颜色，至多也就 \(0\sim \sqrt N\) 这么多种。
故总个数不可能超过 \(2\sqrt N\)，而且远小于这个上界，故总时间复杂度 \(O(N\sqrt N)\)。
小插曲：有人在 AtCoder 上发布了 \(O(n\log n)\) 的 Poly 做法，把标算爆了，但是看不懂。
#include
#include
#include
#include