時間安排

先寫了 $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;
}