题解 |蒟蒻来补题了QAQ

A 我要学三角形

容易发现最小的三角形的周长为 $2 + 3 + 4 = 9$ ，因此 $n\leq 8$ 时一定无解。当 $n > 8$ 时，题目要求的可以等价为 $2 * (c - a)$ 的最大值，即让 $c$ 尽可能的大，让 $a$ 尽可能的小。为了保证两边之和大于第三边，那么 $c$ 最大为 $n/2-(n \% 2==0)$ ；而为了让 $a$ 尽可能小，则让 $b$ 取 $c - 1$ ，剩下的分给 $a$ 。注意还要判断此时是否满足 $a < b$ 。

void solve() {
	ll n;
	cin >> n;
	if (n <= 8) {
		cout << 0 << endl;
		return;
	}
	ll c = n / 2 - (n % 2 == 0);
	ll b = c - 1;
	ll a = n - c - b;
	if (a >= b) {
		cout << 0 << endl;
		return;
	}
	cout << 2ll * (c - a) << endl;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return (0 ^ 0);
}

B 拯救DAG王国

对于 $D A G$ ，我们考虑拓扑排序，拓扑排序有个性质：拓扑排序中任意时刻在队列里的点不能相互到达。

对于点 $u$ ，记 $t a g [u]$ 为点 $u$ 能到达的点和能到达点 $u$ 的点数之和，则对于 $A$ 类城市， $t a g [u] = n - 1$ ，对于 $B$ 类城市， $t a g [u] = n - 2$ 。

利用上述性质，我们可以求出可能是目标城市的 $t a g [u]$ ，最后判断即可。

若存在 $A$ 类城市 $u$ ，则一定存在某一时刻，队列中只有点 $u$ ，此时还没有遍历到的点就是点 $u$ 能到达的点， $t a g [u] + = n u m$ 。

若存在 $B$ 类城市 $u$ ，则一定存在某一时刻，队列中有 $u$ 和 $v$ 两个点， $u$ 和 $v$ 不能互相到达，若存在 $v\rightarrow z$ ， $z$ 的入度为 $1$ ，则 $u$ 不能到 $z$ ， $u$ 一定不是 $B$ 类城市。

而能到达点 $u$ 的城市，只需反向建图，然后进行和上述一样的操作即可。

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> mp(n + 1), ms(n + 1);
	vector<int> d(n + 1), g(n + 1);
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		mp[u].push_back(v);
		ms[v].push_back(u);
		d[v]++, g[u]++;
	}
	queue<int> q;
	vector<int> tag(n + 1);
	int num = n;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			q.push(i);
			num--;
		}
	}
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
		if (q.size() == 0)
			tag[t] += num;
		else if (q.size() == 1) {
			int p = q.front();
			bool flag = 1;
			for (auto& v : mp[p]) {
				if (d[v] == 1) {
					flag = 0;
					break;
				}
			}
			tag[t] += flag * num;
		}
		for (auto& v : mp[t]) {
			if (--d[v] == 0) {
				num--;
				q.push(v);
			}
		}
	}

	num = n;
	for (int i = 1; i <= n; i++) {
		if (!g[i]) {
			q.push(i);
			num--;
		}
	}
	while (!q.empty()) {
		auto t = q.front();
		q.pop();
		if (q.size() == 0)
			tag[t] += num;
		else if (q.size() == 1) {
			int p = q.front();
			bool flag = 1;
			for (auto& v : ms[p]) {
				if (g[v] == 1) {
					flag = 0;
					break;
				}
			}
			tag[t] += flag * num;
		}
		for (auto& v : ms[t]) {
			if (--g[v] == 0) {
				q.push(v);
				num--;
			}
		}
	}
	cout << count_if(tag.begin() + 1, tag.end(), [&](int x) {
		return x >= n - 2;
	}) << endl;

	return (0 ^ 0);
}

C 和生蚝一起做算数吧

一看数据范围，肯定是 $l o g (n)$ 的复杂度，因此从二进制的角度考虑这道题。

为了方便起见，可以将 $x * 2$ ，等价于 $y / 2$ ，代价为 $b+(y\&1)*a$

为了减少 $x + 1$ 的操作数，则该操作要在最后阶段进行

若 $x > y$ ，只能进行 $x / 2$

若 $x < y$ ，可以直接将 $x$ 加到 $y$ ，或 $y / 2$ 继续递归，取 $m i n$

若 $x = = y$ ，递归结束。

注意 $10^{18}*10^{9}$ 会爆 $long\ long$ ，这里我使用了 $\_\_int128\_t$

时间复杂度 $O (l o g N)$

using i128 = __int128_t;
istream& operator>>(istream& is, i128& n) {
	n = 0;
	string s;
	is >> s;
	for (auto c : s) {
		n = 10 * n + c - '0';
	}
	return is;
}
ostream& operator<<(ostream& os, i128 n) {
	if (n == 0) {
		return os << 0;
	}
	string s;
	while (n > 0) {
		s += '0' + n % 10;
		n /= 10;
	}
	reverse(s.begin(), s.end());
	return os << s;
}
i128 a, b, c;
i128 dfs(i128 x, i128 y) {
	if (x == y)
		return 0;
	else if (x > y)
		return dfs(x >> 1, y) + c;
	else
		return min((y - x) * a, dfs(x, y >> 1) + b + (y & 1) * a);
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		i128 x, y;
		cin >> x >> y >> a >> b >> c;
		cout << dfs(x, y) << endl;
	}

	return (0 ^ 0);
}

D 野兽追猎者塔维什

简单版本， $n$ 一定是 $3$ 的倍数，则三种动物的期望数量都为 $n / 3$ ，总血量期望值为 $n / 3 * 10$ ，期望总攻击力为 $n / 3 * 10 + n / 3 * (n - 1)$

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		ll n;
		cin >> n;
		cout << n / 3 * 10 + n / 3 * (n - 1) << ' ' << n / 3 * 10 << endl;
	}

	return (0 ^ 0);
}

E 野兽追猎者塔维什plus

总血量期望值不变，仍然为 $n / 3 * 10$ 。

设雷欧克出现 $x$ 次，则期望总攻击力为 $n/3*10+(n-1)E(xf(x))\ =\ n/3*10+(n-1)\sum_{k=0}^{9}a_{k}\sum_{i=0}^{n}C_{n}^{i}p^{i}(1-p)^{n-i}i^{k+1}$

前面是基础攻击力，后面是 $x$ 个雷欧克，每个给其他 $n - 1$ 个动物增加 $f (x)$ 的攻击力，枚举 $x$ 的值，乘上相应概率即为期望。

constexpr int N = 1e5 + 10, mod = 1e9 + 7;
ll fact[N], infact[N];
ll qmi(ll a, ll k) {
	ll res = 1;
	while (k) {
		if (k & 1)
			res = res * a % mod;
		a = a * a % mod;
		k >>= 1;
	}
	return res;
}
void init() {
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; i++)
		fact[i] = fact[i - 1] * i % mod;
	infact[N - 1] = qmi(fact[N - 1], mod - 2);
	for (int i = N - 2; i >= 1; i--)
		infact[i] = (ll)(i + 1) * infact[i + 1] % mod;
}
ll C(ll a, ll b) {
	if (a < b)
		return 0;
	return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	init();
	ll n;
	cin >> n;
	vector<ll> a(10);
	for (int i = 0; i < 10; i++)
		cin >> a[i];
	ll inv3 = qmi(3, mod - 2);
	ll blood = n * 10 % mod * inv3 % mod;

	ll p = inv3, p1 = 2ll * inv3 % mod;
	vector<ll> f(n + 1), g(n + 1);
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = f[i - 1] * p % mod;
		g[i] = g[i - 1] * p1 % mod;
	}

	ll res = 0;
	for (int k = 0; k <= 9; k++) {
		ll tmp = 0;
		for (int i = 0; i <= n; i++) {
			tmp = (tmp + C(n, i) * f[i] % mod * g[n - i] % mod * qmi(i, k + 1) % mod) % mod;
		}
		res = (res + a[k] * tmp % mod) % mod;
	}

	res = (n - 1) * res % mod;
	ll attack = (blood + res) % mod;

	cout << attack << ' ' << blood << endl;

	return (0 ^ 0);
}

F 祝泥魔

官方题解的不太懂，补一个从别人提交记录学来的做法。。。~~（本题时限过于宽松， $m a p$ 暴力也能过）~~

题目本质就是动态字符串集的多模匹配，与之对应的数据结构就是 $A C$ 自动机，但是动态增加每次都重构 $f a i l$ 树的话会超时。考虑离线做法，我们可以先将所有要添加的字符串建成 $t r i e$ 树，并构建 $f a i l$ 指针，再把 $t r i e$ 树中的计数清空；然后再遍历操作即可。

const int N = 1e6 + 10;
int tr[N][26], idx;
int cnt[N], len[N], ne[N];
struct Q {
	int op;
	string s;
};
void insert(const string& s, int x) {
	int p = 0;
	for (int i = 0; i < s.length(); i++) {
		int u = s[i] - 'a';
		if (!tr[p][u])
			tr[p][u] = ++idx;
		p = tr[p][u];
	}
	cnt[p] += x;
	len[p] = cnt[p] > 0 ? s.length() : 0;
}
void build() {
	queue<int> q;
	for (int i = 0; i < 26; i++) {
		if (tr[0][i])
			q.push(tr[0][i]);
	}
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {
			int c = tr[t][i];
			if (!c)
				tr[t][i] = tr[ne[t]][i];
			else {
				ne[c] = tr[ne[t]][i];
				q.push(c);
			}
		}
	}
}
void query(const string& str) {
	int sz = str.length();
	vector<int> st(sz);
	vector<bool> vis(sz);
	for (int i = 0, j = 0; i < sz; i++) {
		int t = str[i] - 'a';
		j = tr[j][t];
		int p = j;
		while (p) {
			if (cnt[p]) {
				for (int k = 0; k < len[p]; k++)
					vis[i - k] = 1;
				st[i - len[p] + 1]++;
			}
			p = ne[p];
		}
	}
	for (int i = 0; i < sz; i++) {
		if (vis[i]) {
			for (int j = 0; j < st[i]; j++)
				cout << "junimos";
		} else {
			cout << str[i];
		}
	}
	cout << endl;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<Q> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i].op >> v[i].s;
		if (v[i].op == 1)
			insert(v[i].s, 1);
	}
	build();
	for (int i = 0; i < n; i++) {
		const auto& [op, s] = v[i];
		if (op == 1)
			insert(s, -1);
	}
	for (int i = 0; i < n; i++) {
		const auto& [op, s] = v[i];
		if (op == 1)
			insert(s, 1);
		else if (op == 2)
			insert(s, -1);
		else
			query(s);
	}

	return (0 ^ 0);
}

G 小人国的粉刷匠

基础 $D P$ ， $d p [i] [j] [k]$ 表示已将前 $i$ 块涂色，最后一块颜色为 $j$ ，一共分成 $k$ 块的最小花费。

有些块已经固定了颜色，对于其他的块就多一维遍历涂哪一种颜色。

具体状态转移看代码吧:

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m, k, q;
	cin >> n >> m >> k >> q;
	vector<int> v(n + 1);
	for (int i = 1; i <= q; i++) {
		int x, y;
		cin >> x >> y;
		v[x] = y;
	}
	vector<vector<ll>> p(n + 1, vector<ll>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> p[i][j];
		}
	}
	vector dp(n + 1, vector<vector<ll>>(m + 1, vector<ll>(k + 1, INF)));
	if (v[1] > 0)
		dp[1][v[1]][1] = p[1][v[1]];
	else {
		for (int i = 1; i <= m; i++)
			dp[1][i][1] = p[1][i];
	}
	for (int i = 2; i <= n; i++) {
		for (int pre = 1; pre <= m; pre++) {
			for (int u = 1; u <= k; u++) {
				if (v[i]) {
					if (pre == v[i])
						dp[i][v[i]][u] = min(dp[i][v[i]][u], dp[i - 1][pre][u] + p[i][v[i]]);
					else {
						if (u + 1 <= k)
							dp[i][v[i]][u + 1] = min(dp[i][v[i]][u + 1], dp[i - 1][pre][u] + p[i][v[i]]);
					}
				} else {
					for (int j = 1; j <= m; j++) {
						if (pre == j)
							dp[i][j][u] = min(dp[i][j][u], dp[i - 1][pre][u] + p[i][j]);
						else {
							if (u + 1 <= k)
								dp[i][j][u + 1] = min(dp[i][j][u + 1], dp[i - 1][pre][u] + p[i][j]);
						}
					}
				}
			}
		}
	}
	ll ans = INF;
	if (v[n])
		ans = dp[n][v[n]][k];
	else {
		for (int j = 1; j <= m; j++)
			ans = min(ans, dp[n][j][k]);
	}
	if (ans == INF)
		cout << -1 << endl;
	else
		cout << ans << endl;

	return (0 ^ 0);
}

H 仁慈的富蚝

显然最大面积就是所有点的凸包（称为外凸包）的面积。

次大面积可能是删去外凸包上一个点减去一个三角形的面积，还可能是外凸包上的一条边的两个端点向内部的某个点相连形成三角形，删去这个三角形的面积。

前者直接 $O (N)$ 枚举计算

后者需要对内部的点维护一个内凸包，如果对于外凸包每条边枚举内凸包的所有点，时间复杂度为 $O (N^{2})$ ，无法通过。

观察到枚举完外凸包的一条边，逆时针转向下一条边时，其对应的内凸包的点要么不动，要么按逆时针方向转到某个点，这是具有单调性的，那么就可以双指针内外枚举做到 $O (N)$ ，其实这就是旋转卡壳的思想。

总时间复杂度为 $O (N l o g N)$ ，瓶颈在于求凸包。

struct Point {
	ll x, y;
	Point(ll x = 0, ll y = 0) : x(x), y(y) {}
	bool operator<(const Point& B) const {
		return x == B.x ? y < B.y : x < B.x;
	}
	bool operator==(const Point& B) const {
		return !(x - B.x) && !(y - B.y);
	}
	Point operator+(const Point& B) const {
		return Point(x + B.x, y + B.y);
	}
	Point operator-(const Point& B) const {
		return Point(x - B.x, y - B.y);
	}
	Point operator*(const ll a) const {
		return Point(x * a, y * a);
	}
	Point operator/(const ll a) const {
		return Point(x / a, y / a);
	}
	ll operator*(const Point& B) const {
		return x * B.x + y * B.y;
	}
	ll operator^(const Point& B) const {
		return x * B.y - y * B.x;
	}
	friend int relation(Point a, Point b, Point c) {
		ll flag = ((b - a) ^ (c - a));
		if (flag > 0)
			return 1;
		else if (flag < 0)
			return -1;
		return 0;
	}
	friend ll area(Point a, Point b, Point c) {
		return abs((b - a) ^ (c - a));
	}
};
const int N = 1e5 + 10;
Point q[N], t[N];
int n, m, st1[N], top1, st2[N], top2;
void andrew(Point q[], int st[], int n, int& top) {
	sort(q, q + n);
	for (int i = 0; i < n; i++) {
		while (top > 1 && relation(q[st[top - 1]], q[st[top]], q[i]) < 0)
			top--;
		st[++top] = i;
	}
	int k = top;
	for (int i = n - 2; i >= 0; i--) {
		while (top > k && relation(q[st[top - 1]], q[st[top]], q[i]) < 0)
			top--;
		st[++top] = i;
	}
	if (n > 1)
		top--;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> q[i].x >> q[i].y;
	andrew(q, st1, n, top1);  // 外凸包
	set<int> out;
	for (int i = 1; i <= top1; i++)
		out.insert(st1[i]);
	for (int i = 0; i < n; i++) {
		if (!out.count(i))
			t[m++] = q[i];
	}
	andrew(t, st2, m, top2);  // 内凸包

	ll max_area = 0;
	for (int i = 1; i <= top1; i++)
		max_area += (q[st1[i]] ^ q[st1[i + 1]]);  // 外凸包的面积, 即最大面积

	ll res = LONG_LONG_MAX;			   // 切掉的最小面积
	for (int i = 1; i <= top1; i++) {  // 枚举删掉外凸包上的每个点
		int l = i - 1, r = i + 1;
		if (!l)
			l = top1;
		if (r > top1)
			r = 1;
		res = min(res, area(q[st1[l]], q[st1[i]], q[st1[r]]));
	}

	if (top2) {
		int beg = 1;  // 进行旋转卡壳时, 内凸包的起点
		ll minx = area(q[st1[1]], q[st1[2]], t[st2[1]]);
		for (int i = 2; i <= top2; i++) {
			ll tmp = area(q[st1[1]], q[st1[2]], t[st2[i]]);
			if (tmp < minx) {
				minx = tmp;
				beg = i;
			}
		}

		res = min(res, minx);
		for (int i = 2, j = beg; i <= top1; i++) {
			auto d = q[st1[i]], e = q[st1[i + 1]];
			while (area(d, e, t[st2[j]]) > area(d, e, t[st2[j + 1]]))
				j = j % top2 + 1;
			res = min(res, area(d, e, t[st2[j]]));
		}
	}

	cout << max_area - res << endl;

	return (0 ^ 0);
}

J 神奇的魔法

首先要保证 $B$ 中的字符能拼成 $A$ 串，对于剩下的其他字符，若小于 $A [0]$ 则排在 $A$ 串前面，若大于 $A [0]$ 则排在 $A$ 串后面，那么等于 $A [0]$ 的字符呢？记 $A$ 从前往后第一个不等于 $A [0]$ 的字符为 $s e$ ，还要判断 $A [0]$ 和 $s e$ 的关系（~~赛时没判这个 $W A$ 了好几发~~）

若 $A [0] > s e$ ，等于 $A [0]$ 的字符放 $A$ 后面；若 $A[0]\leq se$ ，等于 $A [0]$ 的字符放到 $A$ 前面

void solve() {
	string s, t;
	cin >> s >> t;
	map<char, int> ls, rs;
	for (auto i : s)
		ls[i]++;
	for (auto i : t)
		rs[i]++;
	for (auto i : s) {
		if (rs[i] < ls[i]) {
			cout << "impossible" << endl;
			return;
		}
	}
	set<char> all(s.begin(), s.end());
	for (auto i : all)
		rs[i] -= ls[i];
	string tmp;
	for (auto [c, num] : rs) {
		for (int i = 0; i < num; i++)
			tmp += c;
	}
	sort(tmp.begin(), tmp.end());
	char st = s[0];
	char se = s[0];
	for (int i = 1; i < s.length(); i++) {
		if (s[i] != s[0]) {
			se = s[i];
			break;
		}
	}
	bool flag = 0;
	for (int i = 0; i < tmp.length(); i++) {
		if (tmp[i] < st)
			cout << tmp[i];
		else if (tmp[i] == st) {
			if (tmp[i] <= se)
				cout << tmp[i];
			else {
				if (!flag) {
					cout << s;
					flag = 1;
				}
				cout << tmp[i];
			}
		} else {
			if (!flag) {
				cout << s;
				flag = 1;
			}
			cout << tmp[i];
		}
	}
	if (!flag)
		cout << s;
	cout << endl;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return (0 ^ 0);
}

K 蚝蚝蚝大王的字符串

考虑每一个从左到右首次出现的子串对查询的贡献，若该子串为 $S [x . . . y]$ ，则其对 $L\leq x$ 且 $R\geq y$ 的查询有 $1$ 的贡献

在线的话需要树套树，不过我们可以离线做，将查询按右端点升序排序，这样 $R \geq y$ 就自然满足，只需考虑左端点。

可以利用 $S A M$ 预处理出插入一个新字符产生的本质不同子串的左端点区间，将该区间加 $1$ 。

const int N = 200000;
struct Q {
	int l, r, id;
	bool operator<(const Q& B) const {
		return r < B.r;
	}
};
struct SegmentTree {
	struct Node {
		int l, r;
		ll sum, add;
	} tr[N << 2];
	void build(int u, int l, int r) {
		tr[u] = {l, r};
		if (l == r)
			return;
		int mid = l + r >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	}
	void pushup(int u) {
		tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
	}
	void eval(Node& U, ll add) {
		U.sum += (U.r - U.l + 1) * add;
		U.add += add;
	}
	void pushdown(int u) {
		if (tr[u].add) {
			eval(tr[u << 1], tr[u].add), eval(tr[u << 1 | 1], tr[u].add);
			tr[u].add = 0;
		}
	}
	void modify(int u, int l, int r, int v) {
		if (tr[u].l >= l && tr[u].r <= r) {
			eval(tr[u], v);
			return;
		}
		int mid = tr[u].l + tr[u].r >> 1;
		pushdown(u);
		if (l <= mid)
			modify(u << 1, l, r, v);
		if (r > mid)
			modify(u << 1 | 1, l, r, v);
		pushup(u);
	}
	ll query(int u, int l, int r) {
		if (tr[u].l >= l && tr[u].r <= r) {
			return tr[u].sum;
		}
		int mid = tr[u].l + tr[u].r >> 1;
		ll res = 0;
		pushdown(u);
		if (l <= mid)
			res += query(u << 1, l, r);
		if (r > mid)
			res += query(u << 1 | 1, l, r);
		return res;
	}
} seg;
char str[N];
struct SAM {
	struct tr {
		int len, fa, ch[26];
	} tr[N];
	int tot = 1, last = 1;
	int head[N], v[N], ne[N], idx;
	void extend(int c, int pos) {
		int p = last, np = last = ++tot;
		tr[np].len = tr[p].len + 1;
		for (; p && !tr[p].ch[c]; p = tr[p].fa)
			tr[p].ch[c] = np;
		if (!p)
			tr[np].fa = 1;
		else {
			int q = tr[p].ch[c];
			if (tr[q].len == tr[p].len + 1)
				tr[np].fa = q;
			else {
				int nq = ++tot;
				tr[nq] = tr[q], tr[nq].len = tr[p].len + 1;
				tr[q].fa = tr[np].fa = nq;
				for (; p && tr[p].ch[c] == q; p = tr[p].fa)
					tr[p].ch[c] = nq;
			}
		}
		seg.modify(1, pos - tr[np].len + 1, pos - tr[tr[np].fa].len, 1);
	}
} sam;
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> str + 1 >> m;
	vector<Q> v;
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		v.push_back({l, r, i});
	}
	sort(v.begin(), v.end());
	int pos = 0;
	seg.build(1, 1, n);
	vector<ll> ans(m + 1);
	for (auto& [l, r, id] : v) {
		while (pos < r) {
			pos++;
			sam.extend(str[pos] - 'a', pos);
		}
		ans[id] = seg.query(1, l, pos);
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << endl;

	return (0 ^ 0);
}

L 生蚝吃蚝蚝

将新鲜蚝蚝看为 $1$ ，普通蚝蚝看为 $0$ ，坏蚝蚝看为 $- 1$ ，求个前缀和，枚举右端点 $r$ ，查询有几个左端点满足 $sum[r]-sum[l-1]\geq0$

但是本题要求区间中至少有一个新鲜蚝蚝，即至少有一个 $1$ ，则需要记录一下最后一个 $1$ 出现的位置，问题就转化为了求历史区间中 $\leq sum[r]$ 的个数，瞬间想到主席树，~~但赛时有个小错误一直没发现，换队友写了树状数组才过~~。树状数组的做法就是不像主席那样每遍历到一个 $i$ ，就将 $s u m [i]$ 存入，而是遇到一个新的 $1$ ，才将上一个 $1$ 到当前位置之间的 $s u m$ 存入，这样就不需要可持久化了。

这里我就补一下主席树的做法吧 $q w q$

时间复杂度 $O (N l o g N)$

const int N = 1e5 + 10;
vector<int> nums;
int find(int x) {
	return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int idx, root[N];
struct Node {
	int l, r, cnt;
} tr[N * 50];
int build(int l, int r) {
	int p = ++idx;
	if (l == r)
		return p;
	int mid = l + r >> 1;
	tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
	tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
	return p;
}
int insert(int p, int l, int r, int x) {
	int q = ++idx;
	tr[q] = tr[p];
	if (l == r) {
		tr[q].cnt++;
		return q;
	}
	int mid = l + r >> 1;
	if (x <= mid)
		tr[q].l = insert(tr[p].l, l, mid, x);
	else
		tr[q].r = insert(tr[p].r, mid + 1, r, x);
	tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
	return q;
}
int query(int q, int p, int l, int r, int k) {
	if (r <= k)
		return tr[q].cnt - tr[p].cnt;
	if (l == r)
		return 0;
	int mid = l + r >> 1;
	int res = 0;
	res += query(tr[q].l, tr[p].l, l, mid, k);
	if (k > mid)
		res += query(tr[q].r, tr[p].r, mid + 1, r, k);
	return res;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, x, y;
	cin >> n >> x >> y;
	vector<int> a(n + 1), b(n + 1), sum(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] > x)
			b[i] = 1;
		else if (a[i] < y)
			b[i] = -1;
	}
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + b[i], nums.push_back(sum[i]);
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	root[0] = build(0, nums.size() - 1);

	ll ans = 0;
	int last = 0;
	for (int i = 1; i <= n; i++) {
		if (b[i] == 1) {
			int res = query(root[i - 1], root[0], 0, nums.size() - 1, find(sum[i]));
			if (sum[i] >= 0)
				res++;
			ans += res;
			last = i;
		} else {
			if (last) {    // 赛时写成 if(!last) continue; 导致跳过了下面的insert, 一直没发现, ┭┮﹏┭┮..
				int res = query(root[last - 1], root[0], 0, nums.size() - 1, find(sum[i]));
				if (sum[i] >= 0)
					res++;
				ans += res;
			}
		}
		root[i] = insert(root[i - 1], 0, nums.size() - 1, find(sum[i]));
	}
	cout << ans << endl;

	return (0 ^ 0);
}

M 完美生蚝

比较裸的数位 $D P$ ，利用状压存储有哪些数字的状态，套一下板子就行啦

const int N = 20, M = (1 << 10);
ll k, l, r, a[N], len, dp[N][M];
ll dfs(int pos, int state, int lead, int limit) {
	if (!pos) {
		if (state == ((1 << (k + 1)) - 1))
			return 1;
		return 0;
	}
	if (!limit && !lead && dp[pos][state] != -1)
		return dp[pos][state];
	ll res = 0;
	int up = limit ? a[pos] : 9;
	for (int i = 0; i <= up; i++) {
		if (lead && i == 0)
			res += dfs(pos - 1, state, lead && !i, limit && i == up);
		else {
			if (i <= k)
				res += dfs(pos - 1, state | (1 << i), lead && !i, limit && i == up);
			else
				res += dfs(pos - 1, state, lead && !i, limit && i == up);
		}
	}
	return limit ? res : (lead ? res : dp[pos][state] = res);
}
ll cal(ll x) {
	memset(dp, -1, sizeof(dp));
	len = 0;
	while (x)
		a[++len] = x % 10, x /= 10;
	return dfs(len, 0, 1, 1);
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		cin >> k >> l >> r;
		cout << cal(r) - cal(l - 1) << endl;
	}

	return (0 ^ 0);
}

N wqy's easy problem

排序后对连续上升序列进行计算即可

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a.begin() + 1, a.end());
	int last = 1;
	ll ans = 0;
	for (int i = 2; i <= n; i++) {
		if (a[i] == a[i - 1] + 1) {
			last++;
			if (last >= 2)
				ans += last - 1;
		} else {
			last = 1;
		}
	}
	cout << ans << endl;

	return (0 ^ 0);
}