没参加这场比赛，赛后做了下DE题，还是写下题解吧。。。
D.牛牛的呱数
题意：
牛牛和小青蛙Froggy是好朋友。
牛牛有 n 种很大的数，每种数有无限个，牛牛可以从这些数中任选若干个（至少1个），并把它们拼接起来，拼接顺序任意，所有可以被这样拼接起来的数被成为“呱数”。
如果一个“呱数”还满足它是 p 的倍数，牛牛称它为“p-呱数”。
求长度最短的 “p-呱数” 的长度是多少。
若无解则输出 -1。
(pleq 200,nleq 100。)
思路：
这个题和这里的C题有点类似。
最直接的想法就是建图然后(bfs)，注意到这个题中状态空间只有(O(ncdot p))的大小，所以我们可以在(O(ncdot p))的状态空间中跑最短路，最后直接求解就行。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/26 10:08:06
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 100 + 5, M = 1e6 + 5;
int n, P;
int w[N];
int dis[N][N << 1];
int Pow10[M];
void run() {
cin >> n >> P;
Pow10[0] = 1;
for (int i = 1; i < M; i++) {
Pow10[i] = 1ll * Pow10[i - 1] * 10 % P;
}
vector <string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int j = 0; s[i][j]; j++) {
w[i] = (w[i] * 10 + s[i][j] - '0') % P;
}
}
auto bfs = [&] () {
memset(dis, INF, sizeof(dis));
dis[0][0] = 0;
queue <pii> q;
q.push(MP(0, 0));
while (!q.empty()) {
pii now = q.front(); q.pop();
int u = now.fi, cur = now.se;
for (int i = 0; i < n; i++) {
int len = s[i].length();
if (dis[i + 1][(1ll * cur * Pow10[len] % P + w[i]) % P] > dis[u][cur] + len) {
dis[i + 1][(1ll * cur * Pow10[len] % P + w[i]) % P] = dis[u][cur] + len;
q.push(MP(i + 1, (1ll * cur * Pow10[len] % P + w[i]) % P));
}
}
}
int ans = INF;
for (int i = 1; i <= n; i++) {
ans = min(ans, dis[i][0]);
}
if (ans == INF) ans = -1;
return ans;
};
int ans = bfs();
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
这个题还有一种更为简单的做法，我们注意到每次经过一个串的过程有点类似于一个有限自动机，将当前状态(p
ightarrow p')，会消耗一定的代价。
那么我们预处理出(f[p_1][p_2])表示从模(p)为(p_1)到达模(p)为(p_2)的最小代价。之后通过floyd算法求解两点间最短路即可。
最后答案为(f[0][0])。
E.水灾
题意：
给一个 n 个节点 m 条带权边的无向连通图，有 q 次询问，每次询问图中 ki 个互不相同的点，你可以选择一个数 x，然后将图中所有边权小于等于 x 的边删除。求当删除这些边后 ki 个点互不连通时，x 的最小值。
思路：
- 通过“在树中所有权值小于等于(x)”这一信息我们可以猜到做 法是kruskal重构树，因为在kruskal重构树中满足路径间边权最大值不超过(x)的所有结点都在一颗子树内。
- 考虑将kruskal重构树建出来，那么此时我们要去掉某些结点，使得所有关键点两两不连通。
- 这个题我们是通过边权从大到小来建树，显然树中任意一结点权值都不超过其子树的权值。那么我们要使得最终答案最小，也就是需要求任意两个关键点(lca)的权值的最大值。
- 这里我们将所有结点按照(dfn)序从小到大排序，然后取相邻两个结点的(lca)权值最大值作为答案即可。
最后一步是挺常见的一个技巧：将任意两点的关系转化为按一定顺序排列过后两点的关系。因为不相邻两点的(lca)的深度一定不超过中间相邻两点的(lca)，也就是其权值会更小。而我们需要的信息为权值的最大值，所以此时一定不是最优解。
这个题有点卡常。。存图时要用邻接链表来存。
感觉kruskal重构树关键的地方就是在于将边权的问题转化为树上点权的问题，而树上的某些问题我们就可以通过一些常见的算法来解决，比如求(lca)等等。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/26 17:05:11
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 5e5 + 5;
int n, m, q;
int nodes[N], num;
struct Edge {
int v, next, w;
}e[N << 1];
int head[N << 1], tot;
void adde(int u, int v) {
e[tot].v = v, e[tot].next = head[u], head[u] = tot++;
}
vector <int> G[N << 1];
int fa[N << 1], val[N << 1];
int find (int x) {
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
int f[N << 1][20], deep[N << 1], dfn[N << 1], T;
void dfs(int u, int fa) {
dfn[u] = ++T;
deep[u] = deep[fa] + 1;
f[u][0] = fa;
for(int i = 1; i < 20; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v != fa) dfs(v, u);
}
}
int LCA(int x, int y) {
if(deep[x] < deep[y]) swap(x, y);
for(int i = 19; i >= 0; i--) {
if(deep[f[x][i]] >= deep[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = 19; i >= 0; i--) {
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
}
return f[x][0];
}
void Kruskal (vector <pair<int, pii>>& edges) {
for (int i = 1; i <= n << 1; i++) {
fa[i] = i;
}
sort(all(edges), [&] (pair<int, pii> A, pair<int, pii> B) {
return A.fi > B.fi;
});
int cnt = n;
for (int i = 0; i < sz(edges); i++) {
int u = edges[i].se.fi, v = edges[i].se.se, w = edges[i].fi;
int x = find(u), y = find(v);
if (x != y) {
val[++cnt] = w;
fa[x] = fa[y] = cnt;
adde(cnt, x), adde(cnt, y);
}
}
dfs(cnt, 0);
}
void run () {
memset(head, -1, sizeof(head));
cin >> n >> m >> q;
vector <pair<int, pii>> e;
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
e.push_back(MP(w, MP(u, v)));
}
Kruskal(e);
int lastans = 0;
while (q--) {
int k; cin >> k;
num = 0;
for (int i = 1; i <= k; i++) {
int x; cin >> x; x ^= lastans;
nodes[++num] = x;
}
sort (nodes + 1, nodes + num + 1, [&](int a, int b) {
return dfn[a] < dfn[b];
});
int ans = 0;
for (int i = 2; i <= num; i++) {
ans = max(ans, val[LCA(nodes[i - 1], nodes[i])]);
}
cout << ans << '
';
lastans = ans;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}