NOIP2023模拟5联测26 题解

感觉我这场的官方题解写的是真的挺好的，所以我只能作少量补充。你可以直接去看官方题解，如果你想的话。

T1 x

题解

$n = 2$ 没啥可说的。$\color{white}{这档分你要是没拿到那你还是蛮强的。}$

$n = 3$ 的时候，我们需要比较 $(a_1^{a_2})^{a_3}$ 与 $a_1^{(a_2^{a_3})}$ 的大小。

稍微变一变形，就是比较 $a_1^{a_2 \cdot a_3}$ 与 $a_1^{(a_2^{a_3})}$ 的大小。

这就很好比了，直接比 $a_2 \cdot a_3$ 与 $a_2^{a_3}$ 的大小就好了。

所以当 $a_2 > 1$ 时，直接用 $a_2 \cdot a_3$ 当做 $a_1$ 的指数就好了。

但当 $a_2 = 1$ 时，我们让 $a_2^{a_3}$，即 $1$，作为 $a_1$ 的指数就好了。

那么对于所有的情况，我们先设一个 $tot$，为 $a_1$ 最终的指数。

然后我们从 $2$ 到 $n$ 枚举 $i$，如果 $a_i \not= 1$，直接让 $tot$ 乘上 $a_i$，如果 $a_i = 1$，直接停就好了。

然后快速幂就好了。

注意一下费马小定理的应用就好了。

就好了。

代码

点击查看代码

#include <bits/stdc++.h>
#define int long long
#define mod 998244353

using namespace std;

int n, a, ans = 1, tot = 1, x;

inline int quick_pow(int base, int ci) {
    int res = 1;
    while(ci) {
        if(ci & 1)
            res = res * base % mod;
        base = base * base % mod;
        ci >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> a;
    if(a == 1) {
        putchar('1');
        return 0;
    }
    for(int i = 2; i <= n; ++ i) {
        cin >> x;
        if(x == 1)
            break;
        tot *= x;
        tot %= (mod - 1);
    }
    cout << quick_pow(a, tot) << '\n';
}

T2 u

题解

先设个东西，下面要用：$\displaystyle f(x) = \frac{x (x - 1)}{2}$

假设对于一个权值 $val$，我们去考虑所有权值小于 $val$ 的边。

先来考虑给定的、权值小于 $val$ 的边。假设这些边将图连成了 $k$ 个连通块，块的大小分别为 $s_1, s_2, \dots, s_k$。

再来考虑没有给定的、权值小于 $val$ 的边。我们要让加边前后最小生成树的权值不变，那么我们需要让这些边所连接的两个端点在同一块内，否则最小生成树的边集一定会包含那个边。如果理解不了的话，你可以去考虑 Kruskal 的过程：我们要按边权从小到大枚举每一条边，如果当前边的两个端点在同一块内就不进行操作，否则将它们所在的块合并。那么对于这些没有给定的边，我们要让这些边的左右端点在同一块内，才不会对最终的最小生成树造成影响。

所以我们现在需要考虑，能否让所有权值小于 $val$ 的、没有给定的边的两个端点在同一块内。不好直接判断，那么我们就去算一下当前局势还能容纳多少没有给定的边。

对于这 $k$ 个块，我们不能合并任意两个块，那么一共最多会有 $sum = f(s_1) + f(s_2) + \dots + f(s_k)$ 条边。所以当且仅当没有给定的、权值小于 $val$ 的边数小于等于 $sum - $ 块内相连的给定的边时，当前局势合法，也就是最终答案可能为 $Yes$。

如果对于每一个 $val$，当前局势都是合法的，那么最终答案才为 $Yes$，只要有任一局势不合法，最终答案就为 $No$。

考虑怎么实现。

维护块，并查集会吧？

维护块的大小，并查集的 $size$ 会吧？

维护块内相连的边的数量，将一个点的出边转给另一个点会吧？

然后我们再来考虑其他的。

不难发现，我们不需要对于每一个权值都判断一下是否合法（$M \le 19999900000$，每个权值都判断会 T 飞），因为保证给出的 $m$ 条边能使所有点连通，并且如果没有给定边权为 $val - 1$ 的边且 $val$ 的局势合法，那么 $val - 1$ 的局势一定也合法，所以我们只需要枚举给出的 $m$ 个边权即可。

然后考虑怎么维护 $sum$。假设这次操作将大小为 $s_1$、$s_2$ 的两个块合并，那么新的 $sum$ 等于原来的 $sum + s_1 \times s_2$。

嗯，没有了，自己打去吧。

~~感觉我说的不是人话。~~

代码

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 500005;
struct E {
    int w;
    int u;
    int v;
}edge[N];

int n, m, sum, fa[N], siz[N], tot;
vector<int> e[N];

inline bool cmp(E a, E b) {return a.w < b.w;}

inline int findf(int x) {
    while(x != fa[x])
        x = fa[x] = fa[fa[x]];
    return x;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
        fa[i] = i, siz[i] = 1;
    for(int i = 1; i <= m; ++ i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
        e[edge[i].u].push_back(edge[i].v);
        e[edge[i].v].push_back(edge[i].u);
    }
    stable_sort(edge + 1, edge + 1 + m, cmp);
    for(int i = 1; i <= m; ++ i) {
        if(edge[i].w - i > sum - tot) {
            cout << "No\n";
            return 0;
        }
        int fu = findf(edge[i].u), fv = findf(edge[i].v);
        if(fu != fv) {
            if(siz[fu] > siz[fv])
                swap(fu, fv);
            sum += siz[fu] * siz[fv];
            for(int j = 0; j < e[fu].size(); ++ j) {
                if(findf(e[fu][j]) != fv)
                    e[fv].push_back(e[fu][j]);
                else
                    ++ tot;
            }
            siz[fv] += siz[fu];
            fa[fu] = fv;
        }
    }
    cout << "Yes\n";
}

T3 a

题解

Subtask 1：

暴力枚举。

Subtask 2：

状压 dp。题解是这么说的，但我不知道压啥。

Subtask 3：

单降了都，那就是个栈。卡特兰数。单增输出 $1$ 就行。

Subtask 4：

一个 $B$ 序列合法，当且仅当 $1$ 和 $2$ 的数量与 $A$ 序列相同，并且对于每一个 $i$，$B$ 的长度为 $i$ 的前缀中 $1$ 的数量都不少于 $A$ 的长度为 $i$ 的前缀中 $1$ 的数量。

所以直接 dp 即可。

Subtask 5：

已经很接近正解了。

我们设 $n$ 在 $A$ 序列和 $B$ 序列中的位置分别为 $p, q$，即 $A_p = B_q = n$。

考虑到，这是一个小根堆，而且这是一个排列，所以我们拿出 $n$ 就意味着堆此时空了。所以 $B$ 的前 $q$ 个元素就是 $A$ 的前 $q$ 个元素，只不过顺序可能不太一样。所以 $\{A_1, A_2, \dots, A_q\} = \{B_1, B_2, \dots, B_q\}$，且 $\{A_{q + 1}, A_{q + 2}, \dots, A_n\} = \{B_{q + 1}, B_{q + 2}, \dots, B_n\}$。

然后我们已经知道 $B_q = n$，所以我们可以把原问题看做两个子问题：$[1, q - 1]$ 和 $[q + 1, n]$。其中，$B_1, B_2, \dots, B_{q - 1}$ 是由 $A_1, A_2, \dots, A_q$ 去掉 $A_p$ 经过一些操作变化而来的，而 $B_{q + 1}, B_{q + 2}, \dots, B_n$ 是由 $A_{q + 1}, A_{q + 2}, \dots, A_n$ 经过一些操作变化而来的。

所以我们考虑递归地解决子问题。

找当前序列的最大值，然后枚举其在 $B$ 中的位置，然后分成两个子序列，分治。注意左边要把最大值删去。不难看出来，子序列 $A'$ 一定是原序列 $A$ 的某一区间 $[l, r]$ 删掉一些较大数后得到的。

整合一下现在的信息，我们发现持续在变化的当前只有处理的子序列 $A'$ 所对应的 $l, r$，以及删掉了哪些数。所以我们设 $f_{l, r, i}$ 表示 $A_l, \dots, A_r$ 中，不超过 $i$ 的数构成的子序列的答案，或者说是情况数。

考虑怎么转移。

当 $i$ 不在 $[l, r]$ 时，$f_{l, r, i} = f_{l, r, i - 1}$，这很显然。
当 $i$ 在 $[l, r]$ 时，我们假设 $A_m = i$，那么我们再去枚举 $i$ 在 $B$ 中的位置 $x$，就有：

\[\begin{aligned} f_{l, r, i} = \sum_{x = m}^r f_{l, x, i - 1} \cdot f_{x + 1, r, i - 1} \end{aligned}\]

如果你看了官方题解那个式子，你会发现不太一样，但是结果是一样的，因为这是一个排列，所以在 $[x + 1, r]$ 中不会再出现一个 $i$，所以 $f_{x + 1, r, i - 1} = f_{x + 1, r, i}$，至于为什么我这么写，因为我觉得这样可能更好理解。

直接 dp 就行了，时间复杂度 $O(n^4)$，能过。

Subtask 1 $\sim$ 5：

我们考虑怎么处理 $A$ 是一个数列而不是排列的情况。

假设一个数 $i$ 出现次数大于 $1$，那么我们将其第 $j$ 次出现设为 $i_j$。

首先，我们约定，如果堆中最小值为 $i$，并且堆中存在多个 $i$，那么我们在取的时候先取下标最小的，也就是值相等的情况下满足先进先出的原则。

换句话说，$a_b < c_d$ 当且仅当 $a < c$，或者 $a = c$ 且 $b < d$。

那么在我们约定的条件下，可以把原数列转化为一个排列。

考虑这样转化的正确性。

转化后 $B$ 序列中的每一个数都能唯一对应未转化的 $B$ 序列中的一个数，而且如果 $j < j'$，那么一定有 $i_j$ 在 $B$ 中排在 $i_{j'}$ 之前，这样就得到了一个自然双射，也就完成了证明。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int mod = 1000000007;
int n, a[N], b[N], cnt[N], rk[N], f[N][N][N];

signed main() {
	cin >> n;
	for(int i = 1; i <= n; ++ i)
        scanf("%d",a + i), ++ cnt[a[i]];
	for(int i = 1; i <= n; ++ i)
        cnt[i] += cnt[i - 1];
	for(int i = n; i; -- i)
        b[i] = cnt[a[i]] --, rk[b[i]] = i;
	for(int i = 1; i <= n + 1; ++ i)
		fill(f[i][i - 1], f[i][i - 1] + n + 1, 1);
	for(int l = n; l; -- l) {
        for(int r = l; r <= n; ++ r) {
            f[l][r][0] = 1;
            memcpy(f[l][r] + 1, f[l][r - 1] + 1, 4 * b[r] - 4);
            memcpy(f[l][r] + 1, f[l + 1][r] + 1, 4 * b[l] - 4);
            for(int i = max(b[l], b[r]); i <= n; ++ i)
                if(rk[i] < l || rk[i] > r)
                    f[l][r][i] = f[l][r][i-1];
                else
                    for(int j = rk[i]; j <=r; ++ j)
                        if(b[j] <= i)
                            f[l][r][i] = (f[l][r][i] + 1ll * f[l][j][i - 1] * f[j + 1][r][i]) % mod;
        }
    }
	cout << f[1][n][n];
}