NOI真题训练

真题训练，不依靠外力做题，多写几个部分分，研究高效得分方法。

以下评测分数以 loj 提交为准（冒泡排序除外）。分数统计仅代表极限水平，并不代表真实水平，不供参考。

NOI2017

0 + 76 + 100 + 70 + 100 + 88 + 20 = 454

集训队线 438 。

整数

看完题就有了一个压位的平方暴力的思路，码了码 WA 在了减法的情况，改对后得到了 56 分，本来对照数据表以为只有 30 分左右。

int main() {
    int n = read;
    read.operator int(), read.operator int(), read.operator int();
    int B = 32;
    ull FULL = (1llu << B) - 1;
    for (int i = 1; i <= n; i++) {
        int o = read;
        if (o == 1) {
            int ix = read, k = read;
            if (ix >= 0) {
                ull x = ull(ix);
                x <<= k % B;
                k /= B;
                while (x) {
                    data[k] += x;
                    x = data[k] >> B;
                    data[k] &= FULL;
                    ++k;
                }
            } else {
                ull x = ull(-ix);
                x <<= k % B;
                k /= B;
                while (x) {
                    data[k] -= x;
                    x = data[k] >> B;
                    if (x)
                        x = (1llu << B) - x;
                    data[k] &= FULL;
                    ++k;
                }
            }
        }
        if (o == 2) {
            int k = read;
            printf("%llu\n", data[k / B] >> (k % B) & 1);
        }
    }
}

冷静下来后发现可以类似于 odt 维护二进制位相同的连续段，把修改每一位拆开考虑就可以两个 \(\log\) 维护，得到了 68 分。

auto find (int k) {
	auto it = -- set.upper_bound(k << 1 | 1);
	int k2 = *it >> 1, x = *it & 1;
	if (k == k2) return it;
	return set.insert(k << 1 | x).first;
}

void modi (int k, int t) {
	auto p = find(k), q = p;
	while ((*q & 1) == t) ++ q;
	auto r = find((*q >> 1) + 1);
	int tmp = *p, tmq = *q;
	set.erase(p, r);
	set.insert(tmp ^ 1);
	set.insert(tmq ^ 1);
}

int main () {
	int n = read;
	read.operator int(), read.operator int(), read.operator int();
	set.insert(0 << 1 | 0);
	for (int i = 1; i <= n; i ++) {
		int o = read;
		if (o == 1) {
			int x = read, off = read;
			if (x >= 0) {
				for (int k = 0; k < maxk; k ++)
					if (x >> k & 1)
						modi(off + k, 1);
			}
			else {
				x = -x;
				for (int k = 0; k < maxk; k ++)
					if (x >> k & 1)
						modi(off + k, 0);
			}
		}
		if (o == 2) {
			auto p = find(read);
			printf("%d\n", *p & 1);
		}
	}
}

然后没什么思路了，感觉应该还是要压位，但是维护连续段后似乎难以直接压位？想到 std::insert 可以提供 hint 做到 \(O(1)\) ，于是写了个带 hint 的版本，得了 76 分。（代码略）

然后发现两个 \(\log\) 的瓶颈现在就只在 find 上，由于每次修改拆开后位置相隔很近，事实上 find 也可以给它来个 hint ，每次修改就只需要一次二分，剩下的在之前的基础上暴力跳就好了，复杂度理论上说应该是一个 \(\log\) ，但是只有 84 分，本地测了一下最大的点要跑 2.7s 。

水讨论发现别人用这个方法直接过了，而且时间还不到 1s ，我 tm 又一次吃了常数的亏。

const int maxn = 1000005, maxk = 30;
ull data[maxn];
std::set<int> set;
bool hint;
auto set_hint = set.end();

auto find (int k) {
	auto it = hint ? set_hint : -- set.upper_bound(k << 1 | 1);
	if (hint) {
		while (it != set.end() and (*it >> 1) <= k) ++ it;
		-- it;
	}
	int k2 = *it >> 1, x = *it & 1;
	if (k == k2) return it;
	return set.insert(it, k << 1 | x);
}

void modi (int k, int t) {
	auto p = find(k), q = p;
	while ((*q & 1) == t) ++ q;
	auto r = find((*q >> 1) + 1);
	int tmp = *p, tmq = *q;
	set.erase(p --, r);
	set_hint = set.insert(p, tmp ^ 1);
	set.insert(set_hint, tmq ^ 1);
	hint = 1;
}

int main () {
	int n = read;
	read.operator int(), read.operator int(), read.operator int();
	set.insert(-1);
	set.insert(0 << 1 | 0);
	for (int i = 1; i <= n; i ++) {
		int o = read;
		if (o == 1) {
			int x = read, off = read;
			if (x >= 0) {
				hint = 0;
				for (int k = 0; k < maxk; k ++)
					if (x >> k & 1)
						modi(off + k, 1);
			}
			else {
				hint = 0;
				x = -x;
				for (int k = 0; k < maxk; k ++)
					if (x >> k & 1)
						modi(off + k, 0);
			}
		}
		if (o == 2) {
			/* hint = 0; */
			int k = read;
			auto p = -- set.upper_bound(k << 1 | 1);
			printf("%d\n", *p & 1);
		}
	}
}

蚯蚓排队

刚开始有个启发式合并 + SAM 的想法，但是发现由于 SAM 只能在末尾加字符而不能加在开头，启发式合并是不可行的。

然后发现读错题了，原来询问是在所有串中询问，我还以为是对一个指定的蚯蚓队列进行询问。然后就想到了一个复杂度巨大的暴力，大概是 \(O(mk^2\log + cn + n\log + s\log)\) ，预计 40 分，实际 56 分（全 1 的点复杂度瓶颈处少一个 \(\log\) ）。

void force (int i, int j, int coe) {
	ull shit = 0;
	for (int x = i, k = 1; x and k < Maxk; k ++, x = pre[x]) {
		shit += ull(a[x]) * po[k - 1];
		ull now = shit;
		for (int y = j, k2 = k + 1; y and k2 <= Maxk; k2 ++, y = nxt[y])
			map[now = now * base + ull(a[y])] += coe;
	}
}

int main () {
	po[0] = 1;
	for (int i = 1; i <= Maxk; i ++) po[i] = po[i - 1] * base;
	int n = read, q = read;
	for (int i = 1; i <= n; i ++)
		++ map[ull(a[i] = read)];
	while (q --) {
		int o = read;
		if (o == 1) {
			int i = read, j = read;
			nxt[i] = j;
			pre[j] = i;
			force(i, j, 1);
		}
		if (o == 2) {
			int i = read, j = nxt[i];
			force(i, j, -1);
			nxt[i] = pre[j] = 0;
		}
		if (o == 3) {
			scanf("%s", s + 1);
			int len = int(strlen(s + 1)), K = read;
			ull now = 0;
			for (int i = 1; i <= K; i ++)
				now = now * base + ull(s[i] - '0');
			ll ans = map[now];
			for (int i = K + 1; i <= len; i ++) {
				now = now * base + ull(s[i] - '0');
				now -= ull(s[i - K] - '0') * po[K];
				(ans *= map[now]) %= mod;
			}
			printf("%lld\n", ans);
		}
	}
}

只会暴力，上面的算法主要问题是 map 太慢，用数组分摊给它优化一波：

const ull B = 24, Bl = (1llu << B) - 1;
std::map<ull, int> Map[1 << B];
int &map (ull x) { return Map[x & Bl][x >> B]; }

本地测最慢跑了将近 3s ，交上去，它过了。。。过了。。。。了。。。

看了看题解，发现这个正解就是把 map 换成哈希表？不会吧不会吧。（不过为什么我完全没有想到用哈希表啊？）

说起来也是，这题 2G 的空间原来是这个意图。。。

泳池

显然问题要转换为求最大面积不超过 \(K\) 的概率，设随机变量 \(H_i\) 表示第 \(i\) 列的安全高度，不难得到 \(H_i\) 的分布。

一开始想的是 \(O(n!)\) 枚举所有 \(H\) 的相对大小顺序然后计算，很快发现可以 DP ，设 \(f_{n,m}\) 表示考虑 \(n\) 列，这 \(n\) 列最小值不小于 \(m\) 的满足条件的概率，转移枚举最左边的最小值的位置和值即可，这个 DP 不需要任何优化就可以得到 70 分。一开始以为它的复杂度是 \(O(n^3)\) 甚至 \(O(n^4)\) 级别，冷静分析发现有调和级数，实际上不超过 \(O(n^2\log^2)\) 。

ll solve (int N, int K, ll q) {
	if (K < 0) return 0;
	h[0] = mod + 1 - q;
	for (int x = 1; x <= K; x ++)
		h[x] = h[x - 1] * q % mod;
	std::fill(f[0], f[0] + K + 2, 1);
	for (int n = 1; n <= N; n ++) {
		std::fill(f[n], f[n] + K + 2, 0);
		for (int m = 0; n * m <= K; m ++) {
			for (int i = 1; i <= n; i ++)
				for (int x = m; n * x <= K; x ++)
					(f[n][m] += h[x] * f[i - 1][x + 1] % mod * f[n - i][x]) %= mod;
		}
	}
	return f[N][0];
}

感觉正解应该是 \(O(K^2 \log N)\) 的复杂度，比如常系数齐次线性递推之类的。

或者这个转移看上去很能扯上卷积，正解可能可以用生成函数推导？

游戏

这道题学 2-sat 的时候做过了，题目的限制摆明了就是 2-sat ，只有形如 x 的地图不好处理，初看只能 \(O(3^d)\) 枚举，但实际上只要随便枚举两种状态就能涵盖所有情况，因此带上个 \(O(2^d)\) 就好了。

蔬菜

\(x_i = 0\) 的话显然把每个蔬菜的第一个拆出来然后全部排一遍序就行了，数据表上这个做法只有 20 分，但实际上直接这样做就有 44 分。。。i 了 i 了。

int main () {
	int n = read, m = read, q = read;
	int pp = 0;
	for (int i = 1; i <= n; i ++) {
		int a = read, s = read, c = read, x = read;
		p[++ pp] = par(a, c - 1);
		p[++ pp] = par(a + s, 1);
	}
	std::sort(p + 1, p + pp + 1);
	p[0] = par(0, 1000000000);
	for (int i = 1; i <= 100000; i ++) {
		ans[i] = ans[i - 1];
		for (int j = 1; j <= m; j ++) {
			while (!p[pp].second) -- pp;
			-- p[pp].second;
			ans[i] += p[pp].first;
		}
	}
	while (q --) {
		int d = read;
		printf("%lld\n", ans[d]);
	}
}

进一步地，可以把每种蔬菜拆成 \(c\) 个单位蔬菜，每个单位蔬菜可以用二元组 \((a, T)\) 表示，其中 \(a\) 是收益，\(T\) 是该蔬菜消失的时间。那么把所有单位蔬菜排序然后暴力贪心，单位蔬菜的数量理论上来说是没有保证的，但神奇的事随便减减枝直接搞就能得到 \(p \le 10^3\) 的所有 80 分部分分，结合之前 \(x_i = 0\) 的做法可以得到 88 分。

有理有据的做法也是有的，理论上把所有单位蔬菜拿出来不现实，但考虑到需要做的是把单位蔬菜排序，不妨把来源相同的单位蔬菜绑定在一起，用堆维护起来。注意到来源相同的单位蔬菜 \(a\) 相同，用 \(T\) 最大的单位蔬菜代表这些来源相同的蔬菜。一个非常重要的性质是，如果单位蔬菜 \((a, T)\) 无法加入当前答案，那么它永远无法被加入之后的任何一个答案。推广到一些来源相同的蔬菜，如果 \(T\) 最大的单位蔬菜无法被加入到当前答案，那么这些来源相同的所有蔬菜都可以扔掉。

这样一来就可以做到 \(O((n + pm)\log + (pm)^2)\) 的复杂度，瓶颈部分 \(O((np)^2)\) 在于每次暴力添加一个蔬菜到当前答案集合，事实上这个完全可以用数据结构优化，但是感觉也拿不到 \(10^5\) 的部分分，所以就写了暴力。

下面的代码是 80 分代码（没有处理 \(x_i = 0\) 的部分分）。

const int maxn = 100005;
ll ans[maxn * 10];
struct cai {
	int a, c, x, t;
	int las () {
		if (t) return t;
		return x ? (c + x - 1) / x : 1000000000;
	}
};

bool operator < (cai a, cai b) {
	return a.a == b.a ? a.las() < b.las() : a.a < b.a;
}

int M, tim[maxn], tp, minT;
bool check (int t) { return t >= minT; }

void add (int t) {
	tim[++ tp] = t;
	std::sort(tim + 1, tim + tp + 1); // 懒
	minT = tp / M * M;
	while (minT >= 0 and tim[minT] != minT / M) minT -= M;
	minT = minT >= 0 ? tim[minT] + 1 : 1;
}

int main () {
	int K = 1000;
	int n = read, m = read, q = read;
	std::priority_queue<cai> qu;
	M = m;
	qu.push({0, 1000000000, 0, 1000000000});

	for (int i = 1; i <= n; i ++) {
		int a = read, s = read, c = read, x = read;
		cai tmp = {a, c - 1, x, 0};
		qu.push(tmp);
		++ tmp.c;
		qu.push({s + a, 1, 0, tmp.las()});
	}

	for (int i = 1; i <= K * m; i ++) {
		cai tmp = qu.top();
		qu.pop();
		while (tmp.c <= 0 or !check(tmp.las()))
			tmp = qu.top(), qu.pop();
		ans[i] = ans[i - 1] + tmp.a;
		add(tmp.las());
		if (tmp.c > 1) {
			-- tmp.c;
			qu.push(tmp);
		}
	}

	while (q --) printf("%lld\n", ans[int(read) * m]);
}

分身术

计算几何啥也不会，暴力求凸包，只能拿 20 分。

int main () {
	int n = read, q = read;
	ll ans = -1;
	for (int i = 1; i <= n; i ++) read(P[i].x, P[i].y);
	while (q --) {
		int m = read;
		std::fill(mark, mark + n + 1, 0);
		for (int i = 1; i <= m; i ++) mark[1 + (ans + int(read)) % n] = 1;
		m = 0;
		for (int i = 1; i <= n; i ++) if (!mark[i]) p[++ m] = P[i];
		std::sort(p + 1, p + m + 1, [] (point a, point b) {
					return a.x == b.x ? a.y < b.y : a.x < b.x;
				});
		int p1 = 0;
		for (int i = 1; i <= m; i ++) {
			while (p1 >= 2 and cross(st1[p1] - st1[p1 - 1], p[i] - st1[p1]) >= 0) -- p1;
			st1[++ p1] = p[i];
		}
		std::sort(p + 1, p + m + 1, [] (point a, point b) {
					return a.x == b.x ? a.y > b.y : a.x < b.x;
				});
		int p2 = 0;
		for (int i = 1; i <= m; i ++) {
			while (p2 >= 2 and cross(st2[p2] - st2[p2 - 1], p[i] - st2[p2]) <= 0) -- p2;
			st2[++ p2] = p[i];
		}
		while (p2) st1[++ p1] = st2[p2 --];
		st1[p1 + 1] = st1[1];
		ans = 0;
		for (int i = 2; i <= p1; i ++)
			ans -= cross(st1[i] - st1[1], st1[i + 1] - st1[i]);
		printf("%lld\n", ans);
	}
}

\(k = 1\) 似乎很有性质，预先求出凸包，如果删除的点不在凸包上可以忽略，否则能被新加入的点一定在一个三角形的区域内，而每个不在凸包的点至多属于两个不同的三角形区域，那么可以在每个三角形区域内再求一次凸包。

说是这么说，要实现感觉有点麻烦，咕咕咕。

听说这题的 idea 是 picks 出的。

NOI2018

0 + 100 + 84 + 100 + 100 + 45 + 15 = 444

集训队线 452 。

归程

如果允许离线，不难想到可以把边按 \(a\) 排序，把询问按 \(p\) 排序，预处理个最短路然后不断加边，用并查集维护每个点的答案，可以得到 65 分。

int find (int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void dijkstra (int s, int n);

int main () {
#ifndef LOCAL
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
#endif

	int T = read;
	while (T --) {
		int n = read, m = read;
		for (int u = 1; u <= n; u ++) G[u].clear();
		for (int i = 1; i <= m; i ++) {
			int u = read, v = read, w = read, h = read;
			G[u].push_back({v, w});
			G[v].push_back({u, w});
			e2[i] = {u, v, h};
		}
		dijkstra(1, n);

		int q = read, K = read, H = read;
		if (K == 1) return 0;
		for (int i = 1; i <= q; i ++) {
			int s = read, h = read;
			qu[i] = {s, h, i};
		}

		std::sort(e2 + 1, e2 + m + 1, [] (Edge2 a, Edge2 b) {
					return a.h > b.h;
				});
		std::sort(qu + 1, qu + q + 1, [] (Query a, Query b) {
					return a.h > b.h;
				});

		for (int u = 1; u <= n; u ++) fa[u] = u;

		for (int i = 1, j = 1; i <= q; i ++) {
			while (j <= m and e2[j].h > qu[i].h) {
				int u = find(e2[j].u), v = find(e2[j].v);
				++ j;
				if (dis[u] < dis[v]) fa[v] = u;
				else fa[u] = v;
			}
			ans[qu[i].id] = dis[find(qu[i].s)];
		}

		for (int i = 1; i <= q; i ++) printf("%d\n", ans[i]);
	}
}

强制在线似乎可以直接把加边的过程可持久化，来一手可持久化并查集？

太麻烦了没写，还可以用 kruskarl 重构树，对于询问倍增到重构树上的点，然后求个子树 min 即可，写的时候重构树的点数只开到了 n ，WA 了几次。

const int maxn = 200005, maxm = 400005, maxk = 20;
const int Maxk = 19;
struct Edge { int v, w; };
std::vector<Edge> G[maxn];
int dis[maxn + maxm];
struct Edge2 { int u, v, h; } e2[maxm];
int fa[maxk][maxn + maxm], top[maxn + maxm], minh[maxn + maxm];

int find (int x) { return top[x] == x ? x : top[x] = find(top[x]); }

void dijkstra (int s, int n) {
	std::priority_queue<par> q;
	std::fill(dis, dis + n + 1, 2000000000);
	dis[s] = 0;
	q.push(par(0, s));
	while (!q.empty()) {
		int u = q.top().second, d = -q.top().first;
		q.pop();
		if (d > dis[u]) continue;
		for (Edge e : G[u])
			if (dis[u] + e.w < dis[e.v]) {
				dis[e.v] = dis[u] + e.w;
				q.push(par(-dis[e.v], e.v));
			}
	}
}

int main () {
#ifndef LOCAL
	freopen("return.in", "r", stdin);
	freopen("return.out", "w", stdout);
#endif

	int T = read;
	while (T --) {
		int n = read, m = read;
		for (int u = 1; u <= n; u ++) G[u].clear();
		for (int i = 1; i <= m; i ++) {
			int u = read, v = read, w = read, h = read;
			G[u].push_back({v, w});
			G[v].push_back({u, w});
			e2[i] = {u, v, h};
		}
		dijkstra(1, n);

		std::sort(e2 + 1, e2 + m + 1, [] (Edge2 a, Edge2 b) {
					return a.h > b.h;
				});
		for (int u = 1; u <= n; u ++) top[u] = u, minh[u] = 2000000000;

		int np = n;
		for (int i = 1; i <= m; i ++) {
			int u = find(e2[i].u), v = find(e2[i].v);
			if (u == v) continue;
			++ np;
			fa[0][u] = fa[0][v] = np;
			fa[0][np] = 0;
			top[u] = top[v] = top[np] = np;
			minh[np] = e2[i].h;
			dis[np] = std::min(dis[u], dis[v]);
		}

		for (int x = np; x; x --)
			for (int k = 1; k < Maxk; k ++)
				fa[k][x] = fa[k - 1][fa[k - 1][x]];

		int q = read, K = read, S = read, ans = 0;
		if (!n) return 1;
		while (q --) {
			int x = read, h = read;
			if (K) x = 1 + (x + ans - 1) % n, h = (h + ans) % (S + 1);
			for (int k = Maxk - 1; k >= 0; k --)
				if (fa[k][x] and minh[fa[k][x]] > h)
					x = fa[k][x];
			printf("%d\n", ans = dis[x]);
		}
	}
}

冒泡排序

稍加分析，不难发现一个排列 \(p\) 是“好”的，当且仅当：

• \(\forall j < i \le p_i, p_j < p_i\)
• \(\forall j > i \ge p_i, p_j > p_i\)

直接拿这个写个状压 DP ，可以得到 44 分，代码略。

对于 \(q_i = i\) 的情况，打个表不难发现就是卡特兰数，理论上结合上面做法可以得到 56 分，但实际上并没有这样的数据？

int main () {
#ifndef LOCAL
	freopen("inverse.in", "r", stdin);
	freopen("inverse.out", "w", stdout);
#endif

	int T = read;
	while (T --) {
		int n = read;
		if (n > maxn) {
			for (int i = 0; i < n; i ++) read.operator int();
			ll ans = 1;
			for (int i = 1; i <= n; i ++) {
				(ans *= 4 * i - 2) %= mod;
				(ans *= power(i + 1, -1)) %= mod;
			}
			-- ans;
			printf("%lld\n", ans);
			continue;
		}
		for (int i = 0; i < n; i ++) p[i] = read - 1;
		g[0] = 1;
		for (int S = 1; S < (1 << n); S ++) {
			int i = -1, max = 0, X = 0;
			for (int x = 0; x < n; x ++)
				if (S >> x & 1)
					++ i, max = x;
			while (S >> X & 1) ++ X;
			f[S] = g[S] = 0;
			for (int x = 0; x < n; x ++)
				if (S >> x & 1) {
					bool ok = 1;
					if (x <= i) ok &= x < X;
					if (x >= i) ok &= x == max;
					if (ok) {
						f[S] += f[S ^ (1 << x)];
						if (x == p[i]) g[S] += g[S ^ (1 << x)];
						if (x > p[i]) f[S] += g[S ^ (1 << x)];
					}
				}
			f[S] %= mod;
		}
		printf("%lld\n", f[(1 << n) - 1]);
	}
}

冷静下来，拿上面的性质进一步分析，发现一个排列是“好”的当且仅当它可以划分成两个上升子序列，也等价于最长下降子序列的长度不超过 2 。

这个性质就好用很多，比如可以直接证明不考虑字典序的答案确实是卡特兰数：

设计 DP \(f_{i, j}\) 表示 \(1\) 到 \(i\) 的排列，包含右端点的最大上升子段长度为 \(j\) 的“好”排列数，转移新插入一个最大值，不难得到 \(f_{i, j} = \sum_{k \ge j-1} f_{i-1, k} = f_{i-1, j-1} + f_{i, j+1}\) ，特别的是 \(f_{0,1}=1, f_{i,0}=0\) 。这个时候稍有经验就会知道这个 DP 转移可以放在二维平面上，而 \(f_{i,0}=0\) 的限制就是平面上的一条直线，不经过一条直线的路径数恰恰就是卡特兰数。

但是如果从小到大加数的话字典序的比较就难以压缩在状态里，不妨直接枚举 \(p, q\) 的 lcp 以及 lcp 后面的一位，然后相当于确定了上述 DP 的一个初始状态，放在二维平面上利用折线法计算即可，可以得到 80 分，结合 \(p_i = i\) 的情况理论上有 84 分。

ll _path (int x, int y) {
	if (x < 0 or y < 0) return 0;
	return fac[x + y] * ifac[x] % mod * ifac[y] % mod;
}

ll path (int x0, int y0, int x1, int y1) {
	ll tmp = _path(x1 - x0, y1 - y0) - _path(x1 - x0 - 1, y1 - y0 + 1);
	return tmp < 0 ? tmp + mod : tmp;
}

int main () {
#ifndef LOCAL
	freopen("inverse.in", "r", stdin);
	freopen("inverse.out", "w", stdout);
#endif

	int N = 2000;
	fac[0] = 1;
	for (int i = 1; i <= N; i ++) fac[i] = fac[i - 1] * i % mod;
	ifac[N] = power(fac[N], -1);
	for (int i = N; i; i --) ifac[i - 1] = ifac[i] * i % mod;

	int T = read;
	while (T --) {
		int n = read;
		for (int i = 1; i <= n; i ++) p[i] = read;
		ll ans = 0;
		std::fill(vis + 1, vis + n + 1, 0);
		std::set<int> set;
		for (int i = 1; i <= n; i ++) set.insert(i);
		int m = 0, x = 0;
		for (int i = 1; i <= n; i ++) {
			for (int j = std::max(p[i], x) + 1; j <= n; j ++)
				if (!vis[j]) {
					int _m = std::max(m, j);
					set.erase(j);
					int k = *set.begin();
					set.insert(j);
					if (k < x or (k < j and j < m)) continue;
					ans += path(_m, i, n, n);
				}
			vis[p[i]] = 1;
			if (p[i] < x) break;
			if (p[i] < m) x = p[i];
			else m = p[i];
			set.erase(p[i]);
		}
		printf("%lld\n", ans % mod);
	}
}

上述算法的瓶颈在于 \(O(n^2)\) 枚举字典序的比较情况，再往下优化必然要用更巧妙的方式处理字典序比较，或者干脆抛弃从小到大加数的思路？

你的名字

\(l = 1, r = |S|\) 的话，把 \(s\) 建 SAM ，再把每个 \(t\) 也建 SAM ，同时把 \(t\) 放进 \(s\) 的 SAM 里跑，得到 \(t\) 的每个前缀在两个 SAM 里面分别对应的节点，然后在 \(t\) 的 SAM 上跳 fail 算贡献即可，可以得到 68 分。

int insert (int rt, int pre, int x);

int main () {
#ifndef LOCAL
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
#endif

	scanf("%s", s + 1);
	int n = int(strlen(s + 1));
	for (int i = 1, las = 1; i <= n; i ++)
		las = insert(1, las, s[i] - 'a');
	tpos[0] = ++ cp;

	int q = read;
	while (q --) {
		scanf("%s", t + 1);
		int l = read, r = read, m = int(strlen(t + 1));
		if (l != 1 and r != n) return 1;
		cp = tpos[0];
		memset(ch[cp], 0, sizeof ch[cp]);
		for (int i = 1; i <= m; i ++)
			tpos[i] = insert(tpos[0], tpos[i - 1], t[i] - 'a');
		std::fill(vis + tpos[0], vis + cp + 1, 0);

		ll ans = 0;
		for (int i = 1, u = 1, le = 0; i <= m; i ++) {
			int x = t[i] - 'a';
			while (u and !ch[u][x]) u = fa[u], le = len[u];
			if (u) u = ch[u][x], ++ le;
			else u = 1;
			int v = tpos[i], vlen = len[v], flen = vlen;
			while (!vis[v]) vis[v] = 1, v = fa[v], flen = len[v];
			ans += vlen - std::max(flen, le);
		}
		printf("%lld\n", ans);
	}
}

这个做法推广到任意区间也不难，把 \(s\) 的 SAM 节点的 right 集合处理出来，然后每次算贡献的时候查 right 集合在区间内最靠右的点然后得到实际匹配长度即可。但是 right 集合不能显式地建出来，一般有两种方式，一个是离线下来挂在对应位置然后 set 启发式合并，还有一种是线段树合并。后者唯一的缺点是空间开销较大，但是其他地方都很优秀，并且还能支持更多操作。

复杂度 \(O(n\log)\) 级别，实现的细节比我想象中的要多，调了一段时间才过。

const int maxn = 500005, maxd = 2000005, maxc = 26;
std::vector<int> G[maxd];
char s[maxn], t[maxn];
int ch[maxd][maxc], fa[maxd], len[maxd], cp = 1;
bool vis[maxd];
int spos[maxn], tpos[maxn];
int seg[maxd];
struct Tree {
	int lti, rti;
	int max;
} pool[maxn * 60];
#define self pool[now]

int pp;
inline int newnode () { return ++ pp; }

void merge (int &now, int an, int L, int R) {
	if (!an) return;
	if (!now) return now = an, void();
	pool[newnode()] = self;
	now = pp;
	self.max = std::max(self.max, pool[an].max);
	int M = (L + R) >> 1;
	merge(self.lti, pool[an].lti, L, M);
	merge(self.rti, pool[an].rti, M + 1, R);
}

void lain (int &now, int L, int R, int p) {
	if (!now) now = newnode();
	self.max = std::max(self.max, p);
	if (L == R) return;
	int M = (L + R) >> 1;
	if (p <= M) lain(self.lti, L, M, p);
	else lain(self.rti, M + 1, R, p);
}

int query (int now, int L, int R, int l, int r) {
	if (r < L or l > R) return 0;
	if (l <= L and R <= r) return self.max;
	int M = (L + R) >> 1;
	return std::max(query(self.lti, L, M, l, r), query(self.rti, M + 1, R, l, r));
}

int insert (int rt, int pre, int x) {
	int now = ++ cp;
	len[now] = len[pre] + 1;
	memset(ch[now], 0, sizeof ch[now]);
	while (pre and !ch[pre][x]) ch[pre][x] = now, pre = fa[pre];
	if (pre) {
		int preto = ch[pre][x];
		if (len[preto] == len[pre] + 1) fa[now] = preto;
		else {
			int sp = ++ cp;
			len[sp] = len[pre] + 1;
			fa[sp] = fa[preto];
			memcpy(ch[sp], ch[preto], sizeof ch[sp]);
			while (pre and ch[pre][x] == preto) ch[pre][x] = sp, pre = fa[pre];
			fa[now] = fa[preto] = sp;
		}
	} else fa[now] = rt;
	return now;
}

void dfs (int u, int n) {
	for (int v : G[u]) {
		dfs(v, n);
		merge(seg[u], seg[v], 1, n);
	}
}

int main () {
#ifndef LOCAL
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
#endif

	scanf("%s", s + 1);
	int n = int(strlen(s + 1));
	for (int i = 1, las = 1; i <= n; i ++) {
		las = insert(1, las, s[i] - 'a');
		lain(seg[las], 1, n, i);
	}
	for (int i = 2; i <= cp; i ++)
		G[fa[i]].push_back(i);
	dfs(1, n);

	tpos[0] = ++ cp;

	int q = read;
	while (q --) {
		scanf("%s", t + 1);
		int l = read, r = read, m = int(strlen(t + 1));
		cp = tpos[0];
		memset(ch[cp], 0, sizeof ch[cp]);
		for (int i = 1; i <= m; i ++)
			tpos[i] = insert(tpos[0], tpos[i - 1], t[i] - 'a');
		std::fill(vis + tpos[0], vis + cp + 1, 0);

		ll ans = 0;
		for (int i = 1, u = 1, le = 0; i <= m; i ++) {
			int x = t[i] - 'a';
			while (u and !ch[u][x]) u = fa[u], le = len[u];
			if (u) u = ch[u][x], ++ le;
			else u = 1;
			int R = query(seg[u], 1, n, l, r);
			while (!R or R - l + 1 <= len[fa[u]])
				u = fa[u], le = len[u], R = query(seg[u], 1, n, l, r);
			le = R ? std::min(le, R - l + 1) : 0;
			int v = tpos[i], vlen = len[v], flen = vlen;
			while (!vis[v]) vis[v] = 1, v = fa[v], flen = len[v];
			ans += vlen - std::max(flen, le);
		}
		printf("%lld\n", ans);
	}
}

屠龙勇士

注意到每条龙使用的剑是完全确定的，所有限制都是同余方程，直接 exCRT/exgcd ，但是会爆 long long ，需要非常注意，在特定地方使用快速乘。

还要注意剑的攻击力可能相同，用 std::multiset 存储而不是 std::set 。

出题人的意图可能是要考察选手对代码细节的掌控？反正我是调了好久。

int main () {
#ifndef LOCAL
	freopen("dragon.in", "r", stdin);
	freopen("dragon.out", "w", stdout);
#endif

	int T = read;
	while (T --) {
		int n = read, s = read;
		for (int i = 1; i <= n; i ++) read(a[i]);
		for (int i = 1; i <= n; i ++) read(p[i]);
		for (int i = 1; i <= n; i ++) read(aw[i]);
		std::multiset<ll> set;
		while (s --) set.insert(read);

		ll min = 0, B = 0, M = 1;
		for (int i = 1; i <= n; i ++) {
			auto it = set.upper_bound(a[i]);
			if (it != set.begin()) -- it;
			int t = int(*it);
			set.erase(it);
			set.insert(aw[i]);

			if (!p[i]) return 0;
			ll x, y, g = exgcd(t, p[i], x, y);
			if (a[i] % g) goto fail;
			ll m = p[i] / g, b = mul(x, a[i] % p[i] / g, m);
			if (b < 0) b += m;

			g = exgcd(m, M, x, y);
			ll d = B - b;
			if (d % g) goto fail;
			d /= g;
			M *= m / g;
			B = (b + mul(mul(x, m, M), d, M)) % M;
			if (B < 0) B += M;

			min = std::max(min, (a[i] + t - 1) / t);
		}

		if (B < min) {
			ll d = (min - B + M - 1) / M;
			B += d * M;
		}
		printf("%lld\n", B);

		continue;
fail:
		puts("-1");
	}
}

情报中心

观察了下数据表，意识到这题要拿部分分必须从特殊性质下手。

暴力直接 \(O(n^3)\) 该咋枚举咋枚举，15 分。

链的话可以正反来两次扫描线，由于每条边都是非负权值，算入一个的少了边的方案不会影响答案，15 分。

\(c_i=0\) 就只要考虑路径的代价，枚举每一条边，用 set 启发式合并求出经过每条边最小的两条路径，15 分。

剩下两个 \(S_1, S_2\) 实在是写不动了。

大样例确实很给力，但是这部分分必须一个一个写，每个部分分的分值不高，太难受了。

namespace FORCE {
	const int maxn = 305;
	std::bitset<maxn> bs[maxn], bm[maxn];
	ll main (int n, int m) {
		for (int u = 2; u <= n; u ++) {
			bs[u] = bs[fa[u]];
			bs[u].set(si(u));
		}
		for (int i = 1; i <= m; i ++)
			bm[i] = bs[ma[i]] ^ bs[mb[i]];
		ll ans = -inf;
		for (int i = 1; i <= m; i ++)
			for (int j = 1; j < i; j ++) {
				if ((bm[i] & bm[j]).any()) {
					std::bitset<maxn> b = bm[i] | bm[j];
					ll now = - mc[i] - mc[j];
					for (int k = 1; k <= n; k ++)
						if (b.test(si(k)))
							now += fw[k];
					ans = std::max(ans, now);
				}
			}
		return ans;
	}
};

namespace CHAIN {
	std::vector<int> ve[maxn];
	ll s[maxn];
	ll bit[maxn];
	void modify (int p, int n, ll x) {
		for (int k = p; k <= n; k += k & -k)
			bit[k] = std::max(bit[k], x);
	}
	ll query (int p) {
		ll res = -inf-inf;
		for (int k = p; k; k -= k & -k)
			res = std::max(res, bit[k]);
		return res;
	}
	ll main (int n, int m) {
		for (int i = 2; i <= n; i ++) s[i] = s[i - 1] + fw[i];
		for (int i = 1; i <= n; i ++) ve[i].clear();
		for (int i = 1; i <= m; i ++) {
			if (ma[i] > mb[i]) std::swap(ma[i], mb[i]);
			/* mc[i] += s[mb[i]] - s[ma[i]]; */
			ve[mb[i]].push_back(i);
		}
		for (int R = 1; R <= n; R ++)
			std::sort(ve[R].begin(), ve[R].end(), [] (int i, int j) {
						return ma[i] > ma[j];
					});
		std::fill(bit, bit + n + 1, -inf-inf);
		ll ans = -inf;
		for (int R = 1; R <= n; R ++)
			for (int i : ve[R]) {
				ans = std::max(ans, -mc[i] + s[mb[i]] - s[ma[i]] + query(n - ma[i]));
				modify(n - ma[i], n, -mc[i]);
			}
		std::fill(bit, bit + n + 1, -inf-inf);
		for (int R = n; R; R --)
			for (int i : ve[R]) {
				ans = std::max(ans, -mc[i] - s[ma[i]] + query(mb[i] - 1));
				modify(ma[i], n, -mc[i] + s[mb[i]]);
			}
		return ans;
	}
};

namespace C0 {
	const int maxk = 20, Maxk = 18;
	std::multiset<ll> a[maxn], b[maxn];
	int fa[maxk][maxn], deep[maxn];
	int lca (int x, int y) {
		if (deep[x] < deep[y]) std::swap(x, y);
		for (int k = Maxk - 1; k >= 0; k --)
			if (deep[fa[k][x]] >= deep[y])
				x = fa[k][x];
		if (x == y) return x;
		for (int k = Maxk - 1; k >= 0; k --)
			if (fa[k][x] != fa[k][y])
				x = fa[k][x], y = fa[k][y];
		return ::fa[x];
	}
	ll main (int n, int m) {
		for (int u = 1; u <= n; u ++) {
			deep[u] = deep[::fa[u]] + 1;
			fa[0][u] = ::fa[u];
			for (int k = 1; k < Maxk; k ++) fa[k][u] = fa[k - 1][fa[k - 1][u]];
		}
		for (int u = n; u; u --) a[u].clear(), b[u].clear();
		for (int i = 1; i <= m; i ++) {
			a[ma[i]].insert(mc[i]);
			a[mb[i]].insert(mc[i]);
			int c = lca(ma[i], mb[i]);
			b[c].insert(mc[i]);
			b[c].insert(mc[i]);
		}
		ll ans = inf;
		for (int u = n; u; u --) {
			for (int v : G[u]) {
				if (a[v].size() > a[u].size()) std::swap(a[u], a[v]);
				for (ll x : a[v]) a[u].insert(x);
			}
			for (ll x : b[u]) a[u].erase(a[u].find(x));
			if (a[u].size() >= 2)
				ans = std::min(ans, *a[u].begin() + *(++a[u].begin()));
		}
		return -ans;
	}
};

int main () {
	int T = read;
	while (T --) {
		++ Case;
		int n = read;
		for (int u = 1; u <= n; u ++) G[u].clear();
		bool _chain = 1, _c0 = 1;
		for (int i = 1; i < n; i ++) {
			int a = read, b = read;
			G[fa[b] = a].push_back(b);
			read(fw[b]);
			_chain &= a == b - 1;
			_c0 &= fw[b] == 0;
		}
		int m = read;
		for (int i = 1; i <= m; i ++) {
			read(ma[i], mb[i], mc[i]);
			if (ma[i] == mb[i]) -- i, -- m;
		}
		ll ans;
		if (_chain) ans = CHAIN::main(n, m);
		else if (_c0) ans = C0::main(n, m);
		else ans = FORCE::main(n, m);
		if (ans == -inf) puts("F");
		else printf("%lld\n", ans);
	}
}

看了看知乎这题现场最高 45 分？

多边形

啊这，完全没有思路？想了几个小时都没想出 \(K=1\) 的正确做法。认输了，写个爆搜，只有 15 分。

void dfs (int u) {
	if (G[u].empty()) return le[++ lp] = u, void();
	std::sort(G[u].begin(), G[u].end());
	for (int v : G[u]) dfs(v);
}

ll ans = 0;
void force (int u, int n) {
	if (n == 1) {
		for (int v : G[u])
			if (v == 1)
				++ ans;
		return;
	}
	vis[u] = 1;
	for (int v : G[u])
		if (!vis[v])
			force(v, n - 1);
	vis[u] = 0;
}

int main () {
#ifndef LOCAL
	freopen("polygon.in", "r", stdin);
	freopen("polygon.out", "w", stdout);
#endif

	int n = read, m = read;
	for (int u = 2; u <= n; u ++) G[fa[u] = read].push_back(u);
	dfs(1);
	for (int u = 2; u <= n; u ++) G[u].push_back(fa[u]);
	if (lp <= m * 2 + 1) {
		for (int i = 1; i <= lp; i ++)
			for (int j = 1; j <= lp; j ++)
				if (j != i)
					G[le[i]].push_back(le[j]);
	} else {
		for (int i = 1; i <= lp; i ++) le[lp + i] = le[i];
		for (int i = 1; i <= lp; i ++)
			for (int j = i + 1; j <= i + m; j ++) {
				G[le[i]].push_back(le[j]);
				G[le[j]].push_back(le[i]);
			}
	}
	force(1, n);
	printf("%lld\n", ans >> 1);
}

妈的看来我树论完全不行啊，两道树题都没啥分，CSP 也吃了这个亏。

看了看别人写的题解发现 \(K=1\) 竟然是一个被我毙掉的做法，\(O(2^3 n)\) 的树形 DP ？

看了看知乎这题现场最高 50 分？（暴力 + \(K=1\) ）。

NOI2019

0 + 100 + 60 + 40 + 88 + 70 + 36 = 394

集训队线 477 。

回家路线

不难想到对于路线设计一个 DP \(f_i\) 表示使用到第 \(i\) 条路线的最小代价。朴素转移要枚举起点上所有的路线。

考虑对于当前从 \(p\) 开始的第 \(i\) 条路径，如果从一个 \(q\) 结束，代价为 \(t\) 的路线转移，那么转移要最小化

\[A(p-q)^2 + B(p-q) + C + t\]

整理得到

\[(Ap^2 + Bp + C) + (Aq^2 - Bq + t) - (2Aq) p\]

第一个括号里面只与 \(p\) 有关，后面两个括号只与 \(p, t\) 有关，可以发现需要最小化的就是用斜率为 \(p\) 的直线截 \((2Aq, Aq^2 - Bq + t)\) 得到的截距。

那么用个凸包维护转移即可。

凸包里面要维护点的双端队列，我第一次写的时候在右移左端点的同时还左移了右端点，这么大的错竟然还能得 90 分？

const int maxt = 1005, maxn = 200005;
const int Maxt = 1000, inf = 2000000000;

struct route { int s, t, p, q, id; };
struct T { int x, y; };
T operator - (T a, T b) { return {a.x - b.x, a.y - b.y}; }
ll cross (T a, T b) { return 1ll * a.x * b.y - 1ll * a.y * b.x; }

struct Hull {
	std::vector<T> st;
	size_t b;
	static int q (T p, int k) { return p.y - k * p.x; }
	int query (int k) {
		if (b >= st.size()) return inf;
		while (b + 1 < st.size() and q(st[b + 1], k) <= q(st[b], k))
			++ b;
		return q(st[b], k);
	}
	void add (T p) {
		auto sp = st.size();
		if (sp and st[sp - 1].x == p.x and st[sp - 1].y < p.y) return;
		while (sp >= b + 2 and cross(st[sp - 1] - st[sp - 2],
					p - st[sp - 1]) <= 0) st.pop_back(), -- sp;
		st.push_back(p), ++ sp;
	}
};

std::vector<route> qu[maxt], ad[maxt];
int f[maxn];
Hull h[maxn];

int main () {
#ifndef LOCAL
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
#endif

	int n = read, m = read, A = read, B = read, C = read;
	for (int i = 1; i <= m; i ++) {
		int s = read, t = read, p = read, q = read;
		qu[p].push_back({s, t, p, q, i});
		ad[q].push_back({s, t, p, q, i});
		f[i] = inf;
	}

	int ans = inf;
	for (int t = 0; t <= Maxt; t ++) {
		for (route r : ad[t]) {
			if (r.s == 1) f[r.id] = A * r.p * r.p + B * r.p + C;
			if (f[r.id] < inf)
				h[r.t].add({2 * A * r.q, A * r.q * r.q - B * r.q + f[r.id]});
		}
		for (route r : qu[t]) {
			f[r.id] = h[r.s].query(r.p);
			if (f[r.id] < inf) f[r.id] += A * r.p * r.p + B * r.p + C;
			if (r.t == n and f[r.id] < inf) ans = std::min(ans, f[r.id] + r.q);
		}
	}

	printf("%d\n", ans);
}

机器人

不难想到设计一个区间 DP \(f_{l,r,m}\) 表示只考虑区间 \([l, r]\) ，所有值不超过 \(m\) 的合法方案有多少。转移枚举最靠右的最大值的位置，注意这个位置的数量是 \(O(1)\) 的，因此总复杂度 \(O(n^2B)\) ，可以得到 50 分。代码略。

对于 \(A, B\) 全部相等的情况，不难证明答案是关于 \(B - A + 1\) 的 \(n\) 次多项式。把 \(B - A + 1\) 从 \(0\) 到 \(n\) 的答案都通过上述 DP 算出来再拉格朗日插值即可，结合上述做法可以得到 60 分。

void dp (int n, int lim) {
	for (int i = 1; i <= n + 1; i ++) f[i][i - 1] = 1;
	for (int x = 1; x <= lim; x ++) {
		for (int l = 1; l <= n; l ++) {
			if (L[l] <= x and x <= R[l]) ++ f[l][l];
			for (int r = l + 1; r <= n; r ++) {
				int lm = (l + r - 1) >> 1, rm = (l + r + 2) >> 1;
				for (int i = lm; i <= rm; i ++)
					if (L[i] <= x and x <= R[i])
						(f[l][r] += f[l][i - 1] * f[i + 1][r]) %= mod;
			}
		}
		tmp[x] = f[1][n];
	}
}

ll lage (int n, int W) {
	ll res = 0;
	for (int i = 0; i <= n; i ++) {
		ll now = tmp[i];
		for (int j = 0; j <= n; j ++)
			if (j != i) {
				(now *= mod + W - j) %= mod;
				(now *= power(mod + i - j, -1)) %= mod;
			}
		res += now;
	}
	return res % mod;
}

int main () {
#ifndef LOCAL
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);
#endif

	int n = read, W = 1000000000, test = 1;
	for (int i = 1; i <= n; i ++) read(L[i], R[i]), test &= L[i] == 1 and R[i] == W;
	if (test)
		dp(n, n), printf("%lld\n", lage(n, W));
	else
		dp(n, 10000), printf("%lld\n", tmp[10000]);
}

序列

第一眼不难想到一个 \(O(n^4)\) 的 DP ，设 \(f_{i,j,k,p}\) 表示考虑前 \(i\) 个，\(a,b,ab\) 分别选了 \(j,k,p\) 个，应该可以得到 28 分。

但不难发现如果确定了 \(L\) 个 \(ab\) 的选择，那么剩下的就是从大到小选，不妨假定 \(a\) 单调不增，此时 DP 状态就没必要记录 \(j\) 了，可以得到 40 分。

int main () {
	int T = read;
	while (T --) {
		int n = read, K = read, L = read;
		for (int i = 1; i <= n; i ++) read(p[i].first);
		for (int i = 1; i <= n; i ++) read(p[i].second);
		std::sort(p + 1, p + n + 1, std::greater<par>());
		for (int i = 1; i <= n; i ++) {
			for (int j = 0; j <= i and j <= L; j ++)
				for (int k = 0; j + k <= i and k <= K - L; k ++) {
					int a = i + L - j <= K ? p[i].first : 0;
					f[i][j][k] = f[i - 1][j][k] + a;
					if (j) chkmax(f[i][j][k], f[i - 1][j - 1][k] + p[i].first + p[i].second);
					if (k) chkmax(f[i][j][k], f[i - 1][j][k - 1] + a + p[i].second);
				}
		}
		printf("%lld\n", f[n][L][K - L]);
	}
}

更高的分就不会了，写了个假贪心，样例都过不了。

去年同步赛还写了这题 60 分，今年完全想不到 \(O(n^2)\) 做法？

正解大概是个模拟费用流吧。

弹跳

题目显然是个最短路模型，需要优化建图，直接用 KDTree 松弛即可，空间线性。但是矩形查询的复杂度是根号的？只能跑 88 分。

const int maxn = 70005;
struct path { int w, L[2], R[2]; };
struct KDT {
	int lti, rti;
	int p[2], min[2], max[2];
} pool[maxn];
#define self pool[now]
#define lt pool[self.lti]
#define rt pool[self.rti]
int tmp[maxn];
int dis[maxn << 1];
std::vector<path> G[maxn];

int cmp_d;
bool cmp (int a, int b) { return pool[a].p[cmp_d] < pool[b].p[cmp_d]; }

int build (int l, int r, int d) {
	if (l > r) return 0;
	int mid = (l + r) >> 1;
	cmp_d = d; // XXX: 卧槽，这都能忘？
	std::nth_element(tmp + l, tmp + mid, tmp + r + 1, cmp);
	int now = tmp[mid];
	self.lti = build(l, mid - 1, d ^ 1);
	self.rti = build(mid + 1, r, d ^ 1);
	self.min[0] = std::min({self.p[0], lt.min[0], rt.min[0]});
	self.max[0] = std::max({self.p[0], lt.max[0], rt.max[0]});
	self.min[1] = std::min({self.p[1], lt.min[1], rt.min[1]});
	self.max[1] = std::max({self.p[1], lt.max[1], rt.max[1]});
	return now;
}

std::priority_queue<par> q;
int N, TOT;
int L[2], R[2];
void _relax (int u, int di) {
	if (di < dis[u]) {
		dis[u] = di;
		q.push(par(-di, u));
	}
}
void relax (int now, int di) {
	++ TOT;
	if (R[0] < self.min[0] or L[0] > self.max[0] or
			R[1] < self.min[1] or L[1] > self.max[1]) return;
	if (L[0] <= self.min[0] and self.max[0] <= R[0] and
			L[1] <= self.min[1] and self.max[1] <= R[1])
		return _relax(now, di);
	if (L[0] <= self.p[0] and self.p[0] <= R[0] and
			L[1] <= self.p[1] and self.p[1] <= R[1])
		_relax(now + N, di);
	relax(self.lti, di);
	relax(self.rti, di);
}

int main () {
#ifndef LOCAL
	freopen("jump.in", "r", stdin);
	freopen("jump.out", "w", stdout);
#endif

	read(N);
	int M = read;
	pool[0].min[0] = read;
	pool[0].min[1] = read;
	pool[0].max[0] = 1;
	pool[0].max[1] = 1;

	for (int now = 1; now <= N; now ++) {
		read(self.p[0], self.p[1]);
		tmp[now] = now;
	}
	for (int i = 1; i <= M; i ++) {
		int s = read, w = read, l = read, r = read, d = read, u = read;
		G[s].push_back({w, {l, d}, {r, u}});
	}

	int root = build(1, N, 0);
	std::fill(dis, dis + N + N + 1, 2000000000);
	q.push(par(dis[N + 1] = 0, N + 1));
	while (!q.empty()) {
		int now = q.top().second, d = q.top().first;
		q.pop();
		if (d > dis[now]) continue;
		if (now > N) {
			int u = now - N;
			for (path p : G[u]) {
				L[0] = p.L[0];
				L[1] = p.L[1];
				R[0] = p.R[0];
				R[1] = p.R[1];
				/* int bak = TOT; */
				relax(root, dis[now] + p.w);
				/* debug("%d\n", TOT - bak); */
			}
		} else {
			if (self.lti) _relax(self.lti, dis[now]);
			if (self.rti) _relax(self.rti, dis[now]);
			_relax(now + N, dis[now]);
		}
	}

	for (int i = 2; i <= N; i ++)
		printf("%d\n", dis[N + i]);
}

斗主地

仔细分析洗牌的选牌概率，事实上这个洗牌就是在保证相对顺序的前提下的均匀随机打乱。

暴力计算出第 \(i\) 个位置洗牌后到第 \(j\) 个位置的概率构成的矩阵，然后作矩阵乘法，统计答案，可以得到 40 分。

mat make (int x) {
	mat a;
	for (int i = 1; i <= x; i ++)
		for (int j = 1; j <= N; j ++)
			a.x[i][j] = C(j - 1, i - 1) * C(N - j, x - i) % mod * iC(N, x) % mod;
	for (int i = x + 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			a.x[i][j] = C(j - 1, i - x - 1) * C(N - j, N - i) % mod * iC(N, x) % mod;
	return a;
}

int main () {
#ifndef LOCAL
	freopen("landlords.in", "r", stdin);
	freopen("landlords.out", "w", stdout);
#endif

	read(N);
	int m = read, t = read;
	bool same = 1;
	for (int i = 1; i <= m; i ++) read(A[i]), same &= A[i] == A[1];

	if (N > 100) return 1;

	fac[0] = 1;
	for (int i = 1; i <= N; i ++) fac[i] = fac[i - 1] * i % mod;
	ifac[N] = power(fac[N], -1);
	for (int i = N; i; i --) ifac[i - 1] = ifac[i] * i % mod;

	mat P;
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			P.x[i][j] = i == j;

	if (same) {
		mat B = make(A[1]);
		while (m) {
			if (m & 1) P *= B;
			B *= B;
			m >>= 1;
		}
	} else
		for (int i = 1; i <= m; i ++)
			P *= make(A[i]);

	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			(ans[j] += P.x[i][j] * ll(t == 1 ? i : i * i)) %= mod;

	int q = read;
	while (q --)
		printf("%lld\n", ans[int(read)]);
}

打个表找找规律，可以惊奇地发现 \(t=1\) 时无论怎样洗牌，最后的答案序列始终是等差数列！由于该等差数列的和始终不变，只需要考虑维护它的公差。再找找规律，又可以惊奇地发现一个参数为 \(X\) 的洗牌就是把公差乘上 \(\frac{\binom{N-2}{X}+\binom{N-2}{X-2}}{\binom{N}{X}}\) ！结合上面的暴力做法可以得到 70 分。

以下代码只有 \(t=1\) 的部分。

int main () {
#ifndef LOCAL
	freopen("landlords.in", "r", stdin);
	freopen("landlords.out", "w", stdout);
#endif

	read(N);
	int m = read, t = read;
	bool same = 1;
	for (int i = 1; i <= m; i ++) read(A[i]), same &= A[i] == A[1];

	fac[0] = 1;
	for (int i = 1; i <= N; i ++) fac[i] = fac[i - 1] * i % mod;
	ifac[N] = power(fac[N], -1);
	for (int i = N; i; i --) ifac[i - 1] = ifac[i] * i % mod;
	ll coe = 1;

	ll d = 1;
	for (int i = 1; i <= m; i ++) {
		(d *= C(N - 2, A[i]) + C(N - 2, A[i] - 2)) %= mod;
		(d *= iC(N, A[i])) %= mod;
	}
	ll rem = 1ll * N * (N + 1) / 2;
	for (int i = 1; i <= N; i ++)
		ans[i] = i * d % mod, rem += mod - ans[i];
	rem = rem % mod * power(N, -1) % mod;
	for (int i = 1; i <= N; i ++)
		(ans[i] += rem) %= mod;

	int q = read;
	while (q --)
		printf("%lld\n", ans[int(read)] * coe % mod);
}

可以进一步做出猜想，\(t=2\) 时无论怎么洗牌答案序列始终是二次多项式。但是探究一次洗牌对该二次多项式的影响就很诡异，远远不是一个乘积那么简单？

I 君的探险

容易想到暴力修改每个点然后逐一验证每条边，操作实现得精细一点就可以得到 20 分。

接下来对于 A 部分，这个图是个匹配，容易想到二进制分组，对于每个二进制只修改一半的点，通过查询就可以直到每个点的匹配点在该二进制位对应的值。这个部分不卡交互次数的常数，顺手。结合上一个部分一共 36 分。

const int maxn = 200000;

namespace FORCE {
	const int maxn = 500;
	bool las[maxn];
	bool link[maxn][maxn];
	void main (int n, int) {
		for (int i = 0; i < n - 1; i ++) {
			modify(i);
			for (int j = 0; j <= i; j ++)
				if (link[j][i] or j == i)
					las[j] ^= 1;
			for (int j = i + 1; j < n; j ++) {
				bool now = query(j);
				if (now != las[j])
					link[i][j] = 1, report(i, j);
				las[j] = now;
			}
		}
	}
};

namespace MATCH {
	int match[maxn];
	void main (int n, int) {
		for (int k = 0; (1 << k) < n; k ++) {
			for (int i = 0; i < n; i ++) if (i >> k & 1) modify(i);
			for (int i = 0; i < n; i ++)
				if (query(i) != (i >> k & 1))
					match[i] |= 1 << k;
			for (int i = 0; i < n; i ++) if (i >> k & 1) modify(i);
		}
		for (int i = 0; i < n; i ++)
			if (i < match[i])
				report(i, match[i]);
	}
};

void explore (int n, int m) {
	if (n % 10 == 8) MATCH::main(n, m);
	else FORCE::main(n, m);
}

B 部分那个感觉可以来个二分什么的，因为对一个前缀进行修改操作，就可以直到一个后缀的父亲是否在这段前缀里头。

End

怎么说呢，感觉题目一年比一年难，分数线却一年比一年高。感觉完全不在线，拿不到分。况且今年的选手看起来强得离谱，感觉要去送了？