本文章由 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}$，由单调性得证。

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

有的题，横坐标和所切的斜率均不单调，比如 P4655 Building Bridges，这时候我们可以用 CDQ 分治来把朴素的 $O(n^2)$ 优化到 $O(n\log n)$。

具体方法比较简单。CDQ 分治所考虑的核心就是左区间对右区间的贡献。怎么转化成为朴素的斜率优化 DP 呢？左边区间的横坐标要单调，右边区间所切的斜率要单调。

这样，我们就先按照切的斜率排序，然后计算左边对右边的贡献，然后按照横坐标排序。

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

首先奇耻大辱。赛时以为 Unrated 就不要紧，帮人调码交了两发，然后棕了。确实该罚，以后牢记。

然后来看题。

先不管操作一二。对于操作三，要求我们把所有糖果分成 $k$ 份，所要统计的是重复出现的糖果的数量，别的没有要求。

如果每人每种糖果先分一颗，这时候每种糖果数量减去 $k$，接下来还没分完的糖果每颗都会带来 $1$ 的贡献。

换句话说，我们就是对于每次询问的 $k$，统计每种糖果超出 $k$ 部分的总和。也就是说，大于 $k$ 的数的总和，减去大于 $k$ 的数的数量乘上 $k$ 就是答案。

这个操作用什么可以完成？平衡树，树状数组，权值线段树都可以做到。赛时无脑上了平衡树，但是实际上因为值域很小，所以后两者不需要离散化就可以。

总的来说，我们的做法就是：用桶维护每种糖果的数量，然后用上面三种数据结构之一维护；加减可以先删再插入，查询就查大于某数的数的和以及数量。

这里是代码。

平衡树有几个点注意：

• 需要加哨兵，否则需要注意边界情况；

• 查大于某数的数的数量，可以找后继然后用根减去左子树。