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

题解:CF1483E Vabank

题意:交互题。现在有个隐藏的数 \(M\),你可以询问 \(X\)\(M\) 的大小关系,如果 \(X\le M\) 则你会增加 \(X\) 块钱,如果 \(X>M\) 你需要支付 \(X\) 块钱,如果你付不起就挂了。初始有 \(1\) 块钱,要找出 \(M\) 是多少,最多 \(105\) 次询问。\(M\le 10^{14}\)

做法:

首先我们先不管支付的事情,那么就是直接二分,有付钱这个事情就不是很好做,直接二分的话我们需要补次钱。我们一开始肯定还是直接倍增,这样刚好是在我有钱的前提下尽量扩大范围去找。同时这样可以更快地缩小范围,方便我们去补钱这一部分最多需要用掉 \(47\) 次操作。

然后我们这个时候就可以找出来答案应该在 \([2^x,2^{x+1})\) 这个范围内,这个时候我们再去进行二分。

但是这里有个问题,正常的二分向左向右是没有什么去别的,这里向左是有负的代价而向右是有正的贡献的,并不是同等地位的,所以我们其实应该考虑适当地向左偏移一点,这样去平衡一下两侧的代价。假设我取在整条线段的 \(\frac{1}{p}\) 的位置,那么向左一次,我们就需要补 \([1,2]\) 次钱,\(1\) 次钱居多,最少的步数就是 \(2\log_p(r-l)\) 次,这里 \([l,r)\) 是确定的答案区间。那么因为剩下 \(58\) 次操作,就大概要求 \(\frac 1 p \ge 0.3\) 左右,实则并没有这么严因为这本身就是个比较松的做法。

然后我们考虑怎么取这个位置,那我这里肯定是和钱有关的,我的钱越多肯定是更不怕挂掉的,当我怎么用钱都不会挂的时候就全部二分就行;当我没钱的时候,我肯定是取在 \(\frac{1}p\)。因为我不会分析,所以我认为放置位置关于钱数是线性的。粗略地估计最大钱数,那就是每次都挂掉我还能继续二分,大概是 \(l\log_2(r-l)+r-l\),就是每轮先认为要 \(l\) 块钱再算一下剩下的贡献,取 \(\frac 1 p = 0.3\),实测可以在 \(103\) 次内解决。

(尝试卡了几下但是最后还是在 \(103\) 次止步了。)

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int nwc;
bool query(int x) {cout << "?" << " " << x << endl;string s; cin >> s;if(s == "Lucky!") {nwc += x;return 1;}elsenwc -= x;return 0;
}
void solve() {nwc = 1;int bs = 1;while(bs <= (int)(1e14)) {if(!query(bs))break;bs <<= 1;}int lp = (bs >> 1), rp = min((int)(1e14), bs - 1) + 1;while(lp + 1 < rp) {int mid = lp + rp >> 1, len = rp - lp, pos;double rat = log2(len) * lp + 2 * (mid - lp);if(nwc >= rat) pos = mid;else {double t = 0.3 + 0.2 * nwc / rat;pos = lp + (rp - lp) * t;}while(nwc < pos)query(lp);if(query(pos))lp = pos;elserp = pos;}cout << "! " << lp << endl;
}
signed main() {int T; cin >> T;while(T--)solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=32536

相关文章:

  • 20251016 正睿二十连测
  • [贝佐斯-六页纸]
  • cc
  • 感知节点@7@ ESP32+arduino+ 第五个程序FreeRTOS 上 增加一个新任务ADC任务
  • 2025年10月切削液厂家 TOP 企业品牌推荐排行榜,全合成切削液,半合成切削液,微乳切削液推荐这十家公司!
  • 普源精电RIGOL DS2202A示波器保存波形到CSV文件过慢解决方法:保存为WFM格式、通过LAN接口使用SCPI+PyVISA控制
  • 动手学深度学习——引言
  • CF1989E Distance to Different
  • AngularJS:构建更智能的Web应用框架
  • 给档案装上“智慧大脑”:文档抽取技术的四大赋能场景
  • P11816QOJ1250 Pionki 轮廓线DP
  • linux系统scatter/gather I/O技术
  • PostgreSQL 为什么不选择 B+ 树索引? - Lafite
  • Joeys shell
  • Redis 集群从部署到可视化管理全流程(超详细实战指南)
  • 什么是BPM流程自动化?从“财务报销”入手,一文读懂企业效率引擎
  • 软件工程学习日志2025.10.16
  • P1072 [NOIP 2009 提高组] Hankson 的趣味题
  • 25w41a快照测评:鹦鹉螺成精了?长矛教你戳穿末影人!
  • Day15-C:\Users\Lenovo\Desktop\note\code\JavaSE\Basic\src\com\classlei
  • Day14
  • window电脑开启hyperV虚拟化功能后导致本地服务端口被占用问题处理方案
  • RAG检索质量差?这5种分块策略帮你解决70%的问题
  • 初识pytorch:网络骨架中的填充之各种层
  • Day5字符型
  • 本地链路地址
  • 体育
  • Meta推出Agent Learning via Early Experience,推动语言代理自主学习新范式
  • Fiddler And LINQ - 特洛伊
  • 计算机视觉在自动化质检中的应用