R14 - T1 序列
难度：黄 / 绿
题意
给定一个长为 \(n\) 的非负整数序列 \(a\)，你可以进行任意次以下的操作：
选择一个区间 \([l,r]\)，然后将 \(a_l,a_{l+1},\cdots,a_r\) 都减去 \(1\)。
你希望用最小的操作次数将 \(a\) 中的所有数变成 \(0\)。在此基础上，定义一次操作 \([l,r]\) 能获得的分数为 \((r-l+1)^2\)，你需要求出：在最小化操作次数的前提下，最终可能的分数的最大值与最小值分别是多少。
Solution
签到题，场上想了三个小时？我太fw了
这种区间加减的好像大部分都是差分后做。虽然我没有做差分也做出了一个更劣解。
令 \(c_i = a_i - a_{i - 1}\)，\(a_0 = a_{n + 1} = 0\)。这样区间减 1 就变成了 \(c_i \gets c_i - 1\)，\(c_{j + 1} \gets c_{j + 1} + 1\)。转换后实际上相当于一个配对问题，将 \(c_i > 0\) 的和 \(c_j < 0\) 进行配对（注意要保证 \(i < j\)）。实际上这个问题不一定有解（就是括号序列不一定合法嘛），但是 \(a_i = \sum_{j < i} c_j \ge 0\) 所以这个一定能匹配上。那么最小操作次数就是两两配对，即为 \(\frac{1}{2} \sum_{i = 1}^{n + 1} |c_i|\)。
想清楚了就基本做完了，最大化分数就总是让最前面的 \(i\) 和最后面的 \(j\) 匹配，最小化就正好反过来。这分别对应着栈和队列两种 DS。复杂度 \(O(N)\)。
赛时思路就是直接考虑，当时很自然的想出了最大化，然后考虑在最大化的操作序列上重新匹配左端点和右端点，复杂度 \(O(N \log N)\)。
赛时
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int pree[N], pre[N], l[N], r[N], nxte[N], n, a[N], st[N], tp, ansmn, ansmx;
void chmin(int &a, int b){ a = min(a, b); }
void chmax(int &a, int b){ a = max(a, b); }
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i){l[i] = pree[i] = i;pre[i] = 0;while(tp && a[st[tp]] >= a[i]){if(a[st[tp]] == a[i]) chmin(pree[i], pree[st[tp]]);// chmax(pre[i], a[st[tp]]);chmin(l[i], l[st[tp]]);--tp;}chmax(pre[i], a[st[tp]]);st[++tp] = i;} for(int i = n; i >= 1; --i){r[i] = nxte[i] = i;while(tp && a[st[tp]] >= a[i]){if(a[st[tp]] == a[i]) chmax(nxte[i], nxte[st[tp]]);chmax(r[i], r[st[tp]]);--tp;}chmax(pre[i], a[st[tp]]);st[++tp] = i;}for(int i = 1; i <= n; ++i){// cout << i << ' ' << l[i] << ' ' << r[i] << ' ' << pree[i] << ' ' << nxte[i] << ' ';auto cal = [](int i, int l, int r){return i * (r - l + 1) * (r - l + 1);};if(nxte[i] == i){ansmx += cal(a[i] - pre[i], l[i], r[i]);}}cout << ansmn << ' ' << ansmx;return 0;
}
std
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
#define int long long
int a[N], c[N], n;
int cal(int x, int l, int r){return x * (r - l) * (r - l);
}
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i], c[i] = a[i] - a[i - 1];c[n + 1] = a[n + 1] - a[n];int ansmx = 0, ansmn = 0;stack<int> st;for(int i = 1; i <= n + 1; ++i){if(c[i] > 0) st.push(i);else if(c[i] < 0){while(c[i] + c[st.top()] < 0) ansmx += cal(c[st.top()], st.top(), i), c[i] += c[st.top()], st.pop();int minx = min(abs(c[i]), c[st.top()]);ansmx += cal(minx, st.top(), i);c[i] = 0, c[st.top()] -= minx;}}for(int i = 1; i <= n; ++i) c[i] = a[i] - a[i - 1];c[n + 1] = a[n + 1] - a[n];queue<int> q;for(int i = 1; i <= n + 1; ++i){if(c[i] > 0) q.push(i);else if(c[i] < 0){while(c[i] + c[q.front()] < 0)ansmn += cal(c[q.front()], q.front(), i), c[i] += c[q.front()], q.pop();int minx = min(abs(c[i]), c[q.front()]);ansmn += cal(minx, q.front(), i);c[i] = 0, c[q.front()] -= minx;}}cout << ansmn << ' ' << ansmx << '\n';return 0;
}
R14 - T2 复制粘贴
难度：黄 / 绿
题意
Yoimiya 有一个文本编辑器，一开始这个文本编辑器里面有一个字符 Y。
文本编辑器支持剪贴板，也就是复制粘贴操作。Yoimiya 可以进行两种操作：
- 复制：该操作耗费 \(x\) 秒，进行该操作后，剪贴板中的字符串将被替换为当前文本编辑器中的字符串。
- 粘贴：该操作耗费 \(y\) 秒，该操作会将剪贴板中的字符串拼接到文本编辑器中的字符串的末尾。
一开始，剪贴板中是空字符串。
给定正整数 \(N\)，问最少需要多少秒，才能使文本编辑器中 Y 的个数 \(>N\)。
Solution
发现操作序列被 Copy 分成若干段，假设总共进行了 \(k\) 次 Copy 操作，那么第 \(i\) 次 Copy 操作之后总是紧跟着 \(a_i\) 次 Paste。题目限制即为 \(\prod_{i = 1}^k (a_i + 1) > N\)，要最小化 \(Cost = \sum_{i = 1}^k (a_i \times y) + k \times x\)。
由于 \(a_i + 1\ge 2\)，所以 \(k\) 有上界 \(O(\log N)\)。那么就可以枚举 \(k\)，此时 \(Cost = \sum_{i = 1}^k (a_i \times y) + k \times x = k \times (x - y) + \sum_{i = 1}^k(a_i + 1)\)。发现可以均值，可是这里的变量是整数怎么办？一个小 trick：可以设有 \(p\) 个 \(a_i + 1 = t\)，\(k - p\) 个 \(a_i + 1 = t + 1\)，然后二分这个 \(t\) 就可以算出最小贡献。
枚举两维，二分一维，再加上单次验证求幂，复杂度 \(O(\log ^ 4 N)\)。
千万小心不要爆 ll。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
ll n, x, y, ans = LLONG_MAX;
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> x >> y;if(n == 1) return cout << x + y << '\n', 0;ll D = ceil(log2(n));for(ll i = 1; i <= D; ++i){for(ll p = 0; p <= i; ++p){ll l = 2, r = n + 1;while(l < r){i128 mid = (l + r) >> 1, ck = 1;for(int j = 1; j <= p; ++j){if(ck > n / mid){ck = n + 1; break;}ck *= mid;}for(int j = p + 1; j <= i; ++j){if(ck > n / mid){ck = n + 1; break;}ck *= (mid + 1);}assert(ck > 0);if(ck > n) r = mid;else l = mid + 1;}assert(l == r);i128 sum = (i128)l * p + i128(l + 1) * (i - p) - i;if(ans / y >= sum){ll tmp = (ll)sum * y + i * x;assert(sum * y > 0 && i * x > 0);ans = min(ans, tmp);}}}cout << ans;return 0;
}
R14 - T3 染色
难度 ：蓝
题意
有 \(n\) 种颜料和一个长度为 \(m\) 的画板，颜色分别为 \(1,2,\cdots,n\)。第 \(i\) 个颜料有 \(c_i\) 桶。
现在你可以用一个笔刷在这个画板上画 \(n\) 段，具体来说，你可以选择任意一个 \(1\le p\le m\) 作为你一开始的位置，接下来依次对每个 \(i=1,2,\cdots,n\)，你可以将笔刷从当前位置 \(p\) 向左或向右移动 \(c_i\) 格，即移动到 \(q=p-c_i+1\) 或 \(q=p+c_i-1\) 处，并将 \(p,q\) 之间的位置（包括 \(p,q\)）都染成第 \(i\) 种颜色。
这里要求新的位置 \(q\) 不能超出画板的边界，即 \(1\le q\le m\)。
如果一个位置被染色多次，我们认为这个位置的颜色是它最后一次染上的颜色；如果一个位置没有被染色，我们认为这个位置的颜色为 \(0\)。现在你需要求出染色完成后可以得到多少种不同的画板，答案对 \(998244353\) 取模。
这里两个最终画板是不同的，当且仅当存在至少一个位置 \(i\) 满足这两个画板在第 \(i\) 个位置上的颜色不同。
Solution
这种后面覆盖前面的都可以倒过来做。然后就可以上人类智慧了，\(f_{i, j, 0 / 1}\) 表示倒着做到第 \(i\) 个，目前有颜色区间长度为 \(j\)，现在刷子在左 / 右端点。总是枚举最后一段笔刷在区间范围里来回动（这是不会造成任何影响的），然后到 \(k\) 的时候跳出了原有范围来进行转移。发现这个转移还需要一个 dp 来判断合法性。也就是 \(g_{i, j, len, end, 0 / 1}\) 表示从 \(i\) 画到第 \(j\) 段，都没有超出 \(len\) 的长度，最后到达 \(len\) 区间中的第 \(end\) 个位置，起点是最左边还是最右边，转移就是简单背包。
复杂度 \(O(N^2M^2)\)。
注意一开始 \(f_{n, c[n], 0}\) 和 \(f_{n, c[n], 1}\) 实际上是一种情况，特判掉。
std
#include <bits/stdc++.h>
using namespace std;
const int N = 155, mod = 998244353;
#define int long long
int c[N], n, m, f[2][N][N];
bitset<N> g[2][N][N][N]; // 长度限制为 len, 从第 i 个的左 / 右端点开始走，走到第 j 个, 能不能走到 k
void add(int &x, int y){ (x += y) %= mod; }
int mul(int x, int y){ return (x * y) % mod; }
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> c[i];for(int i = n; i >= 1; --i){for(int t : {0, 1}){for(int len = 1; len <= m; ++len){int st = (t == 0 ? 1 : len);g[t][len][i][i][st] = 1;for(int j = i - 1; j >= 1; --j){for(int k = 1; k <= len; ++k){if(k + c[j] - 1 <= len) g[t][len][i][j][k] = g[t][len][i][j][k] | g[t][len][i][j + 1][k + c[j] - 1];if(k - c[j] + 1 >= 1) g[t][len][i][j][k] = g[t][len][i][j][k] | g[t][len][i][j + 1][k - c[j] + 1];}}}}}f[0][n][c[n]] = f[1][n][c[n]] = 1;for(int i = n; i >= 2; --i){for(int ti : {0, 1}){for(int len = 1; len <= m; ++len){for(int j = i - 1; j >= 1; --j){for(int k = len + 1; k <= len + c[j] - 1; ++k){if(k - c[j] + 1 >= 1){if(g[ti][len][i][j + 1][k - c[j] + 1])add(f[1][j][k], f[ti][i][len]);if(i == n) f[1][j][k] = (f[1][j][k] >= 1 ? 1 : f[1][j][k]);}if(1 + c[j] - 1 >= k - len + 1){if(g[ti][len][i][j + 1][c[j] - (k - len + 1) + 1])add(f[0][j][k], f[ti][i][len]);if(i == n) f[0][j][k] = (f[0][j][k] >= 1 ? 1 : f[0][j][k]);}}}}}}int ans = 0;for(int i = n; i >= 1; --i){for(int len = 1; len <= m; ++len){for(int t : {0, 1}){if(!g[t][len][i][1].count()) continue;add(ans, mul(f[t][i][len], m - len + 1));if(i == n) break;}}}cout << ans;return 0;
}
R14 - T4 树
难度：紫
题意
给定一棵 \(n\) 个点的树，以及树上的 \(m\) 条路径。
现在你需要将这些路径划分为尽可能少的若干个集合，使得每个集合内部的路径两两不交。
Solution
区间图的树升级版？
如果将相交的路径两两连边，发现这个图是一个弦图。题目要求的是最小染色数。
最小染色数就是最大团啊，最大团就是被最多路径经过的那个点的路径数 \(k\)。
那方案呢，如果直接跑 MCS 是 \(O(M^2)\) 的。
我们找到被经过路径数最大的中深度最小的那个点，这个点一定有一条路径以它为 lca，然后把这条路径删掉，继续找。直到最大的被经过路径数减少了 1 算一轮，这一轮中被删掉的路径就染同一种颜色。可以验证这个构造是合法的。
咋想出来的我也不知道，云浅说很套路
树剖维护是两个 log 的，卡常。当然我也不可能写 LCT。
std
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
#define ls(p) p << 1
#define rs(p) p << 1 | 1
#define Tp template<typename T>
#define Ts template<typename T,typename... _T>
char buf[1<<20],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
Tp inline void read(T& x){x=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())if(c=='-')f=1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);f&&(x=-x);
}
Ts inline void read(T& x,_T&... y){read(x),read(y...);}
template<typename T>void qw(T x){if(x<0)x=-x,putchar('-');if(x/10)qw(x/10);putchar(x%10+48);
}
int ans[N], val[N * 4], idx[N * 4], tag[N * 4], son[N], siz[N], tp[N], f[N], dfn[N], _dfn[N], tsp, dep[N], n;
struct edge{int u, v, pre;
};
struct myvec{int head[N], cnt;edge e[N * 2];inline void push_back(int u, int v){e[++cnt] = {u, v, head[u]};head[u] = cnt;}inline int back(int u){return e[head[u]].v;}inline void pop_back(int u){head[u] = e[head[u]].pre;}
}e, rge;
struct node{int u, v;
}Que[N];
inline void addtag(int p, int k){ val[p] += k, tag[p] += k; }
inline void pushdown(int p){if(tag[p]){addtag(ls(p), tag[p]);addtag(rs(p), tag[p]);tag[p] = 0;}
}
inline void pushup(int p){val[p] = max(val[ls(p)], val[rs(p)]);idx[p] = (val[ls(p)] >= val[rs(p)] ? idx[ls(p)] : idx[rs(p)]);
}
inline void build(int p, int pl, int pr){val[p] = tag[p] = 0;if(pl == pr) return idx[p] = pl, e.head[pl] = rge.head[pl] = 0, void();int mid = (pl + pr) >> 1;build(ls(p), pl, mid);build(rs(p), mid + 1, pr);pushup(p);
}
inline void update(int p, int pl, int pr, int L, int R, int k){if(L <= pl && R >= pr) return addtag(p, k), void();int mid = (pl + pr) >> 1;pushdown(p);if(L <= mid) update(ls(p), pl, mid, L, R, k);if(R > mid) update(rs(p), mid + 1, pr, L, R, k);pushup(p);
}
inline void dfs(int u, int fa){siz[u] = 1;son[u] = 0;f[u] = fa;dep[u] = dep[fa] + 1;for(int k = e.head[u]; k; k = e.e[k].pre){int v = e.e[k].v;if(v != fa){dfs(v, u);if(siz[son[u]] < siz[v]) son[u] = v;siz[u] += siz[v];}}
}
inline void devide(int u, int top){_dfn[dfn[u] = ++tsp] = u, tp[u] = top;if(son[u]) devide(son[u], top);for(int k = e.head[u]; k; k = e.e[k].pre){int v = e.e[k].v;if(v != f[u] && v != son[u])devide(v, v);}
}
inline void ins(int id){int u = Que[id].u, v = Que[id].v;while(tp[u] != tp[v]){if(dep[tp[u]] < dep[tp[v]]) swap(u, v);update(1, 1, n, dfn[tp[u]], dfn[u], 1);u = f[tp[u]];}if(dfn[u] > dfn[v]) swap(u, v);int Lca = u;update(1, 1, n, dfn[u], dfn[v], 1);rge.push_back(Lca, id);
}
inline void del(int id){int u = Que[id].u, v = Que[id].v;while(tp[u] != tp[v]){if(dep[tp[u]] < dep[tp[v]]) swap(u, v);update(1, 1, n, dfn[tp[u]], dfn[u], -1);u = f[tp[u]];}if(dfn[u] > dfn[v]) swap(u, v);update(1, 1, n, dfn[u], dfn[v], -1);// rge[Lca].emplace_back(id);
}
inline void solve(){int m;read(n, m);build(1, 1, n);e.cnt = rge.cnt = tsp = 0;for(int i = 1; i < n; ++i){int u, v;read(u, v);e.push_back(u, v);e.push_back(v, u);}dfs(1, 0);devide(1, 1);for(int i = 1; i <= m; ++i){int u, v;read(u, v);Que[i] = {u, v};ins(i);}int k = val[1];qw(k), putchar('\n');for(int i = k; i >= 1; --i){int u = _dfn[idx[1]], nw = val[1];while(nw == i){int id = rge.back(u); rge.pop_back(u);del(id);ans[id] = i;u = _dfn[idx[1]], nw = val[1];}}for(int i = 1; i <= m; ++i) qw(ans[i]), putchar(' ');putchar('\n');
}
signed main(){int c, T; read(c, T);while(T--) solve();return 0;
}
Summary
T1 卡太久了啊。后面的部分分都没时间看。下次先 2h 写部分分试一下。
