当前位置: 首页 > news >正文

2022 ICPC Hangzhou G and 2022 ICPC Jinan

2022 ICPC Hangzhou G and 2022 ICPC Jinan

ICPC Hangzhou

G

手玩可以发现合法的图中最多只有一个环。所以对于 \(m = n - 1\) 的情况直接判合法;对于 \(m > n\) 的情况直接判非法,此时图中肯定不知有一个环;需要考虑 \(m = n\) 即图是基环树的情况。

当图是基环树时,得到该图的一个生成树也就是断开一条环上的边,也就是说断开的每条边都要是等价的,这就要求这个图有对称性。假设以环上的第 \(i\) 个点为根的子树是 \(t_i\)\(t_i = t_j\) 表示两颗子树同构,则任意 \(t_i = t_j\) 时,基环树上的任意一颗子树都同构,是可以的。还有一种情况是两种形态的树在基环树上交替出现,此时一定是偶环。

判断同构用树哈希:

using i64 = long long;
using u64 = unsigned long long;
// using i128 = __int128_t;
// using point = std::array<i128, 2>;constexpr i64 Mod = 998244353;
constexpr int N = 1e5, P = 10;
const u64 Mask = std::mt19937_64(time(nullptr))();;std::vector<int> adj[N + 5];
int deg[N + 5];
bool cir[N + 5];
u64 val[N + 5];void init(int n) {for (int i = 1; i <= n; ++i) {adj[i].clear();deg[i] = 0;cir[i] = false;}
}// 树哈希
u64 shift(u64 x) {x ^= Mask;x ^= x << 13;x ^= x >> 7;x ^= x << 17;x ^= Mask;return x;
}
u64 dfs(int cur, int lst) {val[cur] = 1ull;for (auto &to : adj[cur]) {if (to != lst && !cir[to]) {val[cur] += shift(dfs(to, cur));}}return val[cur];
}bool solve() {int n = 0, m = 0;std::cin >> n >> m;init(n);for (int i = 0; i < m; ++i) {int u = 0, v = 0;std::cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);deg[u] += 1;deg[v] += 1;}if (m == n - 1) {return true;}if (m > n) {return false;}// 找环std::queue<int> q;for (int i = 1; i <= n; ++i) {if (deg[i] == 1) {q.push(i);}}while (not q.empty()) {auto cur = q.front();q.pop();for (auto &to : adj[cur]) {if (deg[to] == 0) {continue;}deg[cur] -= 1;deg[to] -= 1;if (deg[to] == 1) {q.push(to);}}}for (int i = 1; i <= n; ++i) {if (deg[i] >= 2) {cir[i] = true;}}std::vector<int> node;for (int i = 1; i <= n; ++i) {if (!cir[i]) {continue;}int cur = i, lst = 0;do{node.push_back(cur);for (auto &to : adj[cur]) {if (cir[to] && to != lst) {lst = cur;cur = to;break;}}} while (cur != i);break;}// 奇环if (node.size() % 2) {auto p = dfs(node[0], 0);for (int i = 1; i < node.size(); ++i) {if (dfs(node[i], 0) != p) {return false;}}}// 偶环else {std::array<u64, 2> p = { dfs(node[0], 0), dfs(node[1], 0) };for (int i = 2; i < node.size(); ++i) {if (dfs(node[i], 0) != p[i & 1]) {return false;}}}return true;
}

ICPC Jinan

A

先用操作 3 一定是不劣的,用完操作 3 后,问题就变成了将一个序列里的数通过加减调整成全部一样,同时你可以删掉 \(m\) 个数,当知道要变成什么数时,也就知道了该删掉那 \(m\) 个数,即操作次数最多的那些数。

可能的目标值是不多的,大约只有 \(N\times log_2(10^9)\)(即每个数一直除 2 直到 1 为止),于是我们就可以先预处理出序列里的数到所有可能值得操作数,再枚举最后可能的值,优先队列选出操作数少的 \(n - m\) 个就好了

constexpr int N = 500, L = 40;int n, m;
int a[N + 5];
std::vector<int> s;i64 d[N + 5][N * L];i64 cnt(int j) {i64 ret = 0;std::priority_queue<i64> q;for (int i = 1; i <= n; ++i) {if (q.size() < m) {q.push(d[i][j]);ret += d[i][j];}else if (q.top() > d[i][j]) {ret -= q.top();q.pop();q.push(d[i][j]);ret += d[i][j];} }return ret;
}bool solve() {std::cin >> n >> m;s.clear();m = n - m;for (int i = 1; i <= n; ++i) {std::cin >> a[i];int cur = a[i];while (cur != 0) {s.push_back(cur);cur /= 2;}}// 预处理操作数std::sort(s.begin(), s.end(), std::greater<int>());s.erase(std::unique(s.begin(), s.end()), s.end());for (int i = 1; i <= n; ++i) {int cnt = 0;for (int j = 0; j < s.size(); ++j) {while (a[i] / 2 > s[j]) {a[i] /= 2;cnt += 1;}d[i][j] = cnt + std::abs(a[i] - s[j]);if (a[i] > 1) {d[i][j] = std::min(d[i][j], 1ll * (cnt + 1 + s[j] - a[i] / 2));}}}i64 ans = Inf;for (int i = 0; i < s.size(); ++i) {ans = std::min(ans, cnt(i));}std::cout << ans << '\n';return true;
}
http://www.hskmm.com/?act=detail&tid=35355

相关文章:

  • C++在类定义内的函数包含static代表什么含义呢?
  • 2025/10/20~2025/?/? 做题笔记 - sb
  • 10-20 Extra-Problem 总结
  • ansible底层文件传输机制中默认模式遇到权限拒绝后启用管道模式可以得到解决
  • 10月20日记
  • Rust 编译加速的最佳实践
  • 20232304 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • 笔记本 光驱 的内部结构及用法: 应急强大的系统启动 (恢复) 光盘 (DVD+R/RW)
  • Android 源码解析系列1- Android init 进程启动流程
  • 分层图
  • 10.20总结
  • 学习相关
  • 题解:Luogu P10644 [NordicOI 2022] 能源网格 Power Grid
  • 题解:Luogu P10004 [集训队互测 2023] Permutation Counting 2
  • 题解:Luogu P2075 区间 LIS
  • 英语_阅读_2050 Space tourism_待读
  • goframe框架命令行工具gf在zsh下不能用
  • 题解:Luogu P4143 采集矿石
  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司