决策延后和随机映射
__biu_biu_biu__
·
·
算法·理论
写在前面
这个决策延后是个盗版。不是 DP 那个。
作为笔者，我也不知道这两个东西有什么关联。
但作为两个比较常见的 trick，就让我来整理一下吧。
合并延后
对于 n 个询问，如果可以按某种顺序排序后，对于每个点对 (i,j) 满足：
- 如果 i<j 且 f(i,j)=1，则 i 无论选不选都对 j 产生不了影响；
- 如果 i<j 且 f(i,j)=1，则如果 j 满足了，则 i 一定满足；
那么这些询问是可以进行延后处理的，其中的 f 为另一些限制，此时的延后处理是解决关于 f 的限制问题的。
延后处理的核心是两个数组 ans 和 anss，分别记录了当前的实际答案与合并延后后的答案。
合并延后的目的是处理：现在无法贡献，但与以后的一起加可以贡献的情况。
### 例一、$^*$BagBag
本题为笔者的自创题。
有一个包容量为 $m$，$n$ 件物品，有重量 $w$ 和价值 $v$，以及一个多的魔法值 $k$，求最大的装货方式 $(a_1,a_2,a_3,\dots,a_p)$，使得 $m+\max\limits_{1\le i\le p}(k_{a_i})\ge \max\limits_{1\le i\le p}(w_{a_i})$。求 $\sum v_{a_i}$ 最大。
如果直接暴力的话肯定会出现现在加不了，后面加的了的问题。
考虑决策延后，记录两个变量 $ans,anss$ 分别表示当前的合法答案，合并延后的答案。
- 如果这个物品加不了，则 $anss$ 增加，$ans$ 不变。
- 如果这个物品可以加，则比这个物品重量小的都可以加，则 $ans\to anss$，并增加当前的答案。
这道题目是合并延后的入门题，是弱化版。
```cpp
using namespace std;
const int N = 1e6 + 5;
struct node {
int v, w, k;
} a[N];
bool cmp(node x, node y) {
return x.k < y.k;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].v >> a[i].k;
}
sort(a + 1, a + n + 1, cmp);
int ans = 0, anss = 0;
for(int i = 1; i <= n; i++) {
if(m + a[i].k < a[i].w) {
anss += a[i].v;
}
else {
ans = anss = anss + a[i].v;
}
}
cout << ans;
}
```
### 例二、AT_nikkei2019_qual_e Weights on Vertices and Edges
有一个图 $(V,E)$，有点权和边权，将这些边删除一些使得对于剩下的边，其所在的连通块的点权和大于等于这条边的边权，求最小删除的边数。
首先倒着来，改为最多能加的边，我们发现对于 $f$ 表示：点 $i$ 与点 $j$ 是否要合并，排序顺序为边权降序。
一个显然的错误是直接合并，如果符合就改。但可能单次合并不行，但合并成一个更大的连通块可行，所以这个贪心有问题。
这样的话对于点 $i$ 和 $j$ 要合并的情况下，如果 $i<j$，即 $w_i<w_j$，则 $w_i$ 的选择对 $w_j$ 是没有影响的，且如果 $j$ 可以，则 $i$ 也可以。
所以我们记录 $ans$ 表示合法的以 $i$ 为根的答案，$anss$ 表示以 $i$ 为根的所有答案。
为了方便，我们记 $sum_u$ 为 $u$ 所在的连通块的点权和，对于边 $(u,v,w)$：
- 如果 $u,v$ 在一个连通块：
- 如果 $sum_u\ge w$，则这条边加入没问题，记录 $ans_u = ans_u+1,anss_u=anss_u+1$。
- 否则加入有问题，则只记录 $anss_u = anss_u +1$。
- 如果 $u,v$ 不在同一个连通块：
- 如果 $sum_u +sum_v < w$，则加入这条边有问题，但我们仍然将两个连通块合并，记录 $ans_u = ans_u+ans_v$，且 $anss_u = anss_u + anss_v+1$。
- 如果 $sum_u +sum_v \ge w$，则无问题，此时由于其满足上述性质，则 $u$ 和 $v$ 以前不行的边就可以了，所以记录 $ansu=anss_u = anss_u+anss_v+1$。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
struct edge {
int u, v, w;
} a[N];
int fa[N], mx[N], sum[N], ans[N], ans1[N], n, m;
bool cmp(edge x, edge y) {
return x.w < y.w;
}
int Find(int u) {
if(u == fa[u]) return u;
return fa[u] = Find(fa[u]);
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> sum[i];
fa[i] = i;
}
for(int i = 1; i <= m; i++) {
cin >> a[i].u >> a[i].v >> a[i].w;
}
sort(a + 1, a + m + 1, cmp);
int anss = 0;
for(int i = 1; i <= m; i++) {
int fu = Find(a[i].u), fv = Find(a[i].v);
if(fu == fv) {//如果 w<sum(fu) 就加入答案，否则先等着
mx[fu] = max(mx[fu], a[i].w);
if(mx[fu] <= sum[fu]) {
ans[fu]++,ans1[fu]++;
}
else {
ans1[fu]++;
}
}
else {
fa[fv] = fu;
sum[fu] += sum[fv];
mx[fu] = max(max(mx[fu], mx[fv]), a[i].w);
if(mx[fu] <= sum[fu]) {
ans[fu] = ans1[fu] + ans1[fv] + 1;
ans1[fu] = ans[fu];
}
else {
ans[fu] = ans[fu] + ans[fv];
ans1[fu] = ans1[fu] + ans1[fv] + 1;
}
}
}
for(int i = 1; i <= n; i++) {
if(fa[i] == i) {
anss += ans[i];
}
}
cout << m - anss;
return 0;
}
```
## 随机映射
随机映射就是将元素映射为随机的值，然后用异或求和等方式将原来苛刻的条件映射成几个数值的比较。
### 例一、[CSP-S2022] 星战
给你 $4$ 个操作，分别为删点、加点、删边、加边。问你每次加边后图是否是内向基环树。
内向基环树就是每一个点都有一个出边，我们可以利用这个性质。
我们给每一个点附上一个随机权值 $val_x$，如果一个点有出边就加上权值，在记录一下点作为终点的随机权值和 $sum_x$ 和满状态下的 $sum1_x$。
则对于 $4$ 个操作：
- $sum_y\to sum_y-val_x,ans\to ans - val_x$，表明 $x\to y$ 的被删掉了。
- $ans\to ans-sum_x,sum_x = 0$，表明点 $x$ 死掉了。
- $sum_y \to sum_y + val_x,ans \to ans + val_x$，表明加入了边。
- $ans\to ans + sum1_x - sum_x$，表示加入剩下的边，然后 $sum_x \to sum1_x$。
如果 $ans$ 和 $\sum val_x$ 相等，则是 `Yes` 否则是 `No`。
习题：P2087 / P16726。