个人赛链接: https://www.luogu.com.cn/contest/120853#description
今天只补了七道, 太难了呜呜呜...
A.二叉树的遍历
解题思路
签到题, 最基础的树的建立与遍历;
神秘代码
#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;
struct str {
int id;
str* left;
str* right;
}tree[N];
void dfs1(str u) {
cout << u.id << ' ';
if (u.left) dfs1(*u.left);
if (u.right) dfs1(*u.right);
}
void dfs2(str u) {
if (u.left) dfs2(*u.left);
cout << u.id << ' ';
if (u.right) dfs2(*u.right);
}
void dfs3(str u) {
if (u.left) dfs3(*u.left);
if (u.right) dfs3(*u.right);
cout << u.id << ' ';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout .tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
tree[i].id = i;
if(a)tree[i].left = &tree[a];
if(b)tree[i].right = &tree[b];
}
dfs1(tree[1]);
cout << endl;
dfs2(tree[1]);
cout << endl;
dfs3(tree[1]);
cout << endl;
return 0;
}
B.Bad Cowtractors S
解题思路
根据题意可以得知是求最大生成树, 只需要把kruskal算法的排序改为从大到小即可;
神秘代码
#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, idx, res;
int 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];
}
bool check() {
for (int i = 1; i <= m; i++) {
int a = cre[i].a, b = cre[i].b, c = cre[i].c;
if (find(a) != find(b)) {
p[find(a)] = find(b);
res += c;
idx++;
}
}
if (idx != n - 1) return false;
else return true;
}
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, b, c;
cin >> a >> b >> c;
cre[i] = { a,b,c };
}
sort(cre + 1, cre + 1 + m,cmp);
if (check()) cout << res;
else cout << -1;
return 0;
}
C.3-1
解题思路
一道非常坑的题, 当我在想怎么遍历的时候却被告知这是一个贪心题; 于是我非常
决然开心地去开始找规律; 于是发现如果想要最短时间去经过尽可能多的装置, 最理想的情况就是一条路走到黑, 但是这样的限制就是树的深度d; 于是我们知道如果装置数量k<=d时, 我们只需要比k-1多走一步即可, 最后传送回起点; 然而当数量超过d时, 我们就必须要有回头这个操作, 设第d+i个装置为a, 如果a不在最深层, 那我们应该先去找a, 然后回来再去最深层, 因为我们要保证最后传送回起点的收益是最高的, 所以当k>d时, 我们就需要比k-1多走两步, 一步过去一步回来;
神秘代码
#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;
int a, b;
int w[N], p[N];
int maxn = 1;
vector<int> v[N];
void dfs(int u, int fa) {
for (int i = 0; i < v[u].size(); i++) {
int j = v[u][i];
if (j == fa) continue;
w[j] = w[u] + 1;
maxn = max(maxn, w[j]);
dfs(j, u);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
w[1] = 1;
dfs(1,1);
int res = 0;
cout << 0 << endl;
for (int i = 2; i <= n; i++) {
if (i <= maxn) {
cout << res + 1 << endl;
res += 1;
}
else {
cout << res + 2 << endl;
res += 2;
}
}
return 0;
}
E.族谱树
解题思路
本题涉及最近公共祖先算法, 因为我还没学于是就去恶补了一下, 并且十分喜欢tarjan算法, 但是本题并不是模板题...因为tarjan是离线的, 而本题输入并不是离线; 然后我从题解中一个很巧妙的方法; 对于dfs,我们可以理解为是从左到右去遍历图, 所以第i层的最近公共祖先一定是在这一层最靠右的点的链上; 所以我们开设一个res数组, d[x]表示x所在的层数, res[d[x]]表示在处理到x之前所有深度为i的点的最近公共祖先; 于是当dfs到x时, 如果res[d[x]] = 0, 所有x是第一个点, 最近公共祖先就是x自己; 如果res[d[x]] = y, 那么就像tarjan从最近公共祖先一样, res[d[x]] = find(y);
因为本题最后一个数据非常极限, 所以把求层数也放进tarjan里面了, 还用上了快读才过的...
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e6 + 10, mod = 1e9 + 7;
int n, m, idx;
int p[N], d[N], res[N], st[N];
int h[N], ne[N], e[N];
inline int read(){
register int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9'){
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
void add(int a, int b) {
ne[idx] = h[a], e[idx] = b, h[a] = idx++;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u, int fa) {
d[u] = d[fa] + 1;
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
tarjan(j,u);
p[j] = u;
}
}
if (!res[d[u]]) res[d[u]] = u;
else res[d[u]] = find(res[d[u]]);
}
signed main() {
n = read(), m = read();
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
int a;
a = read();
add(a, i);
}
tarjan(1,0);
for (int i = 1; i <= m; i++) {
int a;
a = read();
printf("%d\n", res[a]);
}
return 0;
}
G.树的分解
解题思路
对于一个节点, 如果他的一个子树的节点数等于m, 那这个子树就可以作为一个连通块; 如果小于m, 那我们就只能把他归到父节点的连通块上, 如果该节点有多个节点数小于m的子树, 并且把他们和父节点归为一个连通块时, 如果这个连通块的数量超过m了, 则说明操作无解, 因为如果子树本身节点数小于m, 还不如父节点管它, 那么这个子树就被孤立, 也不行; 那如果都归到一起后还是小于m呢, 那么就把当前连通块的节点数作为当前以父节点为根的树的节点数去向上回溯, 作为父父节点的子树再去进行同样的操作; 注意这时你会发现只有当节点数小于m时才会作为子树向上回溯, 所以我们前面就没有讨论子树节点数大于m的情况; 并且由上面的操作我们发现可以先dfs到最底层, 然后由下到上进行操作;
神秘代码
#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;
int a, b;
int w[N], p[N];
bool st[N];
bool f;
vector<int> v[N];
queue<int> le;
bool cmp(int a, int b) {
return w[a] < w[b];
}
void dfs(int u, int fa) {
w[u] = 1;
for (int i = 0; i < v[u].size(); i++) {
int j = v[u][i];
if (j == fa) continue;
dfs(j, u);
if (w[j] == m) b++;
else if (w[j] < m) w[u] += w[j];
}
if (w[u] == m) w[u] -= m, b++;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
memset(w, 0, sizeof w);
memset(p, 0, sizeof p);
memset(st, false, sizeof st);
f = false;
a = 0, b = 0;
cin >> n >> m;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
k = n / m;
dfs(1,0);
if (b == k) cout << "YES" << endl;
else cout << "NO" << endl;
for (int i = 1; i <= n; i++) v[i].clear();
}
return 0;
}
H.聪明的猴子
解题思路
本质还是一个最小生成树, 我们可以把每棵树之间距离算出来所为两个点之间的权值, 因为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, idx, res, num;
int w[N], p[N];
PII pos[N];
struct str {
int a, b, c;
}cre[N];
int find(int a) {
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
bool cmp(str a, str b) {
return a.c < b.c;
}
void check() {
for (int i = 1; i <= num; i++) {
int a = cre[i].a, b = cre[i].b, c = cre[i].c;
if (find(a) != find(b)) {
p[find(b)] = find(a);
idx = max(idx, c);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout .tie(0);
cin >> m;
for (int i = 1; i <= m; i++) {
int a;
cin >> a;
w[i] = a * a;
}
cin >> n;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
pos[i] = { a,b };
}
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
int x = pos[i].first - pos[j].first;
int y = pos[i].second - pos[j].second;
int d = x * x + y * y;
num++;
cre[num] = { i,j,d };
}
}
sort(cre + 1, cre + 1 + num, cmp);
check();
for (int i = 1; i <= m; i++) {
if (w[i] >= idx) res++;
}
cout << res;
return 0;
}
I.生命之树
解题思路
看了标签才知道是一个树形dp的题目, 树形dp的状态表示为: dp[i][1/0] 表示当前i这个结点是选还是不选时, 以i为父节点的子树中的最大价值; 对于本题来说, 如果不选, dp[i][0]就是0, 因为题目是要求一条连续的路径, 如果不选父节点i, 那么要不是一条路径从中间某个地方断开, 要么就会发现当前路径已经不归属于为i为父节点的子树, 而是更下一层; 所以我们发现dp[i][0]是没有意义的, 所以我们可以把状态表示优化为dp[i]; 而如果选了当前节点i, 设他的子节点为j; 因为选了当前节点所以d[i]初始化w[i], 并且只要d[j]这条路径的价值>0, 我们就让d[i]+=d[j], 否则还不如不加; dfs结束后, 我们只需要一遍d[1]~d[n], 找出最大值即可;
注意本题有个坑点, 如果所有点的价值都是负的, 那么我们可以一个点都不选, 价值就为0; 所有结果res应该要初始化为0;
神秘代码
#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;
int w[N], p[N];
int dp[N];
vector<int> v[N];
void dfs(int u,int fa) {
dp[u] = w[u];
for (int i = 0; i < v[u].size(); i++) {
int j = v[u][i];
if (j == fa) continue;
dfs(j,u);
if(dp[j]>=0) dp[u] += dp[j];
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout .tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1,-1);
int res = 0;
for (int i = 1; i <= n; i++) {
res = max(res,dp[i]);
}
cout << res;
return 0;
}