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

Codeforces 2155D Batteries 题解 [ 绿 ] [ 图论 ] [ Ad-hoc ]

Batteries:很有趣的一个 Ad-hoc,之前见到过一个类似的构造。如果对上脑电波应该很快能秒掉。

看到这种比较奇怪的交互次数限制,可以想到拆限制的式子\(\lfloor\dfrac{n^2}{a}\rfloor = \lfloor\dfrac{n}{a}\cdot n\rfloor\)。这提示我们对于每一个电池最多只能操作 \(\bm{\dfrac{n}{a}}\)

然后形式化一下题意,可以转化为一个 \(n\) 点的完全图,图上有 \(a\) 个黑点,一条边是黑边当且仅当 \(u, v\) 都是黑点。你需要在 \(\lfloor\dfrac{n^2}{a}\rfloor\) 次内找出一条黑边。

一眼看上去非常没有头猪,所以可以试试拎出来环、菊花、树、链、二分图之类的特殊图来研究。然后你就能发现,如果从这张图里,随意挑出一个 \(n\) 点的简单环,然后往环上加一些捷径边,就能完成构造。具体而言,令 \(k = 1\),然后按顺序执行下列操作(连边的意思就是对 \(u, v\) 进行一次询问):

  1. 对于所有的 \(1 \le i \le n\),连边 \(i\to(i+k - 1)\bmod n + 1\),直到找到一个黑边。
  2. \(k\gets k + 1\),返回第一步。

说人话就是先搞出一个 \(n\) 个点的有向环,然后每一轮对每个点依次询问走 \(1, 2, 3, 4, \cdots\) 步抵达的点进行询问。

正确性证明是简单的,对于有 \(a\) 个黑点的环,任意两个黑点之间的距离的最小值不会超过 \(\dfrac{n}{a}\),因此每个黑点都跳 \(\bm{\dfrac{n}{a}}\) 步就一定能找到一条黑边,这和我们上文拆的限制是一样的。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
int n, res;
void solve()
{cin >> n;int now = 1;while(1){for(int i = 0; i < n; i++){int v = (i + now) % n;cout << i + 1 << " " << v + 1 << endl;cin >> res;if(res == 1) return;}now++;}
}
int main()
{int t;cin >> t;while(t--) solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=26438

相关文章:

  • Disruptor框架深度解析与实战指南
  • P2824 [HEOI2016/TJOI2016] 排序
  • GCC背后的故事C程序常量变量的地址分配
  • 龙芯是被gcc正儿八经支持的
  • python程序设计课程练习题
  • IEEE754浮点格式与解析
  • 国庆 Day3 强基数学
  • Petrozavodsk Summer 2024. Day 1. Welcome Contest
  • 项目作业2
  • 如何使用 INFINI Gateway 对比 ES 索引数据
  • Ambari安装Hadoop
  • Ambari-bigtop搭建hadoop数据仓库架构
  • 安装Ambari集群
  • Python中的`namedtuple`:命名元组的用法与优势
  • 我的首页
  • 一摞python风格的纸牌
  • 记录一个ubuntu24.04蓝牙不显示不可用的解决方案
  • AI时代需要重新定义投资回报评估模型
  • MOVEit网络攻击波及普华永道与安永,供应链安全再响警钟
  • shell编程
  • Penchick Online Mathematical Olympiad, Qualifying Test 1, III.4
  • QBXT2025S刷题 Day6
  • CF2145 Educational Codeforces Round 183 (Rated for Div. 2) 游记
  • 52个AI工具
  • 可观测专题【左扬精讲】——《Go 语言实现企业级 APM 监控系统实战:从 0 到 1 搭建高性能监控平台》
  • 多区域多 VLAN 网络搭建与访问控制及服务器部署实验
  • Tina_Linux_系统软件 开发指南
  • 2025方钢、扁钢、圆钢、光轴、六角钢、异型钢、冷拉/冷拔方钢、冷拉/冷拔扁钢、冷拉/冷拔圆钢、冷拉/冷拔六角钢、冷拉/冷拔异型钢、热轧方钢/扁钢厂家权威推荐榜:坚固耐用与精准定制口碑之选
  • GO_基础2
  • LDO(一)FVF型LDO