题解 P5779 【[CTSC2001]聪明的学生】

· · 题解

既然没有人发题解，那我就发一篇吧~

此题的关键点在于，题目中的一句话：总是头上贴着最大的那个数的人最先猜出自己头上的数。至于怎么推的，我也不知道QAQ。

根据样例分析一下我们可以知道，当一个人（头上数字最大的人）能够推理出自己的数字的情况有以下两种：

(其实我觉得推理的过程可以视为假设自己的数字是其他两人数字之差然后推翻这个结论即可）

1.其他两人的数字相同。 此时我们可以得知自己头上的数字一定是其他两人的数字之和，因为题目中提到了，三个人头上的数字均为正整数（如果是其他两数之差的话就是0了，不符合题意）；

2.假设自己的数字不是最大的（即为其他两人数字之差），而在这种情况下，数字最大的那个人在他理论上能够猜出的那一步却没有猜出来。 因为我们知道这三个人都非常聪明，所以在这种情况下就只有一种可能了：自己是其他两数之和。

设f(x,y,t）表示目前第t个人头上的数字最大（为表示方便，A对应t=0，B对应t=1，C对应t=2）其后一个人的数字是x，前一个人的数字是y时能猜出自己数字的步数。 可以知道，如果x>y，那么f(x,y,t)=f(y,x-y,t 的下一位)+2；反之，则f(x,y,t)=f(y-x,x,t的前一位)+1。（+2和+1的对应关系不要搞反啦，一个是转一圈回来，一个是直接顺着下一步就到啦）

于是我们就可以通过递归的方式来解决啦~ （当然也可以直接用循环倒推求解）

下面是代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int M=3e4+111;
int n,m;
int nxt[3]={1,2,0},pre[3]={2,0,1};
int ans[M][3];
int dfs(int x,int y,int now)
{
    if(x==y) return now+1;
    else return x>y?dfs(y,x-y,nxt[now])+2:dfs(y-x,x,pre[now])+1; 
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==-1) break;
        int p0=(n-1)%3,p1=nxt[p0],p2=pre[p0];
        int cnt=0;
        for(int i=1;i< m;i++) if(dfs(i,m-i,p0)==n) ans[++cnt][p0]=m,ans[cnt][p1]=i,ans[cnt][p2]=m-i;
        printf("%d\n",cnt);
        if(p0!=1) for(int i=1;i<=cnt;i++) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
        else for(int i=cnt;i>=1;i--) printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
    }
    return 0;
}

如果宁发现了哪里写得不对的地方，欢迎指出~

如果觉得写得还可以的话，记得点个赞哦~

感谢阅读~