Educational Codeforces Round 146 (Rated for Div. 2)（B，E详解）

题外话：抑郁场，开局一小时只出A，死活想不来B，最后因为D题出锅ura才保住可怜的分。但咱本来就写不到D

B - Long Legs（数论）

本题题解法一学自同样抑郁的知乎作者 幽血魅影的题解，有讲解原理。
法二来着知乎巨佬 cup-pyy（大佬说《不难发现》呜呜）

题意

三种操作：

1. 向上走 $m$ 步
2. 向右走 $m$ 步
3. 给自己一次走的步数加 $1$，即使得$m=m+1$

问从 $(0,0)$ 走到 $(a,b)$的最小操作次数，值得注意的是操作三不可逆。

解析

假设我们最终一步的大小增长到 $m$， 那么在这个过程中我能以 $[1,m]$ （当步数增长到该数时）之间的任何数字向上或向右迈出 $k$ 步。
贪心的考虑，使得最大的步数 $m$ 迈的越多对我们来说更优。
设终点为 $(a,b)$ 我们先向上迈出 $a\mathrm{mod}m$ 步， 再向右迈出 $b\mathrm{mod}m$ 步，此时剩下的向上向下还需要走的步数肯定都能整除 $m$。

通俗的来讲操作流程就是，先将步数增加到 k = min(a % m, b % m)，向取模小的那个方向走一步，再将步数增加到 k = max(a % m, b % m)，向取模大的方向走一步，此时两个方向剩余步数都能整除 $m$，将步数增加到 $m$ 直接走即可。

于是答案有 $ans=\lceil a/m\rceil +\lceil b/m\rceil +m-1$。
设最终的 $m$ 为 未知数 $x$ ，观察方程 f(x)=a+bx+x−1f(x) = \\frac {a + b} x + x - 1f(x)=xa+b​+x−1， 不难发现其中的 a+bx+x\\frac {a + b} x + xxa+b​+x 是双勾函数， 而 $1$ 是常数，函数在 x=a+bx = \\sqrt{a + b}x=a+b​ 时取到最小值。
但是原式中有向上取整的影响，我们需要在 极值 a+b\\sqrt{a + b}a+b​ 的周围寻找真正的极值点。

法二：考虑到数据范围，甚至可以枚举最终的 $m$ 以取最小值。

代码

solve1() 为法一，solve2() 为法二，都能 AC。

#include <bits/stdc++.h>
using namespace std;
#define ll long longvoid solve1(){int a, b;cin >> a >> b;int x = sqrt(a + b);int ans = a + b;for(int i = max(1, x - 100); i <= x + 100; i ++){ans = min(ans, (a + i - 1) / i + (b + i - 1) / i + i - 1);}cout << ans << "\\n";
}void solve2(){int a, b;cin >> a >> b;int ans = a + b;for(int i = 1; i <= 1000000; i ++){ans = min(ans, (a + i - 1) / i + (b + i - 1) / i + i - 1);}cout << ans << "\\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve1();// solve2();}return 0;
}

E - Chain Chips

第一次见 DDP （动态动态规划）。

题意

给定 $n$ 个节点的无向图和 $n-1$ 条边，每条边有权值 wiw_iwi​，$i$号边连接 $i$ 与 $i+1$ 号节点。
最初每个节点上有一个编号与节点编号相同的球，每次可以将一个球通过一条边移动到相邻的节点上，花费为边的权值，问使得每个节点上有一个球，且球的编号与节点编号不同的最小花费。
并且有 $q$ 个询问，每次询问会修改一条边，询问修改后原问题的答案。（每次修改都会持续对问题影响，每次询问之间不独立）

解析

博主自己做时，没看懂每次操作对接下来都有影响，还以为每次操作都是独立的，写了个 DP。
在这里先讲解一下如果每次操作独立的解法（因为没有样例可能有bug，但思路应该没问题的）

每次操作独立

我们考虑最大的花费：将所有球向右移动一位，将最后一个球移动到 $1$ 号节点上，这样所有的边都被使用了两次。

我们从较小的情况考虑：

1. 两个节点那么就是 $1$ 号球到节点 $2$，$2$ 号球到节点 $1$，ans=w1∗2ans = w_1 * 2ans=w1​∗2。
2. 三个节点情况也很简单 $1$->节点$3$ ，$2$->节点$1$，$3$->节点$2$。ans=w1∗2+w2∗2ans = w_1 * 2 + w_2 * 2ans=w1​∗2+w2​∗2。
3. 四个节点我们可以将其分成两部分 $[1,2],[3,4]$，即两个情况 $1$ 。这时我们发现 节点 $[2,3]$ 之间的边我们没有使用到。
4. 最后再考虑一下五个节点的情况，我们可以将其分成 $[1,2,3]+[4,5]$ 或者 $[1,2]+[3,4,5]$，即情况 $1$ $+$ 情况 $2$。

此时我们就可以发现，可以将某一段区间不选不让球通过，以此来减少我们的花费。

就可以想到维护一个前缀DP 和 后缀DP，因为和本题关系不到了，具体看代码吧，也可以跳过直接看正解。

这是操作独立的代码不是本题的代码！

#include <bits/stdc++.h>
using namespace std;
#define ll long longconst int N = 2e5 + 10;
const ll inf = 1e18;ll f1[N], f2[N]; //f1:前i个完成交换的最小花费， f2：从n ~ i完成交换的最小花费
int n, a[N];void init(){f1[0] = 0, f1[1] = inf, f1[2] = 2 * a[1];for(int i = 3; i <= n; i ++){f1[i] = inf;ll sum = a[i - 1];for(int j = i - 2; j >= i - 3; sum += a[j], j --){f1[i] = min(f1[i], f1[j] + sum * 2);}}f2[n + 1] = 0, f2[n] = inf, f2[n - 1] = 2 * a[n - 1];for(int i = n - 2; i >= 1; i --){f2[i] = inf;ll sum = a[i];for(int j = i + 2; j <= i + 3; sum += a[j - 1], j ++){f2[i] = min(f2[i], f2[j] + sum * 2);}}cout << "f1[n] = " << f1[n] << " f2[n] = " << f2[n] << "\\n";
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i < n; i ++){cin >> a[i];}init();int m;cin >> m;while(m --){int idx, val;cin >> idx >> val;ll ans = f1[idx] + f2[idx + 1];ans = min(ans, f1[idx - 1] + f2[idx + 2] + val * 2);if(idx - 2 >= 0)ans = min(ans, f1[idx - 2] + a[idx - 1] * 2 + val * 2 + f2[idx + 2]);if(idx + 3 <= n + 1)ans = min(ans, f1[idx - 1] + val * 2 + a[idx + 1] * 2 + f2[idx + 3]);cout << ans << "\\n";}return 0;
}

操作之间不独立

总结一下上述规律以及结论：
关于 $n$ 个节点，无论数量为多少，总能将其分成若干个大小为 $2$ 或 $3$ 的区间使其错排， 使得其中某些边可以不被使用，以此减少花费。

推广一下，我们可以使得任意长度的一段错排花费代价为边权和的两倍（一条边被使用肯定要使用两次，本节点过去 + 其他节点过来），而上述的分成长度为 $2$ 或 $3$ 的是贪心的使得更多边可以不被使用。

重点：
对于一段节点 $[l,r]$，其中的边权之和为 $s$，那么可以用 $2s$ 的代价将其错排，排列完后边 $[l-1,l]$ 和 $[r,r+1]$ 就可以不再使用，那么题目就可以抽象为给定连续的 $n-1$ 段，其中有些段可以不选但不能有连续的超过一段不选求最小值权值和。

我们就要考虑 DDP 线段树维护。具体见代码

先将最重要的线段树结构体定义和 线段之间合并 拿出来讲解。

struct node{int l, r;ll vl, vr, vall, vno; // 最小花费// vl:选[l, l + 1]，不选[r - 1, r] 左选右不选// vr:选[r - 1, r]，不选[l, l + 1] 右选左不选// vall: 左右都选// vno: 左右都不选
}tr[N * 4];void pushup(int p){node &ls = tr[p << 1], &rs = tr[p << 1 | 1];/* 所有选择都基于：可以有边不选，但不能有连续的两条边及以上不选 */tr[p].vl = min({ls.vl + rs.vl,ls.vall + rs.vl,ls.vall + rs.vno});tr[p].vr = min({ls.vr + rs.vr,ls.vr + rs.vall,ls.vno + rs.vall});tr[p].vall = min({ls.vl + rs.vall,ls.vall + rs.vr,ls.vall + rs.vall});tr[p].vno = min({ls.vr + rs.vl,ls.vr + rs.vno,ls.vno + rs.vl});
}

剩下的就是基本的线段树，看代码和注释就行了。

#include <bits/stdc++.h>
using namespace std;
#define ll long longconst int N = 2e5 + 10;
const ll inf = 1e18;int n, a[N];struct node{int l, r;ll vl, vr, vall, vno; // 最小花费// vl:选[l, l + 1]，不选[r - 1, r] 左选右不选// vr:选[r - 1, r]，不选[l, l + 1] 右选左不选// vall: 左右都选// vno: 左右都不选
}tr[N * 4];void pushup(int p){node &ls = tr[p << 1], &rs = tr[p << 1 | 1];/* 所有选择都基于：可以有边不选，但不能有连续的两条边及以上不选 */tr[p].vl = min({ls.vl + rs.vl,ls.vall + rs.vl,ls.vall + rs.vno});tr[p].vr = min({ls.vr + rs.vr,ls.vr + rs.vall,ls.vno + rs.vall});tr[p].vall = min({ls.vl + rs.vall,ls.vall + rs.vr,ls.vall + rs.vall});tr[p].vno = min({ls.vr + rs.vl,ls.vr + rs.vno,ls.vno + rs.vl});
}void build(int p, int l, int r){tr[p] = {l, r, inf, inf, inf, inf};if(l == r){tr[p].vno = 0;tr[p].vall = a[l];if(l == 1 || l == n - 1) tr[p].vno = inf; // 左右两端的边必须选，因为1号节点和n号节点只有一条边连接return ;}int mid = (l + r) >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);
}void update(int p, int loc, int k){if(tr[p].l == tr[p].r){tr[p].vall = k;return ;}int mid = (tr[p].l + tr[p].r) >> 1;if(loc <= mid) update(p << 1, loc, k);else update(p << 1 | 1, loc, k);pushup(p);
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i < n; i ++) cin >> a[i];   build(1, 1, n - 1); // n 个点 n - 1 条边int m;cin >> m;for(int i = 1; i <= m; i ++){int u, val;cin >> u >> val;update(1, u, val);cout << min({tr[1].vl, tr[1].vr, tr[1].vall, tr[1].vno}) * 2 << "\\n";}return 0; 
}