P5779 题解

yx666 · 2024-01-26 09:51:20 · 题解

P5779 题解

题意简述

梗概

• 教授在三个学生学生 A，B 和 C 的脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。

• 接着，教授从学生 A 开始，以 A，B，C，A，……，的顺序询问每个学生能否猜出自己头上的数，学生只可回答「不能」或自己头上的数。

• 教授在第 N 次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是 M，请推断出另外两个学生的头上贴的是什么数。

• 对于全部数据，N<500，M<3\times 10^4。

提示

1. 每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。

2. 教授总是从学生 A 开始提问的。

3. 这三个足够聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。

4. 稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。

解题思路

思考

本题的入手点为：总是头上贴着最大的那个数的人最先猜出自己头上的数。 至于为什么，我也不知道。

那么，一个人是怎么确定自己是最大的那个人呢？

明显，他可通过反证法，只要自己不是那两个人的差，那么自己就是那两个人的和，也就是最大的那个。

假设自己是其他两人之差，考虑以下情况：

1. 其他两个人数字相同：因为大家都是正整数，所以自己只能为和，假设不成立。

2. 其他两个人数字不同：因为头上贴着最大的那个数的人最先猜出自己头上的数，所以：如果其他两个人中最大的那个人没有在最早的轮次猜出自己的数，那么自己就是最大的数。

举例

上面那句话有点绕，举点例子：

例1：

• A，B，C 分别为 2，4，6。

• 对于 C，他会设自己为 2。显然，如果 C 假设成立，当前就是 2，4，2，那么 B 会在第一次问到他时猜出，因为 A，C 数字相同。

• 但对于 B，他只知道面前两人分别是 2 和 6，第一次问到他时猜不出，所以 C 会发现自己的假设是错的。

• 所以 C 为推翻自己的假设，得到自己是 6，在第一次问到他时就会猜出。

例2：

• A，B，C 分别为 2，8，6（第一个样例）。

• 对于 B 来讲，他设自己是 A，C 两人的差 4，当前是 2，4，6。

• B 想，如果当前是 2，4，6，那么 C 会在第一次问到他时就猜出答案（例1）。

• 但是这次，C 显然不会在第一次就猜出答案，推翻了 B 的假设。

• 所以 B 在第二次问到他时就猜出了自己是 A，C 之和 8。

总结

不难发现，每个人的假设都是由其他两人中最大的那个人的回答来推翻的。

而每个人的回答又套在他的假设之上，也就是其他人的回答，这是一个类似于俄罗斯套娃的逻辑回路。

所以，我们想到递归（或者递推、DP）。

代码实现

核心代码

核心思路

1. 定义：

   • 不妨设 short dfs(short x, short y, short p) 表示一个人猜出自己的数需要的最早轮次数。
   • 其中 x 表示上家的数字，y 表示下家的数字，p 表示当前的该人的位置（0 表示 A，1 表示 B，2 表示 C）。

2. 限制条件：

3. 转移方程：

   • \operatorname{dfs}(x,y,p)=\begin{cases}\operatorname{dfs}(y-x,x,xj_{p})+2&x< y\\p+1 &x=y\\ \operatorname{dfs}(y,x-y,sj_{p})+1\ &x>y\\\end{cases}
   • 其中 sj_{p} 与 xj_{p} 分别指 p 的上家和下家。
   • 注意 +1 与 +2 的区别，上家只需一步就轮到该人，下家则需两步。

4. 答案：

   • 从 0 到 m-1 依次枚举 x，如果 \operatorname{dfs}(x,m-x,p)=n，则记录答案（其中 p 为 (n-1) \bmod 3）。

核心源码

short sj[] = {2, 0, 1}; // 返回上家
short xj[] = {1, 2, 0}; // 返回下家

/*
 * x：该人上家头顶的号码
 * y：该人下家头顶的号码
 * p：该人的位置（0,1 或 2）
 */
short dfs(short x, short y, short p)
{
    if (x == y)
        return p + 1;
    else
        return x > y ? dfs(y, x - y, sj[p]) + 1 : dfs(y - x, x, xj[p]) + 2;
}

总体代码

#include <stdio.h>

#ifndef DEBUG
#define DEBUG 0

#endif

short sj[] = {2, 0, 1}; // 返回上家
short xj[] = {1, 2, 0}; // 返回下家

/*
 * x：该人上家头顶的号码
 * y：该人下家头顶的号码
 * p：该人的位置（0,1 或 2）
 */
short dfs(short x, short y, short p)
{
    if (x == y)
        return p + 1;
    else
        return x > y ? dfs(y, x - y, sj[p]) + 1 : dfs(y - x, x, xj[p]) + 2;
}

/*
 * 存答案，ans_sj 存上家，ans_sj 存下家
 * ans_sj 是正序的（从小到大），ans_xj 是倒序的
 */
short ans_sj[30002], ans_xj[30002];

int main()
{
    short n, m;
    while (scanf("%hd %hd", &n, &m) != EOF)
    {
        if (n == -1 && m == -1)
            break;

        short p_now = (n - 1) % 3; // 最大的人的位置

        short cnt = 0;
        for (short i = 1; i < m; ++i) // 枚举
        {
            if (dfs(i, m - i, p_now) == n)
                ans_sj[cnt] = i, ans_xj[cnt] = m - i, ++cnt;
        }

        printf("%hd\n", cnt);
        if (p_now == 1) // 上家在前
        {
            for (short i = 0; i < cnt; ++i)
                printf("%hd %hd %hd\n", ans_sj[i], m, ans_xj[i]);
        }
        else // 下家在前
        {
            if (p_now == 0) // 最大的在第一个
                for (short i = cnt - 1; i >= 0; --i)
                    printf("%hd %hd %hd\n", m, ans_xj[i], ans_sj[i]);

            else // 最大的在最后一个
                for (short i = cnt - 1; i >= 0; --i)
                    printf("%hd %hd %hd\n", ans_xj[i], ans_sj[i], m);
        }
    }
    return 0;
}