QBXT2025S刷题 Day7

今天的题
很拉了，\(100pts\)，\(rk70+\)。
今天这个老师讲题好有意思啊。

T1

如果 \(a[i] = b[i]\)，则这个数非出现不可。
如果不相等，我们就可以把我们不想要的数换掉。
因此我们从 \(0\) 开始枚举，看看这个数是否必须出现。
如果不必出现，那我们就直接输出。
然后我们看一看如果一个位置如果 \(a[i]\) 和 \(b[i]\) 都不是我们找到的 \(\text{mex}\)，这两个数就可以随意交换，就把答案乘上 \(2\)。
代码：

//☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
//░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
//░░░░░░░░░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░░░░░░░░░░░
//░░░░░░░░░░░░░░░░░░░░░█▀▀▀▄░░▀▀▀▄▄░░░░░░░░░░░░░░░
//░░░░░░░░░░░░░░░░░░░░░█▄▄▄░▀▀▄▄░░░▀▀▄░░░░░░░░░░░░
//░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▄▄░▀▄░░░░▀▄░░░░░░░░░░
//░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░▀▄░░░░▀▄░░░░░░░░
//░░░░░░░░░░░░░░░░░▄▀▀▀▀▀▀▀▀▄░░░░▀▄░█░░░░▀▄░░░░░░░
//░░░░░░░░░░░░░░░▄▀░░░░░░░░░░█░░░░░█░█░░░░▀▄░░░░░░
//░░░░░░░░░░░░░▄▀░░░░░░░░░░░▄█░░░░░░█░█░░░░▀▄░░░░░
//░░░░░░░░░░░▄▀░░░░░░░░░░░▄▀░█░░░░░░░█░█░░░░█░░░░░
//░░░░░░░░░▄▀░░░░░░░░░░░░█░▄▀░░░░░░░░░█▀█░░░░█░░░░
//░░░░░░░░█░░░░░░░░░░░░░░░▀▄░░░░░░░░░░▀▄█░░░░█░░░░
//░░░░░░░░█▄░░░░░░░░▄▄░░░░░░▀▄░░░░░░░░░██░░░░█░░░░
//░░░░░░░░█░▀▄░░░░▄▀░░▀▄░░░░░░▀▄░░░░░░░██░░░░█░░░░
//░░░░░░░░░▀▄░▀▄▄▀░▄▀▀▄░▀▄░░░░░░▀▄░░░░░█░░░░░█░░░░
//░░░░░░░░░░░▀▄█░▄▀░░░░▀▄░▀▄░░░░░░▀▄░░▄▀░░░░▄█░░░░
//░░░░░░░░░░░░░▀▀░░░░░░░░▀▄░▀▄░░░░░░▀▄▀░░░░░██░░░░
//░░░░░░░░░░▄▀▀▀▀▄░░░░░░░░░▀▄░▀▄░░░░░░░░░░░██░░░░░
//░░░░░░▄▄▀▀░░░░░░█▄░░░░░░░░░▀▄░█░░░░░░░░░▄█▀░░░░░
//░░░░▄▀░░░░░░░░░░░░▀▀▀▄▄▄▄▄▄▄▄▀░░░░░░░░░░▀█░░░░░░
//░░░█░░░░░░░░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░░░░
//░░█░░░░░░░░▄▀░▀█░░░░░░░░░░░░░░░░░░█▀▀█░░░░░░▀▄░░
//░░█░░░░░░░▄▀▄▀▄░▀▀▀▀▄▄▄▄▄▄▄▄▄▄▄▀▀▀░▄▄░▀█░░░░░█░░
//░░█▀▄▄▄▄▀▀░▄▀░░▀▄▄▄▄░░░░░░░░░░░▄▄▄▀░░▀▄░▀▄▄▄▀█░░
//░░▀▄░░░░▄▄▀░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░░▀▄░░░▄▀░░
//░░░░▀▀▀▀░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀░░░░
//░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
//☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
#include <iostream>
#include <unordered_map>
#include <cstdio>
#include <vector>
#define int long longusing std::cin;
using std::cout;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;int a[N];
int b[N];
std::vector<int> where[N];signed main()
{int n;cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];if (a[i] <= n)where[a[i]].push_back(i);}for (int i = 1; i <= n; ++i)cin >> b[i];int t = -1;for (int i = 0; i <= n; ++i){bool f = true;for (auto it : where[i]){if (a[it] == b[it]){f = false;break;}}if (f){t = i;break;}}cout << t << ' ';int ans = 1;for (int i = 1; i <= n; ++i){if (a[i] != t && b[i] != t)ans = 1ll * ans * 2 % mod;}cout << ans << '\n';return 0;
}

T2

我们考虑 \(\mathcal{DP}\)，我们令 \(dp[i][j]\) 表示考虑到 \(i\)，选了 \(j\) 个字符，字典序最大的字符串。
很好转移。

// ☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░▄▄▄▄▄▄▄░░░░░░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░█▀▀▀▄░░▀▀▀▄▄░░░░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░█▄▄▄░▀▀▄▄░░░▀▀▄░░░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▄▄░▀▄░░░░▀▄░░░░░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░▀▄░░░░▀▄░░░░░░░░
// ░░░░░░░░░░░░░░░░░▄▀▀▀▀▀▀▀▀▄░░░░▀▄░█░░░░▀▄░░░░░░░
// ░░░░░░░░░░░░░░░▄▀░░░░░░░░░░█░░░░░█░█░░░░▀▄░░░░░░
// ░░░░░░░░░░░░░▄▀░░░░░░░░░░░▄█░░░░░░█░█░░░░▀▄░░░░░
// ░░░░░░░░░░░▄▀░░░░░░░░░░░▄▀░█░░░░░░░█░█░░░░█░░░░░
// ░░░░░░░░░▄▀░░░░░░░░░░░░█░▄▀░░░░░░░░░█▀█░░░░█░░░░
// ░░░░░░░░█░░░░░░░░░░░░░░░▀▄░░░░░░░░░░▀▄█░░░░█░░░░
// ░░░░░░░░█▄░░░░░░░░▄▄░░░░░░▀▄░░░░░░░░░██░░░░█░░░░
// ░░░░░░░░█░▀▄░░░░▄▀░░▀▄░░░░░░▀▄░░░░░░░██░░░░█░░░░
// ░░░░░░░░░▀▄░▀▄▄▀░▄▀▀▄░▀▄░░░░░░▀▄░░░░░█░░░░░█░░░░
// ░░░░░░░░░░░▀▄█░▄▀░░░░▀▄░▀▄░░░░░░▀▄░░▄▀░░░░▄█░░░░
// ░░░░░░░░░░░░░▀▀░░░░░░░░▀▄░▀▄░░░░░░▀▄▀░░░░░██░░░░
// ░░░░░░░░░░▄▀▀▀▀▄░░░░░░░░░▀▄░▀▄░░░░░░░░░░░██░░░░░
// ░░░░░░▄▄▀▀░░░░░░█▄░░░░░░░░░▀▄░█░░░░░░░░░▄█▀░░░░░
// ░░░░▄▀░░░░░░░░░░░░▀▀▀▄▄▄▄▄▄▄▄▀░░░░░░░░░░▀█░░░░░░
// ░░░█░░░░░░░░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▄░░░░
// ░░█░░░░░░░░▄▀░▀█░░░░░░░░░░░░░░░░░░█▀▀█░░░░░░▀▄░░
// ░░█░░░░░░░▄▀▄▀▄░▀▀▀▀▄▄▄▄▄▄▄▄▄▄▄▀▀▀░▄▄░▀█░░░░░█░░
// ░░█▀▄▄▄▄▀▀░▄▀░░▀▄▄▄▄░░░░░░░░░░░▄▄▄▀░░▀▄░▀▄▄▄▀█░░
// ░░▀▄░░░░▄▄▀░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░░▀▄░░░▄▀░░
// ░░░░▀▀▀▀░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
// ☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭☭
#include <iostream>
#include <string>
#include <algorithm>using std::cin;
using std::cout;
const int N = 56;
struct Node
{std::string a;std::string b;std::string c;
};Node dp[N][N];int main()
{std::string a, b, c;cin >> a >> b >> c;int n = a.size();for (int i = 0; i < n; ++i){std::string p1, p2, p3;p1 = p2 = p3 = "";p1 += a[i];p2 += b[i];p3 += c[i];dp[i][1] = (Node){p1, p2, p3};}for (int i = 1; i < n; ++i){for (int j = 2; j <= i + 1; ++j){for (int k = 0; k < i; ++k){std::string A = dp[k][j - 1].a + a[i];std::string B = dp[k][j - 1].b + b[i];std::string C = dp[k][j - 1].c + c[i];if (A + B + C > dp[i][j].a + dp[i][j].b + dp[i][j].c)dp[i][j] = {A, B, C};}}}std::string ans = "";for (int i = 0; i < n; ++i){for (int j = 1; j <= i + 1; ++j)ans = std::max(ans, dp[i][j].a + dp[i][j].b + dp[i][j].c);}cout << ans << '\n';return 0;
}

T3

我们发现，从右上到左下的对角线上的点不能互相到达。
对角线分割了起点和终点，让他们不能互相到达，因此必须经过对角线。
我们把所有的点放到行列的交点处。
考虑障碍物。
我们把与障碍物相邻的框并在一起。
其他的框独自成为一个连通块
我们把超级源点 \(s\) 与最左面、最下面的连通块连边，再把每个连通块和与它右上方的连通块连一条边。
再把最上面的连通块、最右面的连通块与超级汇点 \(t\) 连边。
则从 \(s\) 到 \(t\) 的一条边就正好分割了左上和右下。
于是，我们统计从 \(s\) 到 \(t\) 的路径条数就行。

T4

老师：

要把自己看成商人，带入到情境中去

如果我们开通了一个城市之后，与他相连的一个点也可以赚钱，那么我们就把相连的一个点看成这个点的附赠品，直接让 \(a[x] += (a[y] - w[y])\)，看成一段生意。
我们还要把一段段生意组合起来，是这个生意尽量能赚大钱。
可以把通行证看成门槛
这个商人：

1. 要赚最多的钱。
2. 要满足门槛。