思维(交互题),CF 1990E2 - Catch the Mole(Hard Version)

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

E2 - Catch the Mole(Hard Version)


二、解题报告

1、思路分析

考虑每次误判都会让鼹鼠上升一层,相应的,最外层的一层结点都没用了

由于数据范围为5000,我们随便找个叶子结点询问71次,那么会剩下不超过70条路径

为什么呢?

剩下的路径一定满足长度大于71,路径数乘长度 <= 5000,故不超过70条

我们考虑在70条中找到鼹鼠所在的那一条然后在路上二分

我们还剩90次机会,路上二分最多十几次,我们如何70次内找到路径?

考虑直接深搜

由于剩余不超过70条路径,所以我们实际最多也就走70个分叉(再多路径就大于70条了)

然后有个注意的点,如果当前儿子结点为最后一个结点,我们直接进去深搜,这既正确的同时也是为了防止被单链样例卡掉

2、复杂度

时间复杂度: O(N + M + NlogN)空间复杂度:O(N + M)

3、代码详解

 ​
#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
using PII = std::pair<int, int>;
constexpr int inf32 = 1e9 + 7;
constexpr i64 inf64 = 1e18 + 7;// #define DEBUGint query(int x)
{std::cout << "? " << x + 1 << std::endl;int res;std::cin >> res;return res;
}constexpr int B = 71;void solve()
{int n;std::cin >> n;std::vector<std::vector<int>> adj(n);for (int i = 1, u, v; i < n; ++i){std::cin >> u >> v;--u, --v;adj[u].push_back(v);adj[v].push_back(u);}std::vector<int> h(n), fa(n, -1);auto dfs = [&](auto &&self, int u) -> void{for (int v : adj[u]){if (v == fa[u])continue;fa[v] = u;self(self, v);h[u] = std::max(h[u], h[v] + 1);}};dfs(dfs, 0);int leaf = std::find(h.begin(), h.end(), 0) - h.begin();for (int i = 0; i < B; ++i){if (query(leaf) == 1){std::cout << "! " << leaf + 1 << std::endl;return;}}auto find = [&](auto &&self, int u) -> int{std::vector<int> a;for (int v : adj[u]){if (v == fa[u] || h[v] < B)continue;a.push_back(v);}if (!a.size())return u;for (int v : a){if (v == a.back() || query(v) == 1)return self(self, v);}assert(false);return -1;};int v = find(find, 0);std::vector<int> a;for (; ~v; v = fa[v])a.push_back(v);std::reverse(a.begin(), a.end());int lo = 0, hi = a.size() - 1;while (lo < hi){int x = (lo + hi + 1) / 2;if (query(a[x]) == 1)lo = x;else{hi = x - 1;lo = std::max(0, lo - 1);hi = std::max(0, hi - 1);}}std::cout << "! " << a[lo] + 1 << std::endl;
}int main()
{
#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ = 1;std::cin >> _;while (_--)solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1487905.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

OSPF概述

OSPF OSPF属于内部网关路由协议【IGP】 用于单一自治系统【Autonomous System-AS】内决策路由 自治系统【AS】 执行统一路由策略的一组网络设备的组合 OSPF概述 为了适应大型的网络&#xff0c;OSPF在AS内划分多个区域 每个OSPF路由器只维护所在区域的完整的链路状态信息 …

微服务实战系列之玩转Docker(五)

前言 在我们日常的工作生活中&#xff0c;经常听到的一句话&#xff1a;“是骡子是马拉出来遛遛”。目的是看一个人/物是不是名副其实。我们在使用docker时&#xff0c;也要看看它究竟是如何RUN起来的。当面试官问你的时候&#xff0c;可以如是回答&#xff0c;保你“一文通关…

prometheus tsdb索引布局及查询流程

prometheus 磁盘布局 采集到的数据每两个小时形成一个block。每个block由一个目录组成&#xff0c;并存放在data路径下。该目录包含一个包含该时间窗口的所有时间序列样本的块子目录、一个元数据文件和一个索引文件&#xff08;将metric_name和label索引到目录下的时间序列&am…

导航不是GPS吗,有人用北斗吗?

在现代生活中&#xff0c;提到导航&#xff0c;人们脑海中最先浮现的往往是GPS。然而&#xff0c;近年来&#xff0c;中国自主研发的北斗导航系统&#xff08;BeiDou Navigation Satellite System, BDS&#xff09;正在迅速崛起&#xff0c;逐步占据全球导航市场的一席之地&…

SQL-REGEX-常见正则表达式的使用

SQL-REGEX-常见正则表达式的使用 在SQL中&#xff0c;正则表达式&#xff08;Regex&#xff09;的使用可以帮助进行更灵活和精确的模式匹配和数据筛选。不同的数据库管理系统对于正则表达式的支持略有差异&#xff0c;但大体都是相似的。 Tips&#xff1a; 模式描述匹配内容…

洗地机哪个牌子好?推荐四款口碑最好的洗地机

在追求高效、便捷的现代居家环境中&#xff0c;洗地机已然跃升为家庭清洁的新风尚。面对市场上琳琅满目的洗地机产品&#xff0c;洗地机哪个牌子好&#xff1f;如何筛选出那些既拥有卓越清洁能力&#xff0c;又兼备智能化操作及高用户满意度的佼佼者&#xff0c;成为了消费者关…

计算机视觉与图像分类:技术原理、应用与发展前景

引言 随着科技的不断进步&#xff0c;计算机视觉逐渐成为了人工智能领域的重要分支之一。计算机视觉旨在让计算机具备“看懂”图像和视频的能力&#xff0c;从而理解和分析视觉信息。作为计算机视觉中的一个关键任务&#xff0c;图像分类涉及将输入的图像归类到预定义的类别中&…

基于Delaunay三角网的边缘检测

1、背景介绍 Delaunay三角网是一种在平面上对一组点构造三角网格的方法&#xff0c;其中任何点都不在由其周围点形成的任何三角形的外接圆内部。这种方法确保了三角形尽可能接近等边三角形&#xff0c;从而避免了狭长的三角形。如下图所示&#xff0c;为利用平面上点集构建生成…

Pytorch使用教学2-Tensor的维度

在PyTorch使用的过程中&#xff0c;维度转换一定少不了。而PyTorch中有多种维度形变的方法&#xff0c;我们该在什么场景下使用什么方法呢&#xff1f; 本小节我们使用的张量如下&#xff1a; # 一维向量 t1 torch.tensor((1, 2)) # 二维向量 t2 torch.tensor([[1, 2, 3], …

【数据结构--查找】

目录 一、查找&#xff08;Searching&#xff09;的概念1.1、基本概念1.2、算法的评价指标 二、顺序查找2.1、算法思想2.2、算法实现2.2.1、常规顺序查找2.2.2、带哨兵的顺序查找 2.3、效率分析2.4、优化2.4.1、针对有序表2.4.2、被查效率不相等 三、折半查找3.1、算法思想3.2、…

mysql面试(四)

前言 本章节有些长&#xff0c;主要的篇幅是介绍缓存页的算法&#xff0c;如何快速的定位哪些是没有用过的&#xff0c;哪些是用过的&#xff0c;哪些是要淘汰掉的。 建议可以阅读一下这里面LRU算法相关的内容&#xff0c;和很多组件里面基本原理都是想通的&#xff0c;比如re…

总结20个Python接单赚钱的平台,兼职月入6000+_让你早日实现财富自由

今天就给大家盘点几个基本入门接私活的资源&#xff0c;让你轻松学python&#xff0c;实现经济独立。 一、Python兼职种类&#xff1a; 接私活刚学会python那会&#xff0c;就有认识的朋友介绍做一个网站的私活&#xff0c;当时接单赚了4K&#xff0c;后又自己接过开发网站后…

Delphi5实现随机数生成并查找最大值

效果图 输入框不可修改 设置edit控件的readonly属性为true。 生成随机数 Randomize 函数通过获取系统时钟的当前时间&#xff08;或其他系统特定的随机源&#xff09;来自动设置随机数生成器的种子。这样&#xff0c;每次程序运行时&#xff0c;由于系统时间的不同&#xff…

NLP之词的向量化

文章目录 前言One-hot编码one-hot编码-缺点 word2vec-词向量基于语言模型的训练方式基于窗口——CBOW基于窗口——SkipGram 前言 向量对于机器学习非常重要,大量的算法都需要基于向量来完成。对于机器来说&#xff0c;字符是没有含义的&#xff0c;只是有区别。只使用字符无法去…

爬虫开发中AttributeError的快速解决方法

在网络爬虫开发过程中&#xff0c;AttributeError是一个常见且令人头疼的问题。这个错误通常是由于尝试访问一个对象中不存在的属性而引发的。本文将概述如何快速定位和解决AttributeError&#xff0c;并提供使用爬虫代理IP和多线程技术提高爬取效率的示例代码。 概述 Attrib…

mysql 数据库空间统计sql

mysql 数据库空间统计 文章目录 mysql 数据库空间统计说明一、数据库存储代码二、查询某个数据库的所有表的 代码总结 说明 INFORMATION_SCHEMA Table Reference 表参考 information_schema是‌MySQL中的一个特殊数据库&#xff0c;它存储了关于所有其他数据库的元数据信息。…

物理机 gogs+jenkins+sonarqube 实现CI/CD

一、部署gogs_0.11.91_linux_amd64.tar.gz gogs官网下载&#xff1a;https://dl.gogs.io/ yum -y install mariadb-serversystemctl start mariadbsystemctl enable mariadbuseradd gittar zxvf gogs_0.11.91_linux_amd64.tar.gzcd gogsmysql -u root -p < scripts/mysql.…

xLua | xLua Framework | 2 加载

0. 基础 0.1 不同加载模式 测试用 编辑器模式&#xff1b;打包模式&#xff1b;更新模式 public enum GameMode {EditorMode,PackageBundle,UpdateMode, } 0.2 加载资源步骤与接口 private void LoadAsset(string assetName, Action<Object> action) {if (AppConst.G…

c++ 求解质因数(细节详解)

定义 这里先来了解几个定义&#xff08;如已了解&#xff0c;可直接看下一个板块&#xff09; 因数&#xff1a;又称为约数&#xff0c;如果整数a除以整数b&#xff08;b0&#xff09;的商正好是是整数而没有余数&#xff0c;我们就说b是a的因数 质数&#xff1a;又称为素数…

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十章 Linux设备树

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…