【bzoj2523】【CTSC2001】聪明的学生

我就是我 2021-11-09 07:18 291阅读 0赞

真是神仙题，做完后感觉智商提(jiang)升(di)了

这种题一般都是把局面设成状态，然后发现可以由一种状态转移到另一种状态，那就是 $dp$ 了。

但是这道题怎么设呢？

**题目中给了你一个结论，一般题目给的信息都不会没用，这题的结论就很有用 —— 一定是数最大的那个人先猜出来**

随便枚举几个例子，你会发现一个有趣的特殊情况：设一个人看到另外两人的数分别为 $x,y(x\\ge y)$，若 $x=y$，那这个人就直接猜出来自己的数了。

因为这个人的数只可能是 $x-y$ 或 $x+y$，而题目说了三个人贴的都是正整数，所以如果 $x-y=0$ 的话，由于 $0$ 不是正整数，这个人就知道了他的数不是 $x-y$，而是 $x+y$。

那 $x≠y$ 的情况呢？

根据题目给的结论，每个人会先假设自己是 $x-y$，然后某个人会在某一轮确定自己不是 $x-y$ 而是 $x+y$，从而说出“知道”。

我们考虑在什么情况下，一个人会最先说出“知道”。

这个人说“知道”显然只和前两轮另外两人的回答有关系（如果能通过再之前的回答确定，那他上一次回答就会说“知道”了）。

结合题目给的结论，可以得知关键就在于另外两人中数大的那个人上次的回答。这个人能确定自己不是 $x-y$ 而是最大值 $x+y$，当且仅当那个人在是最大值的情况下，应该在上一次回答说“知道”，但那个人没说。只有这样才能确定那个人不是最大值，而那个人是另外两人中的最大值，那么自己就一定是最大值，即 $x+y$ 了。

看！局面状态是可以转移的！

设状态为三个人的数组成的三元组，记录的值为最大值应该在第几轮说“知道”，那显然可以由 $(x,y,x-y)$ 转移到 $(x,y,x+y)$，转移贡献就是 $+1$ 或 $+2$（取决于最大值是前面第几位）。我写的三元组是无序的，实际上写代码时应该有序，顺序为（上上个人的数，上个人的数，这个人的数）。

终止状态就是一开始想到的那个特殊情况：如果另外两个人的数相等，那这个人第一次回答就是“知道”，返回这个人是第几个被提问的就行了（$\[1,3\]$ 内的整数）。

事实上你写出代码之后，会发现并不用记这个人的数，只需要记这个人是哪个人就行了。因为转移只与另外两人的数有关系。

还有就是请写裸的搜索，不要写 $dp$/记忆化搜索，因为状态的前两维（另外两人的数）的值域都是 $\[1,M\]$，$M$ 是 $3e4$ 的，你开不下 $dp$ 数组。

时间复杂度就很玄乎了，可能智商题都不用太管时间复杂度吧。

[代码][Link 1]

提交时间不错啊

转载于:https://www.cnblogs.com/scx2015noip-as-php/p/bzoj2523.html

[Link 1]: https://loj.ac/submission/540417

发表评论取消回复

表情：

评论列表（有 0 条评论，291人围观）

还没有评论，来说两句吧...

相关阅读

相关聪明的木匠

一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= L1,L2,…,LN <= 1000，且均为整数）个长度单位。我们认为切割时仅在

「爱情、让人受尽委屈。」/ 2024年02月18日 22:08/ 0 赞/ 45 阅读

相关聪明的KK【ACM】

聪明的kk时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述聪明的“KK” 非洲某国展馆的设计灵感源于富有传奇色彩的沙漠中陡然起伏的沙

傷城~/ 2023年10月18日 08:12/ 0 赞/ 64 阅读

相关聪明的学生

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

青旅半醒/ 2022年11月21日 09:58/ 0 赞/ 168 阅读

相关很多的博文关于聪明的学生的教育的

刚刚过去的IMO，中国史无前例地获得了第三名，也是自1997年来近20年首次跌出前二。感谢微信等社交软件，相信现在这个新闻已经以火箭的速度传播了。作为一个与数学竞赛及IM

蔚落/ 2022年05月25日 00:10/ 0 赞/ 199 阅读

相关 BZOJ5341[Ctsc2018]暴力写挂——边分治+虚树+树形DP

题目链接： [CSTC2018暴力写挂][CSTC2018] 题目大意：给出n个点结构不同的两棵树，边有边权(有负权边及0边)，要求找到一个点对(a,b)满足dep(

梦里梦外;/ 2022年01月13日 03:53/ 0 赞/ 198 阅读

相关【费用流】bzoj1221 [HNOI2001] 软件开发

几乎为“线性规划与网络流24题”中的餐巾问题。这里把S看成毛巾的来源，T看成软件公司，我们的目的就是让每天的毛巾满足要求(边满流)。引用题解：【问题分析】网络优

矫情吗；*/ 2022年01月07日 01:21/ 0 赞/ 182 阅读

相关 [Ctsc2015]misc

[https://lydsy.com/JudgeOnline/problem.php?id=4055][https_lydsy.com_JudgeOnline_problem.

蔚落/ 2022年01月06日 15:59/ 0 赞/ 232 阅读

相关【bzoj2523】【CTSC2001】聪明的学生

真是神仙题，做完后感觉智商提(jiang)升(di)了这种题一般都是把局面设成状态，然后发现可以由一种状态转移到另一种状态，那就是 $dp$ 了。但是这道题怎么设呢？

我就是我/ 2021年11月09日 07:18/ 0 赞/ 292 阅读

相关 [CTSC1997]选课

[题面][Link 1] 题解树形背包板子题。设\\(f\[i\]\[j\]\\)表示在以\\(x\\)为根的子树选\\(j\\)门课（包括\\(x\\)）能

柔情只为你懂/ 2021年10月23日 14:36/ 0 赞/ 302 阅读

相关 BZOJ 1379: [Baltic2001]Postman 水题

1379: \[Baltic2001\]Postman Description 邮递员每天给N个村子的人送信,每个村子可能在某个十字路口上,或一条路的中央.

绝地灬酷狼/ 2021年09月30日 12:58/ 0 赞/ 215 阅读