UVa 10826 Hot or Cold

题目描述

你和朋友在玩一个猜数字游戏。 朋友想一个111到NNN之间的整数（包含两端）。 你可以无限次猜测，但希望用尽可能少的次数猜中。 朋友不会直接告诉你是否正确；唯一的反馈是：从第二次猜测开始，他会说“变热”或“变冷”，表示这次猜测比上一次更接近还是更远离目标数字（如果距离相同，他可能说任意一个）。 当你确定最后一次猜测正确时，告诉朋友，游戏胜利。

注意：每次猜测都必须是真正的猜测，符合所有已知信息。

问题：在最坏情况下，需要多少次猜测？

输入：多个测试用例，每行一个整数NNN（1≤N≤3001 \le N \le 3001≤N≤300），以N=0N = 0N=0结束。

输出：对每个用例，输出最大猜测次数。

样例输入：

75 75 0

样例输出：

10 guess(es) required. 10 guess(es) required.

题目分析

这是一个最优最坏情况决策问题。我们需要设计一个策略，使得在最坏的反馈序列下，猜测次数最少。

关键约束：

1. 第一次猜测没有“变热/变冷”反馈
2. 第二次及以后的每次猜测都有反馈（相对于上一次）
3. 反馈只告诉我们“更近”或“更远”，不直接给出距离

解题思路

1. 问题本质

每次猜测后，根据反馈可以排除一部分不可能的数字。我们需要选择猜测位置，使得无论反馈如何，剩余的可能区间尽可能小。

2. 状态定义

设f(l,r,last)f(l, r, last)f(l,r,last)表示：

• 已知目标数字在区间[l,r][l, r][l,r]内
• 上一次猜测的数字是lastlastlast
• 从当前状态开始，还需要的最少猜测次数（包括当前这次）

边界情况：

• 如果l=rl = rl=r且last=llast = llast=l，说明已经知道答案，只需111次确认
• 如果l=rl = rl=r但last≠llast \neq llast=l，需要先猜lll，再确认，共222次

3. 状态转移

假设当前猜测ggg（g∈[l,r]g \in [l, r]g∈[l,r]且g≠lastg \neq lastg=last），根据反馈：

• “变热”：目标离ggg比离lastlastlast更近，即∣x−g∣<∣x−last∣|x - g| < |x - last|∣x−g∣<∣x−last∣
• “变冷”：目标离ggg比离lastlastlast更远，即∣x−g∣>∣x−last∣|x - g| > |x - last|∣x−g∣>∣x−last∣

我们需要计算两种反馈对应的新区间。

区间划分公式

解不等式∣x−g∣<∣x−last∣|x - g| < |x - last|∣x−g∣<∣x−last∣：

1. 如果g<lastg < lastg<last：
   目标xxx在ggg和lastlastlast的中点右侧，即x>g+last2x > \frac{g + last}{2}x>2g+last​
   由于xxx是整数，分两种情况：

   • 如果g+lastg + lastg+last是偶数：x>g+last2x > \frac{g + last}{2}x>2g+last​即x≥g+last2+1x \ge \frac{g + last}{2} + 1x≥2g+last​+1
   • 如果g+lastg + lastg+last是奇数：x>g+last2x > \frac{g + last}{2}x>2g+last​即x≥⌈g+last2⌉x \ge \lceil \frac{g + last}{2} \rceilx≥⌈2g+last​⌉

   令mid1=⌊g+last2⌋mid1 = \lfloor \frac{g + last}{2} \rfloormid1=⌊2g+last​⌋，mid2=⌈g+last2⌉mid2 = \lceil \frac{g + last}{2} \rceilmid2=⌈2g+last​⌉，则：

   • “变热”对应区间[max(l,mid2),r][max(l, mid2), r][max(l,mid2),r]
   • “变冷”对应区间[l,min(r,mid1)][l, min(r, mid1)][l,min(r,mid1)]

2. 如果g>lastg > lastg>last：对称地：

   • “变热”对应区间[l,min(r,mid1)][l, min(r, mid1)][l,min(r,mid1)]
   • “变冷”对应区间[max(l,mid2),r][max(l, mid2), r][max(l,mid2),r]

4. 最优决策

对于每个状态(l,r,last)(l, r, last)(l,r,last)，我们枚举所有可能的猜测ggg，计算：

• hot=f(“变热”后的区间,g)hot = f(\text{“变热”后的区间}, g)hot=f(“变热”后的区间,g)
• cold=f(“变冷”后的区间,g)cold = f(\text{“变冷”后的区间}, g)cold=f(“变冷”后的区间,g)

由于我们考虑最坏情况，所以这次猜测的代价是1+max⁡(hot,cold)1 + \max(hot, cold)1+max(hot,cold)。
我们选择ggg使得这个代价最小：

f(l,r,last)=min⁡g∈[l,r],g≠last(1+max⁡(hot,cold)) f(l, r, last) = \min_{g \in [l, r], g \neq last} \left( 1 + \max(hot, cold) \right)f(l,r,last)=g∈[l,r],g=lastmin​(1+max(hot,cold))

5. 状态压缩与记忆化

直接三维状态f(l,r,last)f(l, r, last)f(l,r,last)的状态数是O(N3)O(N^3)O(N3)，太大。

关键观察：状态实际上只依赖于：

1. 区间长度length=r−llength = r - llength=r−l
2. lastlastlast到区间边界的距离dist={last−lif last≥lr−lastif last<ldist = \begin{cases} last - l & \text{if } last \ge l \\ r - last & \text{if } last < l \end{cases}dist={last−lr−last​iflast≥liflast<l​

这是因为区间可以平移，相同长度和相对距离的状态是等价的。

因此我们使用二维数组dp[length][dist]dp[length][dist]dp[length][dist]进行记忆化，状态数降为O(N2)O(N^2)O(N2)。

6. 初始猜测

第一次猜测没有lastlastlast，我们可以选择任意位置first∈[1,N]first \in [1, N]first∈[1,N]。
最终答案是min⁡firstf(1,N,first)\min_{first} f(1, N, first)minfirst​f(1,N,first)。

算法复杂度

• 状态数：O(N2)O(N^2)O(N2)
• 每个状态计算：枚举O(N)O(N)O(N)个可能的ggg
• 总复杂度：O(N3)O(N^3)O(N3)，对于N≤300N \le 300N≤300可以接受

参考代码

// Hot or Cold// UVa ID: 10826// Verdict: Accepted// Submission Date: 2025-12-24// UVa Run Time: 0.050s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=310,INF=0x3f3f3f3f;// dp[length][dist] 还需要的最小猜测次数intdp[MAXN][MAXN];// 计算在区间 [l, r] 内，已知上次猜测是 last 时，还需要的最小猜测次数intdfs(intl,intr,intlast){// 区间只剩一个数if(l==r)return(last==l)?1:2;// 压缩状态：length = 区间长度，dist = last到边界的距离intlength=r-l;intdist=(last>=l)?(last-l):(r-last);// 记忆化if(~dp[length][dist])returndp[length][dist];intbest=INF;// 枚举当前猜测点 gfor(intg=l;g<=r;++g){if(g==last)continue;// 不能重复猜同一个数// 计算分界点：|t-g| < |t-last| 等价于 t > midintmid1=(g+last)/2;// 向下取整intmid2=(g+last+1)/2;// 向上取整inthot=0;// "更热"情况intcold=0;// "更冷"情况if(g<last){// g 在 last 左边// "更热": 目标在右边 [max(l,mid2), r]if(mid2<=r)hot=dfs(max(l,mid2),r,g);// "更冷": 目标在左边 [l, min(r,mid1)]cold=dfs(l,min(r,mid1),g);}else{// g 在 last 右边// "更热": 目标在左边 [l, min(r,mid1)]if(mid1>=l)hot=dfs(l,min(r,mid1),g);// "更冷": 目标在右边 [max(l,mid2), r]cold=dfs(max(l,mid2),r,g);}// 最坏情况 + 当前这次猜测intworst=max(hot,cold)+1;best=min(best,worst);}returndp[length][dist]=best;}intmain(){// 初始化记忆化数组memset(dp,-1,sizeofdp);intn;while(cin>>n&&n){intanswer=INF;// 第一次猜测可以选择任意位置for(intfirst=1;first<=n;++first){answer=min(answer,dfs(1,n,first));}cout<<answer<<" guess(es) required."<<endl;}return0;}

总结

本题的难点在于：

1. 理解“变热/变冷”反馈的信息含义
2. 将问题转化为区间划分的动态规划
3. 设计状态压缩减少复杂度

核心技巧：

• 利用不等式推导区间划分公式
• 通过对称性压缩状态
• 采用min⁡max⁡\min \maxminmax决策应对最坏情况

这个解法充分利用了问题的数学性质，在O(N3)O(N^3)O(N3)时间内解决了N≤300N \le 300N≤300的问题，是一个优雅且高效的解决方案。