trudbot

$\href{http://trudbot.cn/}{{点击进入我的个人网站}}$

7.1万

acbaby

Llh
lianxuhanshu
huangbq
xk159753

R虎虎生威R

marvel111
Isaacs
acwing_4813

trudbot
22天前

i顶点每次被染色， 其第a、2a、3a…个祖先都被会染色。

### 时间复杂度

$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
vector<int> g[N];
int cnta[N], cntb[N];

void dfs(int u, int v, int cnt[], vector<int> &path) {
path.push_back(u);
for (auto &s : g[u]) dfs(s, v, cnt, path);
cnt[u] ++, path.pop_back();
if (path.size() >= v) cnt[path[path.size() - v]] += cnt[u];
}

int main () {
int T; cin >> T;
for (int t = 1; t <= T; t ++) {
int n, a, b; cin >> n >> a >> b;
for (int i = 1; i <= n; i ++) {
g[i].resize(0), cnta[i] = 0, cntb[i] = 0;
}
for (int i = 2, fa; i <= n; i ++) {
cin >> fa, g[fa].push_back(i);
}
vector<int> path;
dfs(1, a, cnta, path), dfs(1, b, cntb, path);
double res = 0;
for (int i = 1; i <= n; i ++) {
double pa = 1.0 * cnta[i] / n, pb = 1.0 * cntb[i] / n;
res += pa + pb - pa * pb;
}
printf("Case #%d: %.6lf\n", t, res);
}
return 0;
}



trudbot
1个月前

## 试题H: 整数删除

### 参考代码

ACWing数据够强， 为了运行时间好看加了些优化

#pragma GCC target ("avx")
#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
__attribute__((unused)) int io_ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
return 0;
}();
const int N = 5e5 + 10;
ll v[N], l[N], r[N];

void del(int x) {
r[l[x]] = r[x], l[r[x]] = l[x];
v[l[x]] += v[x], v[r[x]] += v[x];
}

int main () {
int n, k; cin >> n >> k;
r[0] = 1, l[n + 1] = n;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;
for (int i = 1; i <= n; i ++)
cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});
while (k --) {
auto p = h.top(); h.pop();
if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;
else del(p.second);
}
while (head != n + 1) {
}
return 0;
}


trudbot
1个月前

## 试题I: 景区导游

### 参考代码

//
// Created by trudbot on 2023/4/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
using ll = long long;
vector<pair<int, int>> g[N];
ll dep[N], f[N][30], dist[N];

void dfs(int u, int fa, ll d) {
dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa;
for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
for (auto &p : g[u]) {
if (p.first == fa) continue;
dfs(p.first, u, d + p.second);
}
}

int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = 20; i >= 0; i --) {
if (dep[f[a][i]] >= dep[b]) a = f[a][i];
if (a == b) return a;
}
for (int i = 20; i >= 0; i --) {
if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
}
return f[a][0];
}

ll get(int a, int b) {
return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

int main () {
int n, k; cin >> n >> k;
for (int i = 1; i < n; i ++) {
int u, v, t; cin >> u >> v >> t;
g[u].push_back({v, t}), g[v].push_back({u, t});
}
vector<int> a(k);
for (auto &x : a) cin >> x;
dfs(1, 0, 0);
ll sum = 0;
for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]);
for (int i = 0; i < k; i ++) {
ll ans = sum;
if (i != 0) ans -= get(a[i], a[i - 1]);
if (i != k - 1) ans -= get(a[i], a[i + 1]);
if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]);
cout << ans << " ";
}
return 0;
}


trudbot
1个月前

## 试题J: 砍树

### 参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 18;
vector<pair<int, int>> g[N];
int dep[N], f[N][20], cnt[N], w[N];

//倍增初始化
void init(int u, int fa) {
dep[u] = dep[fa] + 1, f[u][0] = fa;
for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
for (auto &e : g[u]) {
if (e.first != fa) init(e.first, u), w[e.first] = e.second;
}
}

//求LCA
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = M; i >= 0; i --) {
if (dep[f[a][i]] >= dep[b]) a = f[a][i];
if (a == b) return a;
}
for (int i = M; i >= 0; i --) {
if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
}
return f[a][0];
}

//差分， 增加记录
void add(int a, int b) {
int LCA = lca(a, b);
cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2;
}

//求和
void dfs(int u, int fa) {
for (auto &e : g[u]) {
if (e.first != fa)
dfs(e.first, u), cnt[u] += cnt[e.first];
}
}

int main () {
int n, m; cin >> n >> m;
for (int i = 1; i < n; i ++) {
int a, b; cin >> a >> b;
g[a].push_back({b, i}), g[b].push_back({a, i});
}
init(1, 0);
for (int i = 0; i < m; i ++) {
int a, b; cin >> a >> b;
}
dfs(1, 0);
//取满足条件的最大编号
int res = -1;
for (int i = 1; i <= n; i ++)
if (cnt[i] == m && (w[i] > res)) res = w[i];
cout << res << endl;
return 0;
}


trudbot
1个月前

stable_sort妙用

#include <bits/stdc++.h>
using namespace std;
#define w(c) c - (c <= 'z' && c >= 'a' ? 'a' : 'A')

int main () {
string s;
while (getline(cin, s)) {
vector<int> pos;
string a;
for (int i = 0; i < s.size(); i ++)
if (isalpha(s[i])) pos.push_back(i), a.push_back(s[i]);
stable_sort(a.begin(), a.end(), [](auto &x, auto &y){return w(x) < w(y);});
for (int i = 0; i < pos.size(); i ++) s[pos[i]] = a[i];
cout << s << endl;
}
return 0;
}


trudbot
1个月前

#include <bits/stdc++.h>
using namespace std;

int main () {
int n; cin >> n;
vector<pair<int, string>> a(n);
for (auto &[w, c] : a) cin >> w >> c;
sort(a.begin(), a.end(), greater<>());
for (auto &[_, c] : a) cout << c << endl;
return 0;
}


trudbot
1个月前
#include <bits/stdc++.h>
using namespace std;

int main () {
int T; cin >> T;
while (T --) {
int n, res = 0; cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
for (int k = 0; k < n; k ++)
if (a[i] + a[j] == a[k]) res ++;
cout << res << endl;
}
return 0;
}


trudbot
1个月前
#include <bits/stdc++.h>
using namespace std;

void print(map<int, int> &cnt, set<int> &s) {
cout << "{";
int idx = 1;
for (auto &x : s) {
cout << x << "=" << cnt[x];
if (idx++ != s.size()) cout << ",";
}
cout << "}\n";
}

int main () {
int T; cin >> T;
while (T --) {
int n; cin >> n;
vector<map<int, int>> cnt(101);
vector<int> a(n);
set<int> v;
for (auto &x : a) cin >> x, v.insert(x);
for (int i = 0; i < n; i ++) {
int m; cin >> m;
cnt[m][a[i]] ++;
}
for (int i = 1; cnt[i].size(); i ++) {
cout << i << "=", print(cnt[i], v);
}
}
return 0;
}


trudbot
1个月前

#include <bits/stdc++.h>
using namespace std;

void print(map<int, int> &cnt, set<int> &s) {
cout << "{";
int idx = 1;
for (auto &x : s) {
cout << x << "=" << cnt[x];
if (idx++ != s.size()) cout << ",";
}
cout << "}\n";
}

int main () {
int T; cin >> T;
while (T --) {
int n; cin >> n;
vector<map<int, int>> cnt(101);
vector<int> a(n);
set<int> v;
for (auto &x : a) cin >> x, v.insert(x);
for (int i = 0; i < n; i ++) {
int m; cin >> m;
cnt[m][a[i]] ++;
}
for (int i = 1; cnt[i].size(); i ++) {
cout << i << "=", print(cnt[i], v);
}
}
return 0;
}


trudbot
1个月前

## 模拟

#include <bits/stdc++.h>
using namespace std;

int main () {
string s;
while (cin >> s) {
int res = 0;
for (int i = s.size() - 1, j = 2; i >= 0; i --, j *= 2) {
res += (s[i] - '0') * (j - 1);
}
cout << res << endl;
}
return 0;
}