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

2023 ICPC ECfinal J

J. Travel 2

思维,模拟搜索。

如果从 \(u\) 选一条边到 \(v\),然后再从 \(v\) 又刚好选到一条边回来 \(u\),那么 \(u-v\) 这条边我们已经知道它分别在 \(u\)\(v\) 里的排名了,一共有 \(m\) 条边,显然 \(2m\) 次可以拿来确定有哪些边。

一开始什么都不知道,考虑从 \(1\) 的第 \(1\) 条边一直出发,以此到 \(v_1,v_2,...\) 的第一条边去找,假如某次询问后又回到了上一个点,那么就从上一个点的第二条边出发,以此往复。

假如某次询问后回到 \(u\) 这个点,而这个点已经已经确定了所有的边,那么可以把这个点标记,接下来去从它所连向的点中找没有确定完所有边的点 \(v\) 去进行上面的搜索过程,确定完 \(v\) 的所有边后再从 \(v\) 回溯到 \(u\),再去找下一个点。

手动模拟一下可以发现的是,除去那 \(2m\) 条确定边的过程中,已经确定完所有边的 \(u\) 去找未确定完所有边的 \(v\) 的过程,就是以 \(u\)\(v\) 的父节点的图中的一颗生成树的树边,而这样的查询过程,向下只会找 \(n-1\) 次,向上回溯需要 \(n-1\) 次,总次数 \(2m+2(n-1)\) 次。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {const int N = 2500;std::vector<int> d(N);auto move = [&](int i)->int{std::cout << "> " << i << std::endl;int x;std::cin >> x >> d[--x];return x;};int x, n = 0;std::cin >> x >> d[--x];std::vector<char> vis(N);std::vector<std::vector<int>> adj(N);auto dfs = [&](auto &&self, int u)->void{n = std::max(n, u);if(adj[u].size() < d[u]) {int v = move(adj[u].size() + 1);adj[u].push_back(v);self(self, v);} else{vis[u] = 1;for(int i = 0; i < adj[u].size(); i += 1) {int v = adj[u][i];if(vis[v]) continue;move(i + 1);self(self, v);for(int j = 0; j < adj[v].size(); j += 1) {if(adj[v][j] == u) {move(j + 1);break;}}}}};dfs(dfs, 0);std::cout << "! ";for(int i = 0; i < n; i += 1) {for(auto &v : adj[i]) {if(i > v) {continue;}std::cout << i + 1 << " " << v + 1 << " ";}}std::cout << std::endl;std::string s;std::cin >> s;}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=29622

相关文章:

  • 嵌入式十六进制的地址转换成十进制MB单位
  • 20232318 2025-2026-1 《网络与系统攻防技术》 实验一实验报告
  • 实时Galgame - 动漫角色 语言生成+图片生成
  • 系统响应慢分析案例
  • Linux文件系统与磁盘工作原理
  • 平安好车主小程序 充电站、加油站列表vmp+wasm逆向
  • Linux文件系统的实验
  • 软中断softirq的CPU使用率升高
  • CPU多进程切换导致过载-CPU上下文切换
  • Vue3 之pinia状态管理
  • 乐理 -01识谱
  • shader func
  • 案例分析-DDOS攻击、网络延迟(延迟确认纳格算法)、NAT延迟
  • 服务器丢包分析-iptables规则-MTU大小设置错误-perf-火焰图分析处理请求时内核线程调用
  • luogu P4513 小白逛公园
  • 2025 年碟式离心机厂家 TOP 企业品牌推荐排行榜,DB640 系列 / DB330 系列 / DB440 系列 / DB460 系列 / DB550 系列 / 专业碟式离心机推荐这十家公司!
  • 20231408徐钰涵课程思维导图Openssl实践
  • 案例分析-DNS+tcpdump+wireshark
  • 2025 年卧式离心机厂家 TOP 企业品牌推荐排行榜,LW250/LW350/LW450/LW530/LW540 / 专业卧式离心机推荐这十家公司!
  • 2025 年水泥管厂家最新推荐排行榜,国标水泥管,二级水泥管,钢筋混凝土水泥管,大口径水泥管,平口水泥管公司推荐!
  • Day1 经典Holle word
  • 内存知识总结
  • 2025 年金属复合板厂家推荐广东粤洋建材科技有限公司,实力产能与定制服务全景解析金属复合板公司推荐
  • 2025 年铝蜂窝板厂家最新推荐排行榜,铝蜂窝板,铝蜂窝吊顶,铝蜂窝墙面板,微孔吸音板,防火A级铝复合板公司推荐
  • 读书笔记:关于Oracle里的“老古董”:LONG类型
  • 致技术社区的英雄们:一场关于文明未来的建造邀请
  • AI图片生成思路
  • SCP/NOIP 复习:插板法
  • 内存泄漏与SWAP
  • 今天开通自己的博客啦,加油加油!成为合格的牛马! - Irving11