个人赛链接: https://www.luogu.com.cn/contest/120853#description
今天只补了七道, 太难了呜呜呜...
A.Geodetic
解题思路
根据题意多源最短路肯定要用floyd算法, 而题目要求找到最短路中所有可能的中间点, 所有我们直接遍历所有点, 找到点i满足g[a][i] + g[i][b] == g[a][b], 则点i就是从a到b最短路的中间点; 这个题我一开始想的很复杂, 想要在floyd上做修改, 但是理解中间点这个需求之后就清晰多了;
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10, mod = 1e9 + 7;
int n, m, k,idx;
int g[50][50];
void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) g[i][j] = 0;
else g[i][j] = 1e9;
}
}
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = 1;
}
cin >> k;
floyd();
while (k--) {
int a, b;
cin >> a >> b;
for (int i = 1; i <= n; i++) {
if (g[a][i] + g[i][b] == g[a][b]) cout << i << ' ';
}
cout << endl;
}
return 0;
}
B.Wormholes G
解题思路
题意说是要倒退时间, 并且对走的这条路没有任何要求, 只要能回到起点就行; 所以放在图上其实就是找负环; 直接用spfa算法判断负环即可;
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k, idx;
int d[N], cnt[N];
int h[N], ne[N], e[N], w[N];
bool st[N];
vector<int> v;
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int spfa() {
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
queue <int >q;
for (int i = 1; i <= n; i++) {
q.push(i);
st[i] = true;
}
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] > n - 1) return 0;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return 1;
}
signed main() {
int t;
cin >> t;
while (t--) {
memset(h, -1, sizeof h);
idx = 0;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for (int i = 1; i <= k; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, -c);
}
if (!spfa()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
C.智能推荐
解题思路
根据题意, 必须解决前面的题才能解锁后面的题, 还是一个比较明显的拓扑序列问题; 用数组w[i]表示完成第i题的天数;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10, mod = 1e9 + 7;
int n, m, k, t, idx;
int d[N], w[N];
int h[N], ne[N], e[N];
bool st[N];
queue<int> q;
map<int, PII> mp;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void check() {
while (q.size()) {
int t = q.front();
if (t == m) {
cout << w[t];
return;
}
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j]--;
if (d[j] == 0) {
q.push(j);
w[j] = w[t] + 1;
}
}
}
cout << -1;
}
signed main() {
cin >> n >> m >> k;
memset(h, -1, sizeof h);
for (int i = 1; i <= k; i++) {
int a;
cin >> a;
w[a] = 0;
q.push(a);
}
cin >> t;
for (int i = 1; i <= t; i++) {
int a, b;
cin >> a >> b;
d[a] = b;
for (int j = 1; j <= b; j++) {
int c;
cin >> c;
add(c, a);
}
}
check();
return 0;
}
D.打鼹鼠
解题思路
一道类似于最长上升子序列的dp, 状态表示为d[i], 表示以第i只鼹鼠结尾的方案中打到鼹鼠数量最多的方案; 因为机器人初识位置任意, 所以我们可以把所有d[i]初始化为1; 状态计算时, 因为题目按时间递增输入, 省去了排序的过程; 我们先遍历i表示是以第i只鼹鼠结尾, 然后再遍历j, 表示第1 ~ i-1只鼹鼠, 然后我们看能不能把i插在j的后面, 计算出i和j两只鼹鼠之间的曼哈顿距离和时间差; 只要曼哈顿距离小于等于时间差, 那么就可以把i放在j的后面, 即dp[i] = max(dp[i], dp[j] + 1); 最后从d[1]~d[n]中找出最大值即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int dp[N], t[N];
PII f[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
f[i] = { b,c };
t[i] = a;
}
for (int i = 1; i <= m; i++) dp[i] = 1;
for (int i = 1; i <= m; i++) {
int a = f[i].first, b = f[i].second;
for (int j = 1; j < i; j++) {
int c = f[j].first, d = f[j].second;
int dis = abs(a - c) + abs(b - d);
if (dis <= abs(t[i] - t[j])) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int maxn = 0;
for (int i = 1; i <= m; i++) {
maxn = max(maxn, dp[i]);
}
cout << maxn;
return 0;
}
F.Superbull S
解题思路
如果不看标签有个生成树, 这个题还真的是不好想; 因为本题是n支队伍都会参与, 并且一共要进行n-1场比赛, 那就是n个点和n-1条边, 其中没有重边和自环, 那就是一棵树; 根据队伍编号我们可以知道所有队伍之间比赛的分数, 也就是任意两个点之间的权值; 经过这样"翻译"一下, 就变成了给定所有两个点之间的权值, 然后找一条最大生成树即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e7 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int d[N], p[N];
struct str {
int a, b, c;
}cre[N];
bool cmp(str a, str b) {
return a.c > b.c;
}
int find(int a) {
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
void check() {
for (int i = 0; i < idx; i++) {
int a = cre[i].a, b = cre[i].b, c = cre[i].c;
if (find(a) != find(b)) {
p[find(b)] = find(a);
res += c;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i];
p[i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int a = d[i], b = d[j];
int c = (a ^ b);
cre[idx++] = { i,j,c };
}
}
sort(cre, cre + idx, cmp);
check();
cout << res;
return 0;
}
G.采购特价商品
解题思路
本题算是个模板题, 只是需要根据坐标把两个店之间的距离求出来, 然后用最短路求出s到t之间的最短路即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, m, k,idx;
double d[N], w[N];
int h[N], ne[N], e[N];
bool st[N];
map<int, PII> mp;
void add(int a, int b, double c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void check(int u) {
for (int i = 1; i <= n; i++) d[i] = 1e9;
priority_queue<PII,vector<PII>,greater<PII>> q;
q.push({ 0,u });
d[u] = 0;
while (q.size()) {
auto t = q.top();
q.pop();
int a = t.second;
if (st[a]) continue;
st[a] = true;
for (int i = h[a]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[a] + w[i]) {
d[j] = d[a] + w[i];
q.push({ d[j],j });
}
}
}
}
signed main() {
cin >> n;
memset(h, -1, sizeof h);
int a, b;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
mp[i] = { a,b };
}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
int x = mp[a].first - mp[b].first;
int y = mp[a].second - mp[b].second;
double c = x * x + y * y;
c = sqrt(c);
add(a, b, c), add(b, a, c);
}
cin >> a >> b;
check(a);
printf("%.2lf", d[b]);
return 0;
}
H.逐个击破
解题思路
根据题意我没学需要去删合适的道路, 但是这样似乎难以下手, 因为我们需要在局部操作去追求整体的最大值, 但是这样的做法一般都是贪心, 但是本题很显然没法用贪心, 所有每次操作都得前瞻后顾, 非常的难受; 所以我们不如改变思路, 我们把这道题看出给定m条道路方案, 问该如何修建道路可以让所有敌军隔离开来, 并且花的钱要尽可能多; 因为题目指明有n-1条边, 说明没有重边或者成环这样的复杂情况, 也是就说我们要在隔离敌军的前提下, 把尽可能多的友军连起来; 所有, 又是一个最大生成树的题, 并且本题和kruskal算法的适配性很好; 因为隔离敌军的本质就是把树分成多个连通块, 且每个连通块里面最多只有一个敌军; 所有在kruskal算法中, 如果这条边的两个顶点所在连通块里都已经有敌军了, 那么这条边就不用连接了; 如果两个连通块中至少有一个没有敌军, 那么就可以连接, 如果其中一个里面有敌军, 那么我们为了更快地辨认连通块里是否有敌军, 我们可以把新形成的连通块的祖宗节点就设为该敌军的节点编号; 为此, 我们在输入敌军编号时可以对其编号进行一下标记方便后期辨认; 最后得到这个特殊的最大生成树的权值和, 然后全部的费用减去权值和即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, k, idx, res;
int p[N];
map<int, int> mp;
struct str {
int a, b, c;
}cre[N];
bool cmp(str a, str b) {
return a.c > b.c;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void check() {
for (int i = 1; i < n; i++) {
int a = cre[i].a, b = cre[i].b, c = cre[i].c;
int x = find(a), y = find(b);
if (mp[x] && mp[y]) continue;
if (x != y) {
if (mp[x]) p[y] = x;
else if (mp[y]) p[x] = y;
else p[x] = y;
res += c;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= m; i++) {
int a;
cin >> a;
mp[a]++;
}
for (int i = 1; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
cre[i] = { a,b,c };
idx += c;
}
sort(cre + 1, cre + n, cmp);
check();
cout << idx-res;
return 0;
}
I.消息扩散
解题思路
本题是一个强连通分量的模板题, 但是, 我没学...无奈之下只好去恶补了一下; 既然是模板题, 那我就不多说了; 想学的自动跳转吧;
神秘代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, idx, times, top, cnt;
int stk[N], id[N], sizes[N], dfn[N], low[N];
int cd[N], rd[N];
int h[N], ne[N], e[N];
bool in_stk[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++times;
stk[++top] = u, in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) {
low[u] = min(low[u], dfn[j]);
}
}
if (dfn[u] == low[u]) {
cnt++;
int y;
do {
y = stk[top--];
in_stk[y] = false;
id[y] = cnt;
sizes[cnt]++;
} while (y != u);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j != -1; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
if (a != b) {
cd[a]++, rd[b]++;
}
}
}
int res = 0;
for (int i = 1; i <= cnt; i++) {
if (!rd[i]) res++;
}
cout << res;
return 0;
}