2025.4.8 dmy NOI模拟赛总结(转化贡献方式 dp， 交互(分段函数找断点)，SAM上计数)

时间安排

先写了 $T3$ $60pts$，然后剩下 $2.5h$ 没有战胜 $T1$ $40pts$。
总得分： 20 + 0 + 40 = 60。

反思：先做自己比较擅长或者更好拿分的题还是很重要的。这场 $T1$ 确实困难。。。

题解

T1.搬箱子(dp，转化贡献方式)

有 $N$ 个箱子排成一行，从左到右依次编号为 $1$ 到 $N$。
另外，有 $N$ 个编号为 $1$ 到 $N$ 的包裹。每个包裹 $i$ 有重量 $W_i$，并且目前放在编号为 $A_i$ 的箱子中。
你的目标是使得每个箱子中恰好有一个包裹。
为此，你可以重复进行以下操作：

• 选择一个包裹，并将它移动到相邻的箱子中。
• 若被移动的包裹重量为 $w$，则此操作的代价为 $w$。

问达到目标的最小操作次数，并且在操作次数最小的前提下，总代价的最小值。

$1\le N\le 10^4,1\le A_i\le N,1\le W_i\le 10^9$

分析：
对于第一问：

求出前 $[1,i]$ 个箱子里包裹数的前缀和 $su{m}_i$，那么 $c_i=su{m}_i-i$ 就是 $i\to i+1$ 运走的包裹数量，如果为负那么反向。$\sum |c_i|$ 就是答案。

对于第二问：

由于要保证运送次数最少因此把 $c_i=0$ 的边断开，会形成若干段，每段内答案独立，分别求出后加起来即可。
若 $c_i>0$ 就加一条 $i\to i+1$ 的有向边，反之加一条 $i+1\to i$ 的有向边，那么不难发现每段内的结构为 存在一个中心点满足左侧的边都方向为左，右侧的边方向为右。

假设中心点在端点处，那么策略是固定的：假设在左端点，那么从左到右考虑移动包裹，每次放下当前 $w$ 最大的包裹，将其余包裹移到右边，将某个位置的包裹合并到之前的包裹后整体考虑。

中心点不在端点：
难点在于怎么将中心点处的包裹按照最优策略分到左右两边。发现一个箱子最后的停留的位置只跟 $w$ 比它的箱子有关，因此考虑一个在值域上的 $dp$： $d{p}_{i,j}$ 表示从按照 $w$ 大到小考虑段内的箱子，已经考虑了前 $i$ 大，中心点的箱子有 $j$ 个划分到左边的最优答案，模拟一边移箱子的过程就可以知道第 $i$ 大箱子的落点和花费。或许能做到 $O(n^3)$，但是不好优化。

按 $w$ 从小到大考虑每个箱子的落点。只看中心点左侧，假设我们已经知道了中心点向左移动的箱子编号。设 $f_i$ 表示 当前 $i$ 号点还要往 $i-1$ 运几个箱子。那么最优策略等价于 每次找到 $w$ 最小的箱子所在位置 $p$，向左找到第一个 $f_x=0$ 的位置 $x$， 将这个箱子移到 $x$，然后将 $[x+1,p]$ 的 $f$ 减 1 。画图理解这样是对的，那么可以将 $d{p}_{i,j}$ 的转移变成从小到大。这样有一个比较好的性质是 当考虑到第 $i$ 小的箱子时，此时 $f_i$ 的状态只和前 $i-1$ 个箱子的位置有关，与它们的移动顺序无关。也就是无论按怎样的顺序移动这些箱子，都能得到相同 $f$ 状态。

那么现在的问题在于 $O(1)$ 求出已经移动过前 $i-1$ 小的箱子，且中心点往左边移过来了 $j$ 个箱子后，第 $i$ 小箱子的落点。这个可以通过每次移动非中心点箱子时 $O(n)$ 重构 $f$ 状态并预处理一些信息后 $O(1)$ 算出来。时间复杂度 $O(N^2)$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
const LL INF = 1e17;
int n, a[N], cnt[N], sum[N];
int eg[N]; 
LL w[N], ret, ans, dp[N][N]; // dp[i][j] 表示 从小到大考虑了前 i 个，中心位置往左边运了 j 个， 往右边运了剩下的答案 
vector< int > hav[N];
int f[N], g[N]; // f[i] 表示 i 还要左运几次， g[i] 表示 i 还要往右运几次 
int to[N], bel[N];
int pl[N], pr[N], cl, cr;
int odr[N], tot, pre[N];
inline bool cmp(int x, int y) {return w[x] < w[y];}
inline LL ml(int x, int y, LL w) {return x >= y ? (x - y) * w : INF;}
inline LL mr(int x, int y, LL w) {return y >= x ? (y - x) * w : INF;}
inline int Fl(int x, int k, int s) { // 已经往左移动了 k 个  if(x == s) return k >= cl ? n + 1 : pl[k + 1];else {if(x < pl[1]) return to[x]; // 独立的 return bel[x] <= k ? to[x] : pl[k + 1];}
}
inline int Fr(int x, int k, int s) { // 已经往右移动第 k 个 if(x == s) return k >= cr ? 0 : pr[k + 1];else {if(x > pr[1]) return to[x];return bel[x] <= k ? to[x] : pr[k + 1];}
}
inline void move(int p, int l, int r, int s) {if(p == 0) {for(int i = s; i >= l; i -- ) f[i] = -eg[i - 1];for(int i = s; i <= r; i ++ ) g[i] = eg[i];}else {	if(a[odr[p]] == s) return ;else if(a[odr[p]] < s) { // 往左推平 for(int i = a[odr[p]]; i >= l; i -- ) {if(f[i] == 0) break;f[i] --;}}else { // 往右推平 for(int i = a[odr[p]]; i <= r; i ++ ) {if(g[i] == 0) break;g[i] --;}}}// 重构， 首先不同的 0 会划分出若干段 cl = f[s], cr = g[s];for(int i = 1; i <= cl + 1; i ++ ) pl[i] = -1;for(int i = 1; i <= cr + 1; i ++ ) pr[i] = n + 1;for(int i = s; i >= l; i -- ) if(i != s && pl[f[i] + 1] == -1) pl[f[i] + 1] = i;for(int i = s; i <= r; i ++ ) if(i != s && pr[g[i] + 1] == n + 1) pr[g[i] + 1] = i;int last = -1;for(int i = l; i < pl[1]; i ++ ) {if(f[i] == 0) last = i;to[i] = last;}for(int i = 1; i <= cl; i ++ ) { // 每一段  前面第一个 iint last = -1; int ed = (i == cl ? s : pl[i + 1]);for(int j = pl[i]; j < ed; j ++ ) {if(f[j] == i) last = j;bel[j] = i; to[j] = (last == -1 ? n + 1 : last);}} last = -1;for(int i = r; i > pr[1]; i -- ) {if(g[i] == 0) last = i;to[i] = last;}for(int i = 1; i <= cr; i ++ ) {int last = -1; int ed = (i == cr ? s : pr[i + 1]);for(int j = pr[i]; j > ed; j -- ) {if(g[j] == i) last = j;bel[j] = i; to[j] = (last == -1 ? 0 : last);}}
} 
inline LL solve(int l, int r) { // 每一段算答案 int s = -1; // 找重心点 for(int i = l; i <= r; i ++ ) if(i == r || eg[i] > 0) {s = i; break;}tot = 0;for(int i = l; i <= r; i ++ ) for(auto v : hav[i]) odr[++ tot] = v;sort(odr + 1, odr + tot + 1, cmp);for(int i = tot; i >= 1; i -- ) {if(a[odr[i]] == s) { // 把最大的留下 for(int j = i + 1; j <= tot; j ++ ) odr[j - 1] = odr[j];break;}}tot --;for(int i = 1; i <= tot; i ++ ) pre[i] = pre[i - 1] + (a[odr[i]] == s);for(int i = 0; i <= tot; i ++ ) for(int j = 0; j <= cnt[s] - 1; j ++ )dp[i][j] = INF;dp[0][0] = 0; move(0, l, r, s); // 移动并获得当前局面 for(int i = 1; i <= tot; i ++ ) { // 考虑第 i 小的移动 for(int j = 0; j <= pre[i - 1]; j ++ ) { // 枚举之前中心点移动了几个 if(a[odr[i]] < s) { // 左边 dp[i][j] = min(dp[i][j], dp[i - 1][j] + ml(a[odr[i]], Fl(a[odr[i]], j, s), w[odr[i]]));}else if(a[odr[i]] > s) { // 右边 dp[i][j] = min(dp[i][j], dp[i - 1][j] + mr(a[odr[i]], Fr(a[odr[i]], pre[i - 1] - j, s), w[odr[i]]));}else { // 枚举左边还是右边 dp[i][j] = min(dp[i][j], dp[i - 1][j] + mr(s, Fr(s, pre[i - 1] - j, s), w[odr[i]])); // 移到右边dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j] + ml(s, Fl(s, j, s), w[odr[i]])); }}move(i, l, r, s);}return dp[tot][-eg[s - 1]];
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%d", &a[i]);cnt[a[i]] ++; hav[a[i]].pb(i);}for(int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + cnt[i];for(int i = 1; i < n; i ++ ) {eg[i] = sum[i] - (i); // i 往 i + 1 运的数量 ret += abs(eg[i]);}for(int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);for(int i = 1; i <= n;) {int j = i;while(eg[j] && j <= n) j ++;ans += solve(i, j);i = j + 1;}cout << ret << ' ' << ans << endl;return 0;
}

T2.很多线。(分段函数找断点)

题意：
交互题。
有 $N$ 条直线，你需要通过不超过 $4N+2$ 次询问某个点到这些直线的距离和来求出所有直线的解析式。

$N\le 100,|a_i|,|b_i|\le 10000$，保证 $a_i$ 两两不同。

分析：
并不会正解，但还是记录一下套路的部分分做法吧。
列出点到直线的距离公式，发现当固定 $x$ 时，距离就是关于 $y$ 的一次绝对值函数，相当于分了两段。那么距离和就是关于 $y$ 的分段函数。具体来说分了 $N$ 段，每段的断点为 $a_{i}x+b_i$。
取 $x=x_0>20000$，那么此时所有断点是两两不同的，只需要根据斜率二分求出所有断点就能求出所有直线解析式。
因此可以做到询问数为 $N{\log }_{2}V$。

T3.很多串。(SAM， 计数)

你有两个小写字母串 $S,T$。令 $f(S)$ 表示 $S$ 中所有不同的非空子串形成的集合，$f(T)$ 表示 $T$ 中所有不同的非空子串形成的集合。令 $G$ 表示所有 $s\in f(S),t\in f(T)$，$s+t$ 形成的多重集。问 $G$ 中字典序第 $k$ 小的是什么串。
注意，如果存在不同的 $s,t$，它们连接的 $s+t$ 是相同的，在 $G$ 中仍然被算多次。

$1\le |S|,|T|\le 75000,1\le k\le |G|$。

分析：
套路的，考虑 按位确定。那么只需要每次 $O(1)$ 求出 $G$ 中有多少个串 小于 当前的答案串，就可以在 $O((|S|+|T|)\times 26)$ 的复杂度解决问题，乘 $26$ 是因为要枚举字符。
肯定是要先建出 $SAM$ 的。
假设当前的答案串为 $S^{\prime }$，我们要往后面加一个字符 $c$，并且假设我们已经求出了 $G$ 中小于 $S^{\prime }$ 的串的数量为 $res$。
那么只需要求出有多少个串 $T$ 满足 前 $|S^{\prime }|$ 个字符与 $S^{\prime }$ 相等，后面部分小于 $c$。
对两部分计算答案：

1. 在拼接的两部分中 $s$ 已经小于了 $S^{\prime }+c$，那么需要 $S^{\prime }$ 是 $S$ 的子串。
   假设 $S^{\prime }$ 在 $S$ 的 $SAM$ 中对应节点 $p$，那么这一部分的答案为 ${\sum }_{j<c}S.f_{nod{e}_{p,j}}\times (T.f_1-1)$。其中 $T.f_p$ 表示 $T$ 的 $SAM$ 中以 $p$ 节点为起点的路径条数。
2. 在拼接的两部分中 $s$ 等于 $S^{\prime }$ 的一个前缀，$t$ 小于后半部分。
   设 $S^{\prime }$ 最长能成为 $S$ 子串的前缀长度为 $sl$，能成为 $t$ 子串的最长后缀长度为 $mxl$，那么首先需要 $sl+mxl\ge |S^{\prime }|$ 才有答案。也就是 $S$ 和 $T$ 首先能把 $S^{\prime }$ 拼出来。那么枚举 $t$ 拼出 $S^{\prime }$ 那一部分的长度 $l$，不难发现 $l\in [|S^{\prime }|-sl,mxl]$。有一个 $corner$ 是 $mxl=|S^{\prime }|$ 时需要让 $mxl$ 减 $1$(因为 $s$ 不能为空)。
   枚举 $l$，求出 $|S^{\prime }|$ 长为 $l$ 的后缀子串在 $|T|$ 的 $SAM$ 中对应的节点 $p$，只需要让答案加上 ${\sum }_{j<c}T.f_{nod{e}_{p,j}}$ 即可。发现 $p$ 对应了 $parent$ 树上的一段祖先链，考虑变成前缀和相减的形式：将原答案拆成 $l\in [0,mxl]$ 的答案减 $l\in [0,|S^{\prime }|-sl-1]$ 的答案。相当于是求 $Parent$ 树上某个点到根的路径的答案，有可能点在边上。显然可以预处理，那么计算答案就是 $O(1)$ 的。

预处理复杂度 $O(|T|\times 26)$，求解复杂度 $O((|S|+|T|)\times 26)$，总复杂度 $O((|S|+|T|)\times 26)$。
CODE：(好像写复杂了)

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const LL INF = LONG_LONG_MAX;
const int N = 76000;
int n, m, ans[N * 2], len;
char s[N], t[N];
LL K;
struct SAM {struct Node {int fa, len;int ch[26];} node[N * 2];bool vis[N * 2];LL f[N * 2], g[N * 2], h[N * 2]; // f[x] 表示以 x 为起点的路径数  g[x] 表示 x 等价类中所有字符串排名 - 1 之和  h[x] 表示 x 到根的 g[x] 之和 LL F[N * 2][26], G[N * 2][26]; // F[x][c] 表示 x 往 [0, c - 1] 转移的所有状态的路径数之和， G[x][c] 表示 x 到根路径上 F[p][c] * (mxlen_p - mnlen_p + 1) 的和 vector< int > E[N * 2];int in[N * 2], lst[N * 2][26]; // lst[x][i] 表示 i 在 parent 树上第一个有 c 出边的祖先 int tot = 1, last = 1;inline void extend(int c) {int p = last, np = last = ++ tot;node[np].len = node[p].len + 1;for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;if(!p) node[np].fa = 1;else {int q = node[p].ch[c];if(node[q].len == node[p].len + 1) node[np].fa = q;else {int nq = ++ tot;node[nq] = node[q]; node[nq].len = node[p].len + 1; node[q].fa = node[np].fa = nq;for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;}}}void dfs(int x) {if(vis[x]) return ;vis[x] = 1; f[x] = 1;LL tmp = 0;for(int i = 0; i < 26; i ++ ) {if(node[x].ch[i]) {dfs(node[x].ch[i]); f[x] += f[node[x].ch[i]];if(i < 25) F[x][i + 1] += f[node[x].ch[i]];}}for(int i = 1; i < 26; i ++ ) F[x][i] += F[x][i - 1];}void bfs() {queue< int > q; q.push(1);while(!q.empty()) {int u = q.front(); q.pop();LL tmp = g[u] + (node[u].len - node[node[u].fa].len);for(int j = 0; j < 26; j ++ ) {if(node[u].ch[j]) {int v = node[u].ch[j];in[v] --; g[v] += tmp; tmp += f[v];if(!in[v]) q.push(v);}}}}void Dfs(int x) {h[x] += g[x]; for(int i = 0; i < 26; i ++ ) G[x][i] += F[x][i] * (node[x].len - node[node[x].fa].len);for(int i = 0; i < 26; i ++ ) if(node[x].ch[i]) lst[x][i] = x;for(auto v : E[x]) {h[v] += g[x];for(int i = 0; i < 26; i ++ ) G[v][i] += G[x][i], lst[v][i] = lst[x][i];Dfs(v);}}inline void build(char *s) {int n = strlen(s + 1);for(int i = 1; i <= n; i ++ ) extend(s[i] - 'a');dfs(1); // 求出 f[x]for(int i = 1; i <= tot; i ++ ) E[node[i].fa].pb(i);for(int i = 1; i <= tot; i ++ ) for(int j = 0; j < 26; j ++ ) in[node[i].ch[j]] ++;bfs(); // 求 g[x] Dfs(1);}
} S, T;
inline void init(int c, int &sl, int &sp, int &mnp, int &mxl, int &mxp, LL &res, LL &mnr, LL &mxr) {if(sl == len) res += S.F[sp][c] * (T.f[1] - 1);// 还可以接   sp = S.node[sp].ch[c]; // 更新 spif(!sp) { // 来更新 mnp if(sl != len) {		int L = (len - sl - 1) - T.node[T.node[mnp].fa].len; // 在当前状态的长度 mnr += (len - sl - 1) + 1LL * L * T.F[mnp][c] + T.G[T.node[mnp].fa][c] + T.F[1][c]; // 增量mnp = T.node[mnp].ch[c];}}else sl ++;// 然后来更新 mxl 和 mxp, mxr if(mxp && !T.node[mxp].ch[c]) { // 需要找到parent 树上 mxp 第一个有 c 边的点， 没有返回 0int u = T.lst[mxp][c]; // 假设是 uif(mxp == 1) res += T.F[mxp][c];else res += mxr - T.h[T.node[mxp].fa] + (mxl - T.node[T.node[mxp].fa].len) * T.F[mxp][c] + (mxl - T.node[T.node[mxp].fa].len); // mxp 的贡献mxp = T.node[mxp].fa, mxl = T.node[mxp].len; mxr = T.h[mxp];if(mxp) {		res += T.h[mxp] - T.h[u] + T.G[mxp][c] - T.G[u][c] + T.node[mxp].len - T.node[u].len;if(u == 0) res += T.F[1][c];mxp = u; mxl = T.node[u].len; mxr = T.h[u];}}if(!mxp) mxp = 1; // 没了 else {int L = (mxl - T.node[T.node[mxp].fa].len);	mxr += mxl + 1LL * L * T.F[mxp][c] + T.G[T.node[mxp].fa][c] + T.F[1][c];mxl ++;mxp = T.node[mxp].ch[c];}	
}
inline LL calc(int c, int sl, int sp, int mnp, int mxl, int mxp, LL res, LL mnr, LL mxr) { // 往后边加 c, O(1) 计算答案 if(sl == len) res += S.F[sp][c] * (T.f[1] - 1);// 还可以接   sp = S.node[sp].ch[c]; // 更新 spif(!sp) { // 来更新 mnp if(sl != len) {		int L = (len - sl - 1) - T.node[T.node[mnp].fa].len; // 在当前状态的长度 mnr += (len - sl - 1) + 1LL * L * T.F[mnp][c] + T.G[T.node[mnp].fa][c] + T.F[1][c]; // 增量  不接 + 接更小的 mnp = T.node[mnp].ch[c];}if(!mnp) return INF;}else sl ++;if(sl == 0) return INF;// 然后来更新 mxl 和 mxp, mxr if(mxp && !T.node[mxp].ch[c]) { // 需要找到parent 树上 mxp 第一个有 c 边的点， 没有返回 0int u = T.lst[mxp][c]; // 假设是 uif(mxp == 1) res += T.F[mxp][c];else res += mxr - T.h[T.node[mxp].fa] + (mxl - T.node[T.node[mxp].fa].len) * T.F[mxp][c] + (mxl - T.node[T.node[mxp].fa].len); // mxp 的贡献mxp = T.node[mxp].fa, mxl = T.node[mxp].len; mxr = T.h[mxp];if(mxp) {		res += T.h[mxp] - T.h[u] + T.G[mxp][c] - T.G[u][c] + T.node[mxp].len - T.node[u].len;if(u == 0) res += T.F[1][c];mxp = u; mxl = T.node[u].len; mxr = T.h[u];}}if(!mxp) mxp = 1; // 没了 else {int L = (mxl - T.node[T.node[mxp].fa].len);	mxr += mxl + 1LL * L * T.F[mxp][c] + T.G[T.node[mxp].fa][c] + T.F[1][c];mxl ++;mxp = T.node[mxp].ch[c];}if(len + 1 - mxl > sl) return INF; // 无解else return res + mxr - mnr; 
}
int main() {scanf("%s", s + 1); n = strlen(s + 1);scanf("%s", t + 1); m = strlen(t + 1);S.build(s); T.build(t);scanf("%lld", &K);int sl = 0, sp = 1; // s 能匹配到哪 以及长度 int mxl = 0, mxp = 0, mnp = 1; // 后缀与 t 匹配的长度，节点LL res = 0, mnr = 0, mxr = 0; // s 的贡献和已经匹配不上后缀的贡献， 可以动态更新 while(1) { // 每次确定一个 bool flag = 0;for(int i = 25; i >= 0; i -- ) { // 确定 i if(calc(i, sl, sp, mnp, mxl, mxp, res, mnr, mxr) < K) {init(i, sl, sp, mnp, mxl, mxp, res, mnr, mxr); ans[++ len] = i; flag = 1;break;}}if(!flag) break; // 确定不了就没了 }for(int i = 1; i <= len; i ++ ) putchar(ans[i] + 'a');return 0;
}