2020 Multi-University Training Contest 2
HUD 6763 The Oculus
题意：
给你一张图， 你每次选一个联通块，每个点有个权值， 你可以设所有权值减一， 当有权值为0是， 与这个点连接的边将断开， 问最少操作多少次能使所有点的权值为0.
题解：
如果暴力， 那么每次肯定是一快减去最小值，然后分成n个块继续每个块减去去小值， 然后又分成n个块……
时间复杂度 > (n ^ 2)那肯定是过不了的。
如果你能再脑海里把这个操作倒着想一边， 你应该就能明白怎么写了。
如果你想不通就再想一边。
太困了我不想解释了， 一句两句也说不清。 自己想吧。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
vector<int> g[N];
int n, m, t, a[N], fa[N];
int find(int x) {
if (x != fa[x]) {
return fa[x] = find(fa[x]);
}
return x;
}
vector<pair<int, int> >v;
int vis[N];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
v.clear();
for (int i = 0; i <= n; i++) {
fa[i] = i;
g[i].clear();
vis[i] = 0;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v.push_back({a[i], i});
}
sort(v.begin(), v.end(), [](pair<int, int> x, pair<int, int> y) {
return x.first > y.first;
});
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
ll ans = 0;
ll count = 0;
v.push_back({0, 0});
for (int i = 0; i < v.size() - 1; i++) {
int pos = v[i].second;
int cost = v[i].first;
int fx = find(pos);
vis[pos] = 1;
count++;
for (int to: g[pos]) {
if (!vis[to]) continue;
int fy = find(to);
if (fx != fy) {
fa[fy] = fx;
count--;
}
}
ans += (count) * 1ll*(cost - v[i + 1].first);
}
printf("%lld
", ans);
}
}
hdu 6768 The Oculus
题意： 给一个 斐波拉契数列， 个一个01串 a, b第i有1表示 a串的值 加上fn[i] (fn为斐波拉契数列)。
a * b = c + fn[i] 让你求i
题解：
fn[i] = a * b - c;
由于 a * b溢出 所有取模 找个模数，使得 fn[i] % mod != fn[j] % mod
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
ll fn[N];
int t, n, m;
int main() {
fn[1] = 1, fn[2] = 2;
ll mod = 787654321;
for (int i = 3; i < N; i++) {
fn[i] = (fn[i - 1] + fn[i - 2] ) % mod;
}
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
ll ans = 0;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
if (x == 1) {
ans = (ans + fn[i] ) % mod;
}
}
ll ans1 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
if (x == 1) {
ans1 = (ans1 + fn[i] ) % mod;
}
}
ll ans2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
if (x == 1) {
ans2 = (ans2 + fn[i] ) % mod;
}
}
ans = ((ans % mod * ans1 % mod)%mod - ans2 + mod) % mod;
for (int i = 1; i < N; i++) {
if (fn[i] == ans) {
printf("%d
", i);
break;
}
}
}
}
[hdu - 6772] (http://acm.hdu.edu.cn/showproblem.php?pid=6772)
题解：
有n个物品， 有t个种类， 每个种类取一个问贡献最大是多少。
题解：
直接dfs 暴力
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100;
int t, n, k;
struct node {
ll a, b, c, d;
};
vector<node>p[100];
vector<int>v;
ll ans;
void dfs(int pos, ll a, ll b, ll c, ll d) {
if (pos >= v.size()) {
ll cnt = (a + 100) * (b + 100) * (c + 100) * (d + 100);
ans = max(ans, cnt);
return;
}
for (int i = 0; i < p[v[pos]].size(); i++) {
dfs(pos + 1, a + p[v[pos]][i].a, b + p[v[pos]][i].b, c + p[v[pos]][i].c, d + p[v[pos]][i].d);
}
}
int main() {
scanf("%d", &t);
while (t--) {
ans = 0;
v.clear();
scanf("%d %d", &n, &k);
for (int i = 0; i <= k; i++) {
p[i].clear();
}
for (int i = 1; i <= n; i++) {
ll t, a, b, c, d;
scanf("%lld %lld %lld %lld %lld", &t, &a, &b, &c, &d);
p[t].push_back({a, b, c, d});
v.push_back(t);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
dfs(0, 0, 0, 0, 0);
printf("%lld
", ans);
}
}
hdu 6774 String Distance
题意：
给你一个字符串 a, b问， a中子串 l到r,每次操作可以删掉一个字符或者增加一个字符， 问最少操作多少次可以使 l 到r的子串等于 a.
题解：
我们发现操作 增加是没用用， 因为我们要再， a串中增加一个字符， 和再b串中删除一个字符效果是一样的。
所以最后匹配的就是两个字符串的 最长上升子序列， 答案就是 (r - l + 1 + m - 2 * lsc)
因b串的长度只有 20， 而询问有1e5， 如果直接求lcs复杂度肯定过不了。
所以用 一个序列自动机。
(nex[i][j])表示 字符 a中 第 i 个位置， 后面出现第一个字符 j的位置。
$dp[i][j] $ 表示 字符串 b 位于 第 i 个位置， 得到长度为j lsc 的 最后一个字符的最前面的位置。
(nex[i][j])很好求。
关键是 (dp[i][j])
初始化 (dp[i][j]) 无穷大， (dp[0][0] = l - 1， dp[i][0] = l - 1)
(dp[i][j] = min(dp[i][j], dp[i - 1][j]))
(dp[i][j] = min(dp[i][j], nex[dp[i - 1][j - 1]][t[i]]) and nex[dp[i - 1][j - 1][t[i]]] <= r)
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int t, n, m, nxt[N][200], vis[200], dp[300][300];
char a[N], b[30];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%s %s", (a + 1), (b + 1));
int la = strlen(a + 1), lb = strlen(b + 1);
for (int i = 'a'; i <= 'z'; i++) vis[i] = la + 10;
for (int i = la; i; i--) {
for (int j = 'a'; j <= 'z'; j++) {
nxt[i][j] = vis[j];
}
vis[a[i]] = i;
}
for (int j = 'a'; j <= 'z'; j++) nxt[0][j] = vis[j];
int q; scanf("%d", &q);
while (q--) {
int l, r; scanf("%d %d", &l, &r);
for (int i = 0; i <= lb; i++) {
for (int j = 0; j <= lb; j++) {
dp[i][j] = 1e8;
}
}
dp[0][0] = l - 1;
for (int i = 1; i <= lb; i++) {
dp[i][0] = l - 1;
for (int j = 1; j <= i; j++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j]);
if (dp[i - 1][j - 1] <= r &&nxt[dp[i - 1][j - 1]][b[i]] <= r) {
dp[i][j] = min(dp[i][j], nxt[dp[i - 1][j - 1]][b[i]]);
}
}
}
for (int i = lb; i >= 0; i--) {
if (dp[lb][i] <= r) {
printf("%d
", (r - l + 1 + lb) - 2 * i);
break;
}
}
}
}
}