20241009 模拟赛

标签：int 边权最小 20241009 生成模拟考虑 dp

A. 排列喵

手玩一下，依次操作 \(1,n,1\) 必然能使序列有序，所以答案不超过 \(3\)。那么依次判断 \(0,1,3\) 即可。原序列如果有序就是 \(0\)。如果 \(a_1=n\) 且 \(a_n=1\) 就是 \(3\)，因为这两个条件有一个不满足时只要操作 \(1,n\) 或 \(n,1\) 就能变成有序。考虑只操作一次时的这个位置 \(p\)，显然一定满足 \(a_p=p\)，进一步，因为 \([1,p)\) 和 \((p,n]\) 是互相独立的，所以前 \(p-1\) 个数一定是一个排列。不难发现两者结合就是一个充要条件。后面的条件判断方式很多，哈希、权值树状数组都可以。有一种很妙的转化是 \(max_{1\leq i<p}a_i=p-1\)。正确性显然。

B. 序列

考虑将依次统计每个数转化为对每个序列，将其中出现的每个数答案 \(+1\)。

考虑这种字典序条件的常见套路，枚举第一个两序列出现不同的位置 \(i\)，再枚举这个位置的值 \(j\in[1,a_i)\)。分成已确定 \((l\leq i)\) 和未确定 \((l>i)\) 两部分位置 \(l\) 计算贡献。那么写出如下代码框架：

for (int i = 1; i <= k; i++){
    for (int j = 1; j < a[i]; j++){
        if (vis[j]) continue;
        _____①_____
        _____②_____
	}
	vis[a[i]] = true;
}

考虑前半部分。因为 \(i\) 这个位置已经满足 \(a_i>b_i\) 了，所以后面的位置可以随便放数，这样的序列方案数就是从 \(n-i\) 个数中选出 \(k-i\) 个进行排列，即 \(val=A_{n-i}^{k-i}\)。于是前半部分（①）统计：

for (int i = 1; i <= k; i++){
    int val = A(n - i, k - i);
    for (int j = 1; j < a[i]; j++){
        if (vis[j]) continue;
        for (int l = 1; l < i; l++) ans[a[l]] += val, ans[a[l]] %= MOD;
        ans[j] += val, ans[j] %= MOD;
        for (int l = 1; l <= n; l++){
            if (vis[l] || l == j) continue;
            ans[l] += val * (k - i) % MOD * iv[n - i] % MOD, ans[l] %= MOD;
		}
	}
	vis[a[i]] = true;
}

考虑后半部分。后半部分可以放 \([1,n]\) 中所有没出现过的数，并且容易发现这些数出现的概率均等，那么贡献应该也一样。总贡献为 \(val\times(k-i)\)，将其平均到每一个数就为 \(\frac{val\times(k-i)}{n-i}\)。于是后半部分（②）统计：

for (int l = 1; l <= n; l++){
    if (vis[l] || l == j) continue;
    ans[l] += val * (k - i) % MOD * iv[n - i] % MOD, ans[l] %= MOD;
}

这样的时间复杂度为 \(O(kn^2)\)。我们考虑优化。

先将上方的第 \(2\) 行中的 l == j 移出去（跳过就相当于先加一次再减一次），得到：

for (int i = 1; i <= k; i++){
    int val = A(n - i, k - i);
    int vl = val * (k - i) % MOD * iv[n - i] % MOD;
    for (int j = 1; j < a[i]; j++){
        if (vis[j]) continue;
        for (int l = 1; l < i; l++) ans[a[l]] += val, ans[a[l]] %= MOD;
        ans[j] += val - vl, ans[j] %= MOD;
        for (int l = 1; l <= n; l++){
            if (vis[l]) continue;
            ans[l] += vl, ans[l] %= MOD;
        }
    }
    vis[a[i]] = true;
}

尝试优化第 \(8\) 行的枚举。考虑把这样的操作转化为全局先加上一个数，再将跳过的部分减去。对于每个 \(i\)，减去的位置是 \(a_j,1\leq j<i\)，也就是说每个数会被它后面的所有位置减去一个值。这可以用一个后缀和实现。

for (int i = 1; i <= k; i++){
    int val = A(n - i, k - i);
    int vl = val * (k - i) % MOD * iv[n - i] % MOD;
    for (int j = 1; j < a[i]; j++){
        if (vis[j]) continue;
        for (int l = 1; l < i; l++) ans[a[l]] += val, ans[a[l]] %= MOD;
        dlt += vl, dlt %= MOD;
        s2[i] = (s2[i] + MOD - vl) % MOD;
        ans[j] += val - vl, ans[j] %= MOD;
    }
    vis[a[i]] = true;
}
for (int i = k; i; i--){
    (s2[i] += s2[i + 1]) %= MOD;
    (ans[a[i]] += s2[i + 1]) %= MOD;
}

现在的瓶颈变成了第 \(4,6\) 行的枚举。考虑先去掉第 \(4\) 行。注意到第 \(6\) 到 \(8\) 行进行的操作都与 \(j\) 无关。那么将其看作 \(a_i-1-cnt\) 次重复操作，\(cnt\) 为 continue 的执行次数。这可以用一颗树状数组维护。第 \(6\) 行是一个显然的后缀和，类似上一次优化，得到如下代码。

for (int i = 1; i <= k; i++){
    int val = A(n - i, k - i);
    int vl = val * (k - i) % MOD * iv[n - i] % MOD;
    int cnt = a[i] - 1 - c1.query(a[i] - 1);
    dlt += cnt * vl % MOD, dlt %= MOD;
    s1[i] = cnt * val % MOD;
    s2[i] = (s2[i] + MOD - cnt * vl % MOD) % MOD;
    for (int j = 1; j < a[i]; j++){
        if (vis[j]) continue;
        ans[j] += val - vl, ans[j] %= MOD;
    }
    c1.add(a[i], 1);
    vis[a[i]] = true;
}
for (int i = k; i; i--){
    (s1[i] += s1[i + 1]) %= MOD;
    (s2[i] += s2[i + 1]) %= MOD;
    (ans[a[i]] += s1[i + 1] + s2[i + 1]) %= MOD;
}

考虑这里的第 \(9\) 到 \(10\) 行也可以类似转化成先对整个 \([1,a_i-1)\) 的前缀全部加上贡献，再减去多余的。可以发现，对于每个 \(a_i\)，它被减去的贡献来自于满足 \(j>i,a_j>a_i\) 的所有 \(j\)。直接倒着做二维偏序就行了。\(O(n\log n)\)。

for (int i = 1; i <= k; i++){
    int val = fac[n - i] * inv[n - k] % MOD;
    int vl = val * (k - i) % MOD * iv[n - i] % MOD;
    int cnt = a[i] - 1 - c1.query(a[i] - 1);
    s1[i] = cnt * val % MOD;
    s2[i] = (MOD - cnt * vl % MOD) % MOD;
    s3[a[i] - 1] += (val - vl + MOD) % MOD;
    (dlt += cnt * vl % MOD) %= MOD;
    c1.add(a[i], 1);
}
for (int i = k; i; i--){
    int val = fac[n - i] * inv[n - k] % MOD;
    int vl = val * (k - i) % MOD * iv[n - i] % MOD;
    ans[a[i]] -= c2.query(n) - c2.query(a[i]);
    ans[a[i]] = (ans[a[i]] + MOD) % MOD;
    c2.add(a[i], (val - vl + MOD) % MOD);
}
for (int i = k; i; i--){
    (s1[i] += s1[i + 1]) %= MOD;
    (s2[i] += s2[i + 1]) %= MOD;
    (ans[a[i]] += s1[i + 1] + s2[i + 1]) %= MOD;
}
for (int i = n; i; i--) (s3[i] += s3[i + 1]) %= MOD;
for (int i = 1; i <= n; i++) printf("%lld\n", ((ans[i] + s3[i] + dlt) % MOD + MOD) % MOD);

C. 雷暴

显然每个值的答案为 \(\max{(maxx-minx,maxy-miny)}^2\)。

D. 神力

做法是设 \(f_{i,j}\) 表示执行了 \(i\) 到 \(n\) 的操作，经过位置 \(j\) 的概率。直接分讨是否执行当前操作，倒着转移即可。正确性难以理解，大概是说这样除了 \(0\) 以外的位置都不会算重，而经过 \(0\) 的概率又是 \(1\)，所以每层转移都将 \(f_{i,0}\) 设置为 \(1\) 就不会算重了。待进一步理解。

E. 圆

注意到 \(n\) 并不大，考虑区间 dp。设 \(dp_{l,r}\) 表示区间不一定删完的最大价值，\(f_{l,r}\) 表示一定删完的最大价值，\(g_{l,r,k}\) 表示最后一次删长度为 \(k\) 的段，一定删完的最大价值（不计算最后一次的贡献）。最后答案为 \(dp_{1,n}\)。

考虑转移。对于 \(dp_{l,r}\)，枚举一个断点 \(k\)，\(dp_{l,r}=\max(f_{l,r},dp_{l,k}+dp_{k+1,r})\)。

对于 \(f_{l,r}\)，枚举最后一次删掉的段的长度 \(k\)，\(f_{l,r}=\max(g_{l,r,k}+v_k)\)。

对于 \(g_{l,r,k}\)，考虑左端点和右端点是否一起删除，则 \(g_{l,r,k}=\max(g_{l+1,r-1,k-2}[s_l=s_r],f_{l,mid}+g_{mid+1,r,k},g_{l,mid,k}+f_{mid+1,r})\)。

直接转移即可。注意细节。

F. 菜？橙！

Part1

难点在于第一步，要想到通过给边赋权的方式将要求的生成树转化为最小生成树。将题目中所给限制拆成两个：\(u\) 最小和 \(v\) 最大。那么通过两种赋权方式分别满足这两个条件并保证最小生成树唯一。

第一种：每条边权为 \((n+1)v_i-u_i\)。

第二种：每条边权为 \(v_i-(n+1)u_i\)。

考虑如何证明，以第一种为例。第二种的证明同理。

首先证明唯一性。考虑反证法，假设存在边权相同的边 \((u,v)\) 和 \((x,y)\)，不妨设 \(v>y\)（\(v,y\) 相等的情况，因为不存在重边，所以两条边的边权显然不相等），那么移项得到 \((n+1)(v-y)=u-x\)。

但这显然是不可能的，因为 \(u-x<n\)，而 \((n+1)(v-y)>n\)，两者不可能相等。因此不可能存在边权相同的边，考虑 kruskal 算法的过程，没有相等的边，遍历边的顺序也不能调换，从而最小生成树也是唯一的。

接下来证明要求的生成树一定是这颗最小生成树。还是反证法，假设现在的树不是最小生成树，那么一定有一条边 \((u,v)\) 能替换掉这条路径上的某条权值更大的边 \((x,y)\)。那么移项得到 \((n+1)(v-y)<u-x\)。因为 \(v\) 是路径上编号最大的点，于是得到 \(v-y>0\)，所以这个式子同样不可能成立。因此要求的生成树一定是最小生成树。

接下来证明最小生成树满足 \(v\) 是路径上最大的点。考虑 \(u\) 到 \(v\) 路径上的某一条边 \((x,y)\)，因为当前的生成树已经是唯一的最小生成树，那么一定满足 \((n+1)v-u>(n+1)y-x\)，移项得到 \((n+1)(v-y)>u-x\)。继续反证，假设 \(v<y\)，那么因为 \(|(n+1)(v-y)|>|u-x|\)，而 \(v-y\) 又是负数，所以 \((n+1)(v-y)<u-x\)，矛盾。因此对于路径上的所有 \(y\)，都满足 \(y<v\)，自然有 \(v\) 是 \(u\) 到 \(v\) 路径上编号最大的点。

还有一种理解方式。先尝试将边权设为 \(\max(u,v)\)，这时上方证明的最后两个性质就很显然了，但这样做的最小生成树不具有唯一性，所以要找到另一种不存在相同边权，但排序方式类似的赋权方式。注意到这样赋权就相当于把所有边按 \(v\) 为第一关键字从小到大，\(u\) 为第二关键字从大到小排序，于是想到正解使用的这一种 \((n+1)v-u\)。

Part2

因为分别满足这两个条件的两颗生成树都在这种赋权方式下具有唯一性，那么同时满足两个条件的生成树就一定与两者相同，也就是说两颗生成树需要一样。那么现在就要：快速得到删除某条边后图的最小生成树，并快速判断两颗最小生成树是否相同。判断相同很简单，只要给每条边赋一个随机权值，记录所有树边的随机权值的和就行了。

现在考虑第一个问题。删除一条边后，原本的最小生成树会断成两个连通块。通过 kruskal 算法的过程可以发现，只要加上连接这两个连通块的最小边（不包括删去的）就能得到新的最小生成树。也就是说，对于每条在最小生成树中的边，需要找到权值最小的一条连接这条树边连接的两个连通块的非树边。

考虑用每条非树边去更新所有树边的答案。容易发现一条非树边 \((u,v)\) 能更新的只有最小生成树中 \(u\) 到 \(v\) 路径上的边。那么对于一条非树边，我们要做的操作就是将树上某条路径上所有边的答案跟这条非树边的权值取 \(\min\)。这样的操作明显可以树剖维护，使用线段树维护区间对一个数取 \(\min\)，单点查询即可。

标签：int,边权,最小,20241009,生成,模拟,考虑,dp
From： https://www.cnblogs.com/luyuyang/p/18535169

20241009 模拟赛