本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 14:55:27

我非常喜欢的组合题。

首先我们把贡献式化简：

$$ \begin{aligned} (\sum |A_i - B_i|)^2 &= (\sum (\max - \min))^2 \ &= (\sum(\max + \min) - 2\sum\min)^2 \ &= (2m - 2\sum\min)^2 \end{aligned} $$

这个式子拆出来之后，贡献式就变得只跟 $\min$ 有关了。我们设 $s = \sum\min$，那么一个 $s$ 的贡献就是 $(2m - 2s)^2$

于是我们现在就只需要知道一个 $s$ 对应了多少个 $A$ 与 $B$ 序列。

首先，$\min$ 的选法是可知的，是 $n + s - 1\choose s$，也就是插板。

这个时候我们已经从这两个序列中选完 $n$ 个位置了。考虑剩下 $n$ 个位置的选法。

剩下 $n$ 个数的总和是 $m - s$，并且我们选的每个数不能小于对应位置所选的最小值。

但是我们并不知道，也不能知道每个位置上选的最小值。

我们考虑枚举有 $x$ 个位置上，$A_i$ 取的是最小值，这里有一个 $n\choose x$，现在考虑对应的 $B_i$ 的方案，因为这里 $A_i$ 的方案已经在前面算过了。

由于这些 $B_i$ 至少选到最小值，我们就把最小值先选上，然后剩下 $m - s$ 分配给 $x$ 个数可空，方案数是 $x + m - s + 1\choose m - s$。

剩下的 $n - x$ 个位置，同理，$A_i$ 选不为最小值的任意数，且和为 $m - s$，方案数是显然的 $m - s - 1 \choose n - x - 1$。

最后的式子是

$$ \sum\limits_{s=0}^m \sum\limits_{x=0}^n \bigg({{n \choose x}{n+s-1\choose s}{x + m - s - 1\choose m - s}{m - s - 1 \choose n -x - 1}{(2m - 2s)^2}}\bigg) $$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 12:40:43

本题即求最大的独立点集。

如果设关系为两点是否可达，然后做一遍传递闭包，我们就把原问题转化为了图的最大反链。

最大反链就是说，在这条链上的所有点，都不满足这一偏序关系。我们统计最大反链的数量就是第一问的答案。

这怎么做？根据 Dilworth 定理，最大反链等于最小链覆盖，后者是经典题。匈牙利或者 Dinic 都好，前者好写。

然后看第二问，也就是构造一组解。

最开始感觉这问挺水的，好像很好构造，但是实际上比第三问麻烦。

我们先第一问匹配出来，然后从右边的非匹配点开始 DFS，右点只走非匹配边，左点只走匹配边，我们就可以知道哪些点被 DFS 到。

取集合 $S$ 代表左边被访问到与右边没有访问到的点的并，那么 $S$ 是一个最小点覆盖，它的补集就是最大独立集。

为啥？

点覆盖指的就是使得每条边的两个端点至少有一个被覆盖的点的集合。根据我们上面的构造方法，右边选取的点一定是匹配点。而如果一个右边的匹配点没有被选入，其一定是由左边某个匹配点访问到了，否则就产生了一条增广路，就不是最大匹配了。因此，一条边要么被左边点选中，要么被右边点选中。

根据这样，我们取 $S$ 的补集就能得到构造方案。

第三问要求我们判断一个点是否可能在最大独立集中。强制选择这个点，删除与它有关的所有点，然后再跑一遍就可以了。

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

明显最小环一定是简单环，那么如果枚举 $(u, v)$，跑不包含此边的最短路计数，那么 $(u, v)$ 构成的简单环的大小便是 $\rho (v) + 1$，数量就是最短路数量。

但这样会重，于是要除以环大小。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-18 10:33:04

看了一圈题解区只有我用了暴力展开 /jy

实际上并不难，还有点水，也不难调。

相信各位应当都会中缀表达式的计算：我们维护一个符号栈和一个数据栈，然后分类讨论根据优先级计算即可。这一点不管是别的题目还是题解区已经讲的很好了，OI Wiki 上的讲解也不错。

这篇题解的重点是把普通整数上的操作扩展到多项式。

由于只有一个字母，我们可以维护系数向量 $v$，其中 $v_k$ 代表 $a^k$ 的系数，常数就是 $a^0$ 的系数。于是，我们就可以用 $O(k)$ 时间做到加减操作。

然后考虑乘和乘方。先考虑朴素的 $O(n^2)$ 乘法。（通过手工模拟可得），代码为：

for (int i = 0; i < K; i++)
  	for (int j = 0; i + j < K; j++) 
      	r.k[i + j] += k[i] * x.k[j];

如果要求更高的速度，可以用 FFT 优化。但是本题数据范围比较小，所以不用。

乘方可以用经典的快速幂，复杂度是 $O(k^2\log n)$ 的，或者是 $O(k \log^2 n)$（FFT 优化）。

接下来就是代码时间了，其实思路是非常好想的。

但是有几点注意：

• 数据换行符含有 \r，不能简单地用 getline

• 最后一个点卡爆 long long，所以需要对这个多项式取模（所以不妨用 NTT）

• 括号可能不匹配 遇到这种情况，应该直接丢掉多余的括号

接下来放看起来还是很不错的代码：

#include <iostream>
#include <stack>
#include <cstring>
#define siz(x) static_cast<int> ((x).size ())
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 30, K = 500, P = 998244353;

class poly {
public:
	int k[K];
	
	poly () { memset (k, 0, sizeof k); }
	poly (const poly &x) { memcpy (k, x.k, sizeof k); }
	poly &operator = (const poly &x) { memcpy (k, x.k, sizeof k); return *this; }
	poly (int x, bool flag = false) { memset (k, 0, sizeof k), k[flag] = x; }
	poly operator + (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) r.k[i] = (k[i] + x.k[i]) % P;
		return r;
	}
	
	poly operator - (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) r.k[i] = (k[i] + P - x.k[i]) % P;
		return r;
	}
	
	poly operator * (const poly &x) {
		poly r;
		for (int i = 0; i < K; i++) for (int j = 0; i + j < K; j++) (r.k[i + j] += k[i] * x.k[j] % P) %= P;
		return r;
	}
	
	poly operator ^ (int x) {
		poly r = *this, p = *this;
		--x;
		while (x) {
			if (x & 1) r = r * p;
			x >>= 1, p = p * p;
		}
		return r;
	}
	
	bool operator == (const poly &x) {
		for (int i = 0; i < K; i++) if (k[i] != x.k[i]) return false;
		return true;
	}
	
	friend ostream &operator << (ostream &out, const poly &x) {
		for (int i = K - 1; i >= 2; i--) if (x.k[i]) {
			if (x.k[i] == 1) out << "a^" << i << " + ";
			else if (x.k[i] == -1) out << "-a^" << i << " + ";
			else out << x.k[i] << "a^" << i << " + ";
		}
		if (x.k[1] == 1) out << "a + ";
		else if (x.k[1] == -1) out << "-a + ";
		else if (x.k[1]) out << x.k[1] << "a + ";
		out << x.k[0];
		return out;
	}
};


stack<char> op;
stack<poly> q;

void ins (char c)
{
	poly y, x;
	
	if (c == '(') return;
	if (q.empty ()) cout << "fuck off", exit (0);
	y = q.top (), q.pop ();
	if (q.empty ()) cout << "fuck off", exit (0);
	x = q.top (), q.pop ();
	switch (c) {
	case '+': q.push (x + y); break;
	case '-': q.push (x - y); break;
	case '*': q.push (x * y); break;
	case '^': q.push (x ^ y.k[0]); break;
	default: break;
	}
}

int prio (char c)
{
	switch (c) {
	case '(': return 0;
	case '+': case '-': return 1;
	case '*': return 2;
	case '^': return 3;
	default: return -1;
	}
}

bool space (char c) { return c == ' ' || c == '\n' || c == '\r'; }

poly expand (void)
{
	int level = 0;
	char c;

	while (!q.empty ()) q.pop ();
	while (space (c = getchar ()));
	do {
		if (isdigit (c)) {
			int x = 0;
			do x = (x * 10 % P + c - '0') % P; while (isdigit (c = getchar ()));
			while (space (c) && c != '\n') c = getchar ();
			q.push (poly (x));
			if (c == '\n') break;
			else continue;
		}
		
		switch (c) {
		case 'a': q.push (poly (1, true)); break;
		case '(': op.push ('('), level++; break;
		case ')':
			if (--level < 0) break;
			while (!op.empty () && op.top () != '(') ins (op.top ()), op.pop ();
			op.pop (); break;
		default:
			while (!op.empty () && prio (op.top ()) >= prio (c)) ins (op.top ()), op.pop ();
			op.push (c); break;
		}
		while (space (c = getchar ()) && c != '\n');
	} while (c != '\n');
	
	while (!op.empty ()) ins (op.top ()), op.pop ();
	return q.top ();
}

int read (void)
{
	int res = 0;
	char c;
	while (!isdigit (c = getchar ()));
	do res = res * 10 + c - '0'; while (isdigit (c = getchar ()));
	return res;
}

signed main (void)
{
	int n;
	poly res;
	
	res = expand ();
	n = read ();
	
	for (int i = 1; i <= n; i++) if (expand () == res) putchar ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"[i - 1]);
	putchar ('\n');
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-18 15:45:19

Lisp 语言语法很简单：

• (function arg1 arg2)，表示以参数 arg1、arg2 等等调用函数 function；例如：(+ 1 2)，(write (+ 2 3))；

• (if cond body alter)，是判断语句，当 cond 不为零时执行 body，否则执行 alter。

• (lambda args body)，生成一个闭包，也就是通常说的函数，args 是参数，body 是语句。例如，(lambda (x y) (+ x y))，(lambda (x y) (lambda (t) (if (= t 0) x y)))

这两种语法都是递归的，也就是说你可以随便嵌套。

可调用对象分两种：语言内置的与闭包。语言内置的，比如 +, read, write；闭包是自己定义的。

语法看起来很简陋，甚至连定义变量都好像做不到，但实际并不是这样。定义变量可以用 lambda 实现：

((lambda (x) (+ x 1)) 1) => 2，相当于 x = 1, x + 1

((lambda (x y) (+ x y)) 2 3)，相当于 x = 2, y = 3, x + y

我们还可以利用闭包做到一些神奇的东西，比如构造链表：

((lambda (cons car cdr) (write (cdr (cons 1 2))))
(lambda (x y) (lambda (t) (if (= t 0) x y)))
(lambda (x) (x 0))
(lambda (x) (x 1)))

这类似于 C++ 中的：

pair cons (int x, int y)
{
	int helper (int t) { return t ? y : x; }
	return helper;
}

int car (pair x) { return x (0); }
int cdr (pair x) { return x (1); }

牛逼炸了。

还能递归，例如求阶乘：

(write ((lambda (this n) (if (= n 0) 1 (* n (this this (- n 1))))) (lambda (this2 n2) (if (= n2 0) 1 (* n2 (this2 this2 (- n2 1))))) (read)))

解释器

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

斜率优化可以优化这样的柿子：

$$f(i) = \max\limits_j f(j) - a_i a_j + b_j$$

在 $i$ 转移时，若 $j < k$ 比 $k$ 优，那么

$$ \begin{aligned} & f(j) - a_ia_j + b_j \gt f(k)-a_ia_k+b_k \ & f(j) + b_j - f(k) - b_k \gt a_i(a_j - a_k) \ & \dfrac{f(j) + b_j - f(k) - b_k}{a_j-a_k} \gt a_i \end{aligned} $$

我们将 $(a_j, f(j) + b_j)$ 看作是一个点，那么就相当于这当直线 $P_jP_k$ 的斜率大于 $a_i$ 时，$j$ 比 $k$ 优。

这也就是一个下凸壳。我们用单调队列就可以维护。

注意到如果 $a_i$ 单增，我们所切的斜率就单增，那么转移就可以做到均摊 $O(1)$。

如果要求的是最小值，那么当斜率小于 $a_i$ 时 $j$ 更优，于是我们就维护一个下凸壳，斜率是单调递减的，于是我们就要保证切的时候斜率也单调递减。

例题 P3648 [APIO2014] 序列分割

转移是显然的

$$ \begin{aligned} f(i, j) &= \max_{k=0}^{i-1} f(k, j - 1) +\sigma_{k} (\sigma_i - \sigma_k) \ & = \max f(k, j - 1) - \sigma_k^2 + \sigma_k\sigma_i \end{aligned} $$

这个转移是 $O(n)$ 的。我们考虑怎么优化。

首先滚动掉第二维然后考虑。

$\sigma$ 是非负序列的前缀和，其单增显然。于是我们可以按照上面的方式，设 $P_j(-\sigma_k, f(k) - \sigma_k^2)$。

每次用 $\sigma_i$ 去切即可。

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

我们有一个基本转移。设 $f(i, j)$ 代表前 $i$ 个数，分了 $j$ 组的最小权值，那么

$$f(i, j) = \min_{0\le k\lt i} f(k, j - 1) + (i - k) \times \max\limits_{l=k+1}^i a_l$$

这个 $\max$ 相当唐，我们用普通的想法很难把它去掉。

考虑跑 $k$ 轮分治，用类似 CDQ 的思想，以左区间去贡献右区间。

怎么合并？分治后，柿子里头的 $\max$ 就变成了一个前后缀最大值的 $\max$。

我们设 $\text{mid}$ 前的后缀最大值为 $p$，其后面的前缀最大值为 $q$，那么 $p$ 显然单不增，$q$ 单不减。

我们可以简单分一下桃子

• $q_i \ge p_j$

$$ \begin{aligned} f(i) &= g(j) + (i-j)q_i \ &= g(j) - q_ij + iq_i \end{aligned} $$

斜率优化显然，决策点是 $(j, g(j))$。为了快速维护 $q_i \ge p_j$ 的性质，我们用双指针（这也是 CDQ 标配），$i$ 从左向右，而 $j$ 从右向左，逐渐加入决策点并维护凸包性质。加入的斜率是单调递减的，于是成为一个上凸壳。我们要在这个上凸壳上找最小值，就要求每次头的斜率小于切的斜，发现

我们加入直线的顺序是单调递减的，那么

然后以均摊 $O(1)$ 复杂度更新 $f(i)$。

• $q_i \lt p_j$

$$ \begin{aligned} f(i) &= g(j) + (i - j) p_j \ &= g(j) + ip_j - jp_j \end{aligned} $$

决策点是 $(p_j, g(j) - jp_j)$，切的

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-22 19:57:53

有一个东西：

$$ \begin{aligned} E(x) &= \sum\limits_{i=1}^V\sum\limits_{j=1}^V \dfrac {\lvert j - i + 1\rvert} {V^2}\ &= \sum\limits_{i=1}^V\bigg(\sum\limits_{j=i}^V \dfrac{j - i + 1}{V^2} + \sum\limits_{j=1}^{i-1}\dfrac{i-j+1}{V^2}\bigg)\ &=\sum\limits_{i=1}^V \dfrac 1{V^2}\bigg(\sum\limits_{j=1}^{V - i + 1} 1 + \sum\limits_{j=2}^i 1\bigg) \ &=\dfrac{1}{V^2} \sum\limits_{i=1}^V\bigg(\dfrac 1 2 (V-i+2)(V-i+1) + \dfrac{1}{2} (i+2)(i - 1)\bigg)\

\end{aligned} $$

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

AB 是唐题，C 也是唐题，但是找规律找挂了。

写挂 C 心态有点挂，然后 DE 全调挂了，赛后发现做法都对。我不好说。

D

简单状压，设 $f(i, j)$ 为前 $i$ 个字符，最后 $k$ 个字符状态为 $j$ 的方案数，然后随便转移就行了，但是我没调出来。

E

单调栈。

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

四边形不等式

$$a \le b \le c \le d, w(a, c) + w(b, d) \le w(a, d) + w(b, c)$$

即，交叉小于包含。

如果有方程

$$f(i) = \min\limits_{1\le j \lt i} w(j, i)$$

设在 $i$ 点的决策点为 $q(i)$，要证 $j \lt i, q(j) \le q(i)$

设有 $c \lt d$，但 $q(c) = b \gt q(d) = a$，那么首先有

$$a \lt b \le c \lt d$$

于是由最优

$$w(a, c) \gt w(b, c), w(b, d) \gt w(a, d)$$

两式相加得

$$w(a, c) + w(b, d) \gt w(a, d) + w(b, c)$$

但是这与四边形不等式矛盾。

简单证明 P3195 玩具装箱有决策单调性

$$w(i, j) = (s_i - s_j - L)^2 = O((s_i - s_j)^2)$$

其中 $s_i$ 是单调增的，那么对 $i \lt j$，有

$$w(i, j - 1) + w(i + 1, j) \lt w(i, j) + w(i + 1, j - 1)$$

也即

$$(s_i-s_{j-1})^2 + (s_{i+1}-s_j)^2 \lt (s_i - s_j)^2 + (s_{i+1}-s_{j-1})^2$$

$$(s_i-s_{j-1}+s_i - s_j)(s_i-s_{j-1}-s_i+s_j) \lt (s_{i+1}-s_{j-1}+s_{i+1}-s_j)(s_{i+1}-s_{j-1}-s_{i+1}+s_j)$$

$$(2s_i - s_j - s_{j-1})(s_j - s_{j-1}) \lt (2s_{i+1}-s_j - s_{j-1})(s_j - s_{j-1})$$

由于 $s_j - s_{j-1} \gt 0$，那么

$$2s_i - s_j - s_{j-1}\lt s_{i+1}-s_j - s_{j-1}$$

也就是 $s_i \lt s_{i+1}$，由单调性得证。