社区讨论
没有用可并堆,直接自底向上贪心 AC 了,为什么?
P10283 [USACO24OPEN] Identity Theft P参与者 48已保存回复 58
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 57 条
- 当前快照
- 1 份
- 快照标识符
- @luajs7qh
- 此快照首次捕获于
- 2024/03/28 09:20 2 年前
- 此快照最后确认于
- 2024/08/05 07:55 2 年前
如题。就是先把子树贪完,过程中维护一个
f 数组表示从这个结点降下一个新的棋子,最少要几步可以调整使条件满足。随时动态维护 f。移动的时候,贪心朝 f 较小的一侧移动。时间复杂度可以证明是一个 log,因为每个棋子最多移动 log 步。但是为什么贪心得到的答案是对的?
CPP#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <functional>
#include <algorithm>
using std::cin, std::cout;
using std::min;
void Solve();
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
Solve();
return 0;
}
void Solve() {
int N;
cin >> N;
std::vector<std::array<int, 2>> child(2);
std::vector<int> chips(2);
int root = 1;
for (int i = 1; i <= N; ++i) {
std::string s;
cin >> s;
int now = root;
for (char c : s) {
int j = c - '0';
if (!child[now][j]) {
child[now][j] = (int)child.size();
child.push_back({0, 0});
chips.push_back(0);
}
now = child[now][j];
}
++chips[now];
}
std::vector<int> f(child.size());
int ans = 0;
auto Update = [&](int u) {
if (!child[u][0] && !child[u][1])
f[u] = 0;
else
f[u] = min(f[child[u][0]], f[child[u][1]]) + 1;
};
std::function<void(int)> Propagate = [&](int u) {
--chips[u];
if (f[u] == 0) {
f[u] = 2;
return ;
}
if (!child[u][0] && !child[u][1]) {
child[u][0] = (int)child.size();
child.push_back({0, 0});
chips.push_back(0);
f.push_back(0);
child[u][1] = (int)child.size();
child.push_back({0, 0});
chips.push_back(0);
f.push_back(0);
++chips[child[u][0]], ++ans;
++chips[child[u][1]], ++ans;
Propagate(child[u][0]);
Propagate(child[u][1]);
Update(u);
return ;
}
int dir = f[child[u][0]] > f[child[u][1]];
if (!child[u][dir]) {
child[u][dir] = (int)child.size();
child.push_back({0, 0});
chips.push_back(0);
f.push_back(0);
}
++chips[child[u][dir]], ++ans;
Propagate(child[u][dir]);
Update(u);
};
std::function<void(int)> DFS = [&](int u) {
if (!u)
return ;
DFS(child[u][0]);
DFS(child[u][1]);
Update(u);
while (chips[u])
Propagate(u);
};
DFS(root);
cout << ans << '\n';
}
回复
共 58 条回复,欢迎继续交流。
正在加载回复...