Dyd's Blog

He who has a strong enough why can bear almost any how.

ABC257

Posted on Edited on In
Symbols count in article: 5.6k Reading time ≈ 5 mins.

血的教训？

link

由于学校考试隔了两天才来改

result

又是差点掉，我……

res

During

先进去 A 、 B 直接模拟（边打边感觉自己已经被手速快的人甩了老远）， C 排序后扫描一遍即可

看 D $O(n^2)$ 暴力计算两个点间最小的 $S$ 作为距离，然后就算裸的最短路，上 dij 即可，中间挂了两次（边数没开够 + 没开 long long ），但心态还算稳

E 就比 D 简单，直接贪心先取最便宜的保证位数最多，然后尽可能去拿最大的数填高位即可

然后 F ，本来看见图的形态不定吓了一跳，一看不定边都连向同一个点，而且每次起点、终点确定，显然跑两遍最短路（边权为 $1$ bfs 即可）处理每个点到 $1, n$ 的距离，记 $mn_1$ 为不确定的边所有确定的端点中到 $1$ 的最短距离， $mn_n$ 同理，再记不走不确定的边的答案为 $as$ ，那 $i$ 的答案就是 $\min(as, dis(1, i) + mn_n + 1, mn_1 + dis(i, n) + 1)$ ，自信一交 WA 4 个点

当时还有$50min$ 的样子，先瞟了一眼 G 感觉可做但有点麻烦，决定先改 F ，以为是自己最短路打挂了改了半天，直到把 bfs 换成 dij 还是 WA 4 个才确定自己最短路没问题，就想是不是有没考虑到的情况，还剩 $2min$ 的时候突然发现我只讨论了不走不确定的边、走一条不确定的边，还可以走两条不确定的边，就把当前节点当作中转，答案还应该对 $mn_1 + mn_n + 2$ 取 $\min$ ！然后我就手贱 + 脑残把 $+2$ 打成 $+1$ ，直接爆炸，刚想改就结束了

After

F 自然是考完马上就过了，现在从 G 开始搞

G

考场上看了一眼感觉可做，现在看最开始想到的是 SAM 、 AC 自动机一类的东西，但感觉不会考就根据数据范围 $5\ \times 10^5$ 像二分 + 线性判断，但发现答案没有单调性，再考虑外国人的比赛不喜欢卡常，猜正解是线性的，加上和前缀匹配有关，考虑 kmp

判 $-1$ 不必多说，最初我想的是在 kmp 匹配的时候，当它新开一个串（ $j = 0$ ）就让答案 $+1$ ，这显然对，然后当它这个匹配不上 $s[j + 1] \ne t[i]$ 要向前跳的时候也让答案 $+1$ ，设当前 $j$ 跳到了 $k$ ，对应的前缀是 $p \sim k$ 这可以理解为把 $p$ 原来匹配的部分截断，显然前面还是 $s$ 的前缀，然后让 $p \sim k$ 那里做新的一段，一交 WA 14 个点

感觉判 $-1$ 不会错，估计是计算答案的方式错了，随手 hack 了自己：

1
2
aaa
aaaaaaaa

答案显然是 $3$ ，但我的做法会输出 $6$ ，因为每次截断后会把新的 $a$ 放到第 $3$ 个位置导致下一个又匹配不了，但其实把 $a$ 放到第 $1$ 个位置才是最优，也就是说，当有多种截断方案的时候（跳失配指针有多种跳法使 $t[i] == s[j + 1]$ ），我难以判断跳到那里使后面最优

那干脆就从后面开始：直接先记录下匹配，然后从后面开始贪心跳，每次尽可能的远，正确性显然，因为你把前面的串后面的字符去掉并不会导致这个串需要被拆分成更多的前缀

感觉我讲的可能有点不清楚，对照代码理解吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
const int N = 5e5 + 100;
char s[N], t[N];
int sl, tl, ans = 0;
int ne[N], match[N];
int main()
{
	scanf("%s %s", s + 1, t + 1);
	sl = strlen(s + 1), tl = strlen(t + 1);
	ne[1] = 0;
	for (int i = 2, j = 0; i <= sl; ++i)
	{
		while (j && s[i] != s[j + 1]) j = ne[j];
		if (s[i] == s[j + 1]) ++j;
		ne[i] = j;
	}
	for (int i = 1, j = 0; i <= tl; ++i)
	{
		while (j && t[i] != s[j + 1]) j = ne[j];
		if (t[i] == s[j + 1]) ++j;
		else
		{
			puts("-1");
			return 0;
		}
		match[i] = j;
	}
	for (int i = tl; i > 0; i -= match[i]) ++ans;
	printf("%d\n", ans);
	return 0;
}

考场上没打这题血亏（主要还是 F 题我太 sb 了）

EX

先想到的是 dp ，然后发现搞不了，搞了半天过不了样例就去看题解然后——没有！rnm ，退钱！然后机智的打开过了的人的程序，看着好像是个带悔的贪心，但它期望那里算的好奇怪啊

然后仔细一想，我是个 sb ，平方的期望不等于期望的平方，换句话说， $E(x^2) \ne E(x) * E(x)$ ，这就导致 $E((x_1 + x_2 + … + x_n)^2) \ne E(x_1 + x_2 + … x_n)^2$ ，举个栗子，设有两个四面的骰子如表：

表面数字 $E(t)$ $E(t^2)$
$x$ $1, 2, 3, 4$ $\frac{5}{2}$ $\frac{15}{2}$
$y$ $5, 6, 7, 8$ $\frac{13}{2}$ $\frac{87}{2}$

然后你会发现 $E((x + y)^2) = E(x^2) + 2 E(x) E(y) + E(y^2) = \frac{167}{2}$ ，而 $E(x + y)^2 = 81$ ，两者不同

所以我们要把 $E(t), E(t^2)$ 都算出来，为了方便最好不妨设 $x_i = E(t_i)$ ， $y_i = E(t_i^2) - E(t_i)^2 - c_i$ ，那么最后 $(\sum x_k)^2 + \sum y_k$ 就是答案（把第一个平方展开，会发现所有 $E(t_i)^2$ 都抵消了，被换成 $E(t_i^2)$ ，而中间的交叉项不变），为了方便，我们给它们都乘个 $36$ 避免分数

（注意，这下面的 $x, y, t$ 含义变了）这就是一个经典问题：给 $n$ 个物品，每个有权 $x_i$ 和 $y_i$ （可负），从中选 $num$ 个，最大化 $(\sum x_k)^2 + \sum y_k$

考虑函数，设 $f(t) = (\sum x_k)t + \sum y_k = \sum(x_k * t + y_k)$ 注意到当 $t$ 确定后，函数 $f(t)$ 的最优化就是一个贪心取最大的 $num$ 个 $x_k * t + y_k$ ，设这 $num$ 个选择的集合为 $D_t$ ，同时设我们要求的答案集合为 $G, S = \sum_{i \in G} x_i$ ，那么 $f(S) = (\sum_{k \in D_S x_k}) S + \sum_{k \in D_S} y_k$ ，考虑 $D_S, G$ 的最优性，有：
$$
\begin{cases}
(\sum_{k \in D_s} x_k)S + \sum_{k \in D_S} y_k \ge S^2 + \sum_{i \in G} y_i \\
S^2 + \sum_{i \in G} y_i \ge (\sum_{k \in D_s} x_k)^2 + \sum_{k \in D_S} y_k
\end{cases}
$$
此时若 $\sum_{k \in D_s} x_k > S$ ，那有：
$$
\begin{aligned}
(\sum_{k \in D_s} x_k)^2 + \sum_{k \in D_S} y_k > (\sum_{k \in D_s} x_k)S + \sum_{k \in D_S} y_k \ge S^2 + \sum_{i \in G} y_i
\end{aligned}
$$
这显然与 $G$ 的最优性矛盾，而若 $\sum_{k \in D_s} x_k < S$ 那么：
$$
\begin{aligned}
& \begin{cases}
S^2 + \sum_{k \in D_S} y_k > (\sum_{k \in D_s} x_k)S + \sum_{k \in D_S} y_k \ge S^2 + \sum_{i \in G} y_i \\
(\sum_{k \in D_s} x_k)^2 + \sum_{i \in G} y_i > S^2 + \sum_{i \in G} y_i \ge (\sum_{k \in D_s} x_k)^2 + \sum_{k \in D_S} y_k
\end{cases} \\
& \begin{cases}
S^2 + \sum_{k \in D_S} y_k > S^2 + \sum_{i \in G} y_i \\
(\sum_{k \in D_s} x_k)^2 + \sum_{i \in G} y_i > (\sum_{k \in D_s} x_k)^2 + \sum_{k \in D_S} y_k
\end{cases} \\
& \begin{cases}
\sum_{k \in D_S} y_k > \sum_{i \in G} y_i \\
\sum_{i \in G} y_i > \sum_{k \in D_S} y_k
\end{cases}
\end{aligned}
$$
这显然也是矛盾的，故 $\sum_{k \in D_s} x_k == S$ ，带会回可得：
$$
\begin{aligned}
& \begin{cases}
S^2 + \sum_{k \in D_S} y_k \ge S^2 + \sum_{i \in G} y_i \\
S^2 + \sum_{i \in G} y_i \ge S^2 + \sum_{k \in D_S} y_k
\end{cases}\\
& \begin{cases}
\sum_{k \in D_S} y_k \ge \sum_{i \in G} y_i \\
\sum_{i \in G} y_i \ge \sum_{k \in D_S} y_k
\end{cases} \\
& \sum_{i \in G} y_i == \sum_{k \in D_S} y_k
\end{aligned}
$$
综上， $G == D_s$

问题在于 $S$ 我们其实不知道，考虑枚举，设 $S \in [L, R]$ ，我们得到了一个 $O(n(R - L))$ 的算法，由于 $R - L$ 过大，我们必须加速

考虑对于当前 $S$ ，将所有物品按照 $x_k * S + y_k$ 排序，发现随着 $S$ 变大，两个物品的顺序可能会交换，而拐点就是 $x_i * S + y_i = x_j * S + y_j$ 即 $S = \frac{y_j - y_i}{x_i - x_j}$ 的时候这样的拐点只有 $O(n^2)$ 个，把它们都找到，排序后扫描即可，总时间 $O(n^2 \log n)$ ；注意最开始要选 $x$ 和最小的，以及 $x_i == x_j$ 的不管

这个模型有点经典，要记住

代码：

代码中为了方便排序把 $y_i$ 取反了，另外c++14 的 std::tuple 用着好不爽啊， CCF 赶紧搞成 c++17 吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define GT(x, i) std::get<i>(x)
#define Ig std::ignore
#define pb emplace_back
#define fi first
#define se second
using LL = long long;
using std::tie;
const int N = 1000 + 100, P = 998244353, iv36 = 859599304;
int n, num, c[N];
bool top[N];
LL sx, sy, ans;
std::pair<LL, LL> a[N];
std::vector<std::tuple<LL, LL, int, int>> excg;
int main()
{
	scanf("%d %d", &n, &num);
	for (int i = 1; i <= n; ++i) scanf("%d", c + i);
	for (int i = 1, t; i <= n; ++i)
	{
		LL s = 0, s2 = 0;
		for (int j = 1; j <= 6; ++j)
		{
			scanf("%d", &t);
			s += t, s2 += LL(t) * t;
		}
		s2 = s2 * 6 - s * s - c[i] * 36;
		a[i] = {s, -s2}; //为方便排序这里取反
	}
	std::sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j < i; ++j)
			if (a[i].fi > a[j].fi) excg.pb(a[i].fi - a[j].fi, a[i].se - a[j].se, j, i); //注意se取反了
			else if (a[i].fi < a[j].fi) excg.pb(a[j].fi - a[i].fi, a[j].se - a[i].se, i, j);
	std::sort(excg.begin(), excg.end(), [&](auto x, auto y){ return GT(x, 1) * GT(y, 0) < GT(x, 0) * GT(y, 1); });
	sx = sy = 0;
	for (int i = 1; i <= num; ++i)
	{
		top[i] = true;
		sx += a[i].fi, sy -= a[i].se; //注意se取反了
	}
	ans = sx * sx + sy;
	for (auto it : excg)
	{
		int i, j;
		tie(Ig, Ig, i, j) = it;
		if (!top[i] || top[j]) continue;
		top[i] = false, top[j] = true;
		sx += a[j].fi - a[i].fi;
		sy += a[i].se - a[j].se; //注意se取反了
		ans = std::max(ans, sx * sx + sy);
	}
	ans = (ans % P + P) % P * iv36 % P;
	printf("%lld\n", ans);
	return 0;
}