CF1081F Tricky Interactor
2021/8/14 23:35:54
本文主要是介绍CF1081F Tricky Interactor,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CF1081F Tricky Interactor
Description
这是一道交互题。
有一个长度为 \(n\) 的 \(01\) 序列,初始时 \(1\) 的个数为 \(t\)。定义一次操作为给定 \(l, r(l \le r)\),交互库会等概率地从区间 \([1, r]\) 和 \([l, n]\) 中选择一个,然后翻转下标在该区间内的数(翻转即 \(x \to 1 - x\)),并告诉你翻转完的序列中有多少个 \(1\)。操作之间不是独立的,即对序列的修改是永久的。
你需要在 \(10000\) 次操作内得出原始的序列。
\(n \le 300\)。
Solution
设这个序列为 \(a\)。注意到连续操作 \([i, i]\) 两次所形成的序列要么是 \(a\),要么是除了 \(a_i\) 都翻转的序列。我们可以多随几次,总能碰到第二种情况,然后就能知道第 \(i\) 个数是 \(0\) 还是 \(1\) 了,然后再还原回去。当然有一个问题就是除开 \(a_i\) 以外剩下的 \(01\) 数量相等,这里我们可以把 \([i, i]\) 改为 \([i, i + 1]\),这样每次能得到 \(a_i + a_{i + 1}\),最后再统计一下就可以了。这样我们就得到了一个期望 \(8n\) 次询问的做法。
其实放 \(10000\) 没有必要,完全可以开到 \(3000\),总不至于有人这么非吧。
这篇关于CF1081F Tricky Interactor的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享