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\)，就有：
如果你看了官方题解那个式子，你会发现不太一样，但是结果是一样的，因为这是一个排列，所以在 \([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];
}
T4 y
求教教，我只能看懂题解的一小部分。不太擅长串串和图论。
标签：dots,26,val,int,题解,sum,edge,NOIP2023 From： https://www.cnblogs.com/Meteor-streaking/p/17793940.html