T1 ican
Statement:
给定一个有 \(n(1 \le n \le 10^7)\) 个元素的序列 \(a(a_i \le 10^9)\)，求满足 \(i < j\) 且 \(a_i < a_j\) 的点对 \((i, j)\) 中 \(j - i\) 的最大值。
Solution:
考虑什么样的 \(a_i\) 可能作为点对中较靠左边的元素出现。显然对于一个 \(k > i\) 且 \(a_k \ge a_i\) 相较于 \(i\) 肯定是不优的，舍弃它不会影响答案。于是这些可能作为较左的点产生贡献的 \(a_i\) 组成了一个递减序列。同理可以得到一个可能作为较右的点对答案产生贡献的递增序列。由于序列的单调性，直接在上面做双指针即可。
T2 neverak
Statement:
给定一个由 \(a_1 \times a_2 \times a_3 \times .... \times a_n\) 个 \(n(n \le 10^5)\) 维 \(1 \times 1 \times 1 \times .... \times 1\) 的小立方体组成的 \(n\) 维立方体，现对其表面进行染色，问被染了 \(0, 1, 2 ... , 2n\) 个面的小立方体分别有多少个。
\(95\)% 数据满足 \(n \le 2000\).
Solution:
注意到每一维实际上是互不影响的，于是我们分别考虑每一维。第 \(i\) 维是被 \(1,a_i\) 夹住的，进而可以发现在这一维上有漏出的面的立方体，该维的坐标只有可能是 \(1\) 或 \(a_i\)。但是有可能 \(a_i = 1\)，那么在这维上每一个立方体都会强制漏出 \(2\) 个面。于是我们考虑按维递推：设 \(f_{i, j}\) 是考虑前 \(i\) 个维，有 \(j\) 个面漏出来的小立方体数，转移如下：
-
\(a_i \ge 2: f_{i, j} = f_{i - 1, j} \times (a_i - 2) + f_{i - 1, j - 1} * 2\)
-
\(a_i = 1: f_{i, j} = f{i - 1, j - 2}\)
这样就得到一个 \(O(n^2)\) 算法，可以多项式优化到 \(O(n \log n)\) 但是我不会（待学）。
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4000 + 10, mod = 998244353;
int geta(int val){
if(val < 0) return 0;
val = val % mod; return val;
}
int n, a[N], cnt, f[N][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; f[0][0] = 1;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 2 * n; j++){
if(a[i] >= 2) f[i][j] = ((f[i - 1][j - 1] * 2 % mod) + (f[i - 1][j] * geta(a[i] - 2)) % mod) % mod;
else if(j >= 2) f[i][j] = f[i - 1][j - 2];
}
}
for(int i = 0; i <= 2 * n; i++) cout << f[n][i] << " ";
return 0;
}
T3 qtree
Statement:
略。
Solution:
容易想到两种暴力：
-
每次查询时，把所有的标记点的距离记作 \(0\)，跑一遍 \(\rm BFS\) 找到每个点的最短距离，并输出询问点的最短距离。
-
每次查询时，把询问点和所有标记点的距离用 \(\rm LCA\) 求出来，取 \(\min\) 输出即可。
考虑把两种暴力综合起来，我们使用 大块更新，小块暴查 的思想，将这些询问分成 \(T\) 个块，每次处理完一个块就用 \(\rm BFS\) 更新答案，而在块中的修改就用第二种暴力求 \(\rm LCA\) 查询即可。两种操作分别的时间复杂度是 \(n\times S\) 和 \(n \log n \times \frac{q}{S}\)，当 \(S = \sqrt{n \log n}\) 时两边取到等号。
当然还有点分树做法（待学）。
qwq
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int n, q, dist[N], bksiz, b[N], _fa[N][18], dep[N];
struct edge{
int v, next;
}edges[N << 1];
int head[N], idx;
inline void add_edge(int u, int v){
edges[++idx] = {v, head[u]};
head[u] = idx;
}
inline int min(int x, int y){
if(x < y) return x;
return y;
}
int Change[N], tot;
inline void change(){
if(!tot) return; queue<int> Q;
for(int i = 1; i <= tot; i++) dist[Change[i]] = 0, Q.push(Change[i]);
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v;
if(dist[v] > dist[u] + 1) dist[v] = dist[u] + 1, Q.push(v);
}
}
tot = 0;
}
inline void init(int u, int fa){
dep[u] = dep[fa] + 1; _fa[u][0] = fa;
for(int i = 1; (1 << i) < dep[u]; i++) _fa[u][i] = _fa[_fa[u][i - 1]][i - 1];
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v; if(v == fa) continue;
init(v, u);
}
}
inline int LCA(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
for(int i = 17; i >= 0; i--) if(dep[_fa[x][i]] >= dep[y]) x = _fa[x][i];
if(x == y) return x;
for(int i = 17; i >= 0; i--) if(_fa[x][i] != _fa[y][i]) x = _fa[x][i], y = _fa[y][i];
return _fa[y][0];
}
inline int query(int u){
int ans = dist[u];
for(int i = 1; i <= tot; i++) ans = min(ans, dep[u] + dep[Change[i]] - 2 * dep[LCA(u, Change[i])]);
// cout << g[u] << " " << ans << "\n";
return ans;
}
inline int read(){
int ret = 0; char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') ret = (ret << 3) + (ret << 1) + (c - '0'), c = getchar();
return ret;
}
inline void write(int x){
if(!x) return;
write(x / 10); putchar((char)((x % 10) + '0'));
}
inline void _write(int x){
write(x); if(!x) putchar('0'); putchar('\n');
}
signed main(){
// freopen("10.in", "r", stdin);
// freopen("lsy.out", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// _write(1333); _write(0);
n = read(); q = read(); bksiz = sqrt(n * log(n) / log(2));
for(int i = 1; i <= n; i++) dist[i] = INF;
for(int i = 1; i < n; i++){
int x, y; x = read(); y = read();
add_edge(x, y); add_edge(y, x);
}
init(1, 0); Change[++tot] = 1; b[1] = true; change();
int cnt = 0;
while(q--){
int opt, x; opt = read(); x = read();
if(cnt >= bksiz) change(), cnt = 0;
if(opt == 1){
if(!b[x]) Change[++tot] = x, b[x] = 1;
}
else{
if(b[x]) _write(0);
else{
int val = query(x); _write(val);
}
}
cnt++;
}
return 0;
}
/*
6 5
1 2
2 3
2 4
4 5
4 6
1 6
2 2
2 4
2 5
2 3
*/
T4 雨即实刑
Statement
给定 \(n(1 \le n \le 2000)\) 个开区间 \((l_i, r_i)\)，初始时满足一定有一个 \(x\) 使得 \(\forall i (1 \le i \le n), l_i < x < r_i\)。每次你可以选择一个区间 \(i\)，使它由 \((l_i, r_i)\) 变为 \((l_i + 1, r_i + 1)\) 或 \((l_i - 1, r_i - 1)\)。问最少需要多少次操作才可以使得区间两两无交。
Solution:
注意到原来的区间每个都有重叠的地方，尝试寻找突破口。手玩一下样例比较容易发现最后区间之间一定是紧密排列的，并且感性理解一下其中一定有一个区间是不动的。如果是这样的话，我们可以枚举这个区间左边有多少个区间，然后 \(\rm DP\) 计算。具体的，枚举固定的区间左边的区间数量 \(lsiz\)。设 \(f_{i, j, k}\) 为考虑前 \(i\) 个区间，左边填了 \(j\) 个数时，是(\(k = 1\))/否已经确定了不动的区间时的最少操作数。转移如下：
-
\(j > 0\)（填到左边）：
直接考虑 \(i\) 所需要的操作数是困难的，不妨考虑贡献法。若对于一个区间我们把它放在左边（从左到右）第 \(i\) 个区间，显然的他对于前面 \(i - 1\) 的区间的移动代价做出了 \(len_i\) 的贡献，接着考虑它自己移动的代价，显然它不考虑中间区间移动的代价是 \(l_i + len_i - l_{id}\)（其中 \(id\) 是固定区间的编号）。我们不知道 \(id\) 的具体值，但由于我们只考虑它本身产生的贡献，直接加上 \(l_i + len_i\) 即可。状态转移方程为 \(f_{i, j, k} = \min(f_{i, j, k}, f_{i - 1, j - 1, k} + i \times len_i + l_i)\)。 -
\(i > j\)（填到右边）：同理可得\(f_{i, j, k} = \min(f_{i, j, k}, f_{i - 1, j, k} + (i - j - k) \times len_i + r_i)\)。
-
\(k = 1\)（作为不动区间）：注意到在前面转移的时候对于左边的区间我们少考虑了 \(-l_{id}\) 的贡献，而对于右边的区间少考虑了 \(r_{id}\) 的贡献，加上即可。于是有 \(f_{i, j, k} = \min(f_{i, j, k}, f_{i - 1, j, k - 1})\)。
但是还有一个问题：不考虑中间填那个区间，什么样的摆放顺序才是最优的呢？注意到对于某一边不同的摆放顺序，一个区间 \(i\)，\(l_i, r_i\) 对答案带来的贡献都是一样的，唯一不同的是 \(len_i\) 带来的贡献，注意到决策顺序带来的 \(len_i\) 前的系数从前往后都是不断变大的，于是我们贪心的让 \(len_i\) 较小的区间放到前面去。
于是我们得到了一个 \(O(n^3)\) 做法。考虑优化做法，我们再次发掘题目中的性质，并结合 贡献取到最小值时 \(lsiz\) 的值可以观察出：最优情况下，固定的区间左右区间数量差小于等于 \(1\)。这个直觉是我们可以将区间整体向少的一边偏移而得到更小的答案。于是我们只需要计算至多 \(2\) 个 \(lsiz\) 便可以得到答案。时间复杂度来到了 \(O(n^2)\)。
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5000 + 10, INF = 1e18;
int n, f[N][N][2], ans = INF;
struct line{
int l, r, len;
}L[N];
bool cmp(struct line l1, struct line l2){return l1.len > l2.len;}
void solve(int lsiz){
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= 1; k++)
f[i][j][k] = INF;
f[0][0][0] = 0; int rsiz = n - 1 - lsiz;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= min(i, lsiz); j++){
for(int k = 0; k + j <= i && k <= 1; k++){
int lcnt = j, rcnt = i - lcnt - k;
if(lcnt) f[i][j][k] = f[i - 1][j - 1][k] + lcnt * L[i].len + L[i].l;
if(rcnt) f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + rcnt * L[i].len - L[i].r);
if(k) f[i][j][k] = min(f[i][j][k], f[i - 1][j][k - 1] - lsiz * L[i].l + rsiz * L[i].r);
}
}
}
ans = min(ans, f[n][lsiz][1]);
}
signed main(){
//freopen("5.in", "r", stdin);
//freopen("lsy.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n; for(int i = 1; i <= n; i++) cin >> L[i].l >> L[i].r, L[i].len = L[i].r - L[i].l ;
sort(L + 1, L + n + 1, cmp);
solve(n / 2); if(n % 2 == 0) solve(n / 2 - 1);
cout << ans << "\n";
return 0;
}