题意：
给你一张图， 你每次选一个联通块，每个点有个权值， 你可以设所有权值减一， 当有权值为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\n", ans);
}
}
题意： 给一个 斐波拉契数列， 个一个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\n", i);
break;
}
}
}
}
题解：
有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\n", ans);
}
}
2020 Multi-University Training Contest 2
原文：https://www.cnblogs.com/BOZHAO/p/13369821.html