NYOJ 453 小珂的烦恼

梦里梦外; 2022-09-19 08:16 214阅读 0赞

## 小珂的烦恼 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

小珂遇到了一个麻烦的问题，有这样的N对数（1，2），（3，5），（4，7），（6，10）……，第i对的差值为i，第n对数的第一个数为没在前n-1对中出现过的数中最小的，现在要找第n对这样的数，你能帮帮他吗？

输入

第一行只有一个整数m（m<=10000),表示测试数据组数。  
接下来的m行，每行有一个整数n(n<=100000)。

输出

输出第n对数，每组输出占一行。

样例输入

2
    1
    3

样例输出

1 2
    4 7

这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。  
有两堆火柴棍,每次可以从某一堆取至少1根火柴棍(无上限)，或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了,如果你不知道这个博弈定理,对于小数目的火柴棍数,可能还能推出来,但是如果火柴棍数一多,就不行了。看了下面的这个介绍,你也会有一种被骗的感觉。  
首先我们知道两堆火柴是没有差别的,也就是说第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一样的结果。  
我们用一个二维的状态（a,b)来记录当前剩下的火柴数，表示第一堆剩下a根火柴,第二堆剩下b根火柴。同样我们假设两个人的编号是A和B，且A先取。  
那么如果某个人遇到了这样的状态(0,0)那么也就是说这个人输了。这样的状态我们叫做奇异状态,也可以叫做失败态。  
那么接下来的几个失败态为(1,2),(3,5),(4,7),(6,10),(8,13)……  
我们用a\[i\]表示失败态中的第一个,b\[i\]表示失败态中的第二个.(i从0开始).  
那么我们可以看到b\[i\] = a\[i\]+i;（i >= 0）,a\[i\]是前面的失败态中没有出现过的最小的整数  
下面我们可以得到三个基本的结论。  
1.每个数仅包含在一个失败态中  
首先我们知道a\[k\]是不可能和前面的失败态中的a\[i\],b\[i\]重复的(这点由a\[i\]的得到可以知道)  
b\[k\] = a\[k\]+k > a\[k-1\]+k>a\[k-1\]+k-1+1>a\[k-1\]+(k-1) = b\[k-1\]>a\[k-1\]这样我们知道每个数仅在一个失败态中。  
2.每个失败态可以转到非失败态。  
加入当前的失败态为(a,b)，那么如果我们只在一堆中取的话,肯定会变成非失败态(这点由第一点可以保证),如果从两堆同时取的话,由于每个失败态的差是不一样的,所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取,都会得到一个非失败态。  
3.每个非失败态都可以转到一个失败态  
对于这个结论,首先我们要知到每个状态(a,b)要么a = a\[i\],要么b = b\[i\].(每个数都出现在一个失败态中),下面我们分两种情况来讨论  
I.a = a\[i\].如果b = a的话那么一次取完就变成了(0,0).如果b > b\[i\]的话,那么我们从第二堆中取走b-b\[i\]就变成了一个失败态。如果b < b\[i\].那么我们从两堆中同时取走a-a\[b-a\[i\]\]这样得到失败态(a\[b-a\[i\]\],a\[b-a\[i\]\]+b-a\[i\])(a\[i\] = a)  
II.b = b\[i\].如果a > a\[i\]那么我们从第一堆中取走a-a\[i\]根火柴.  
如果a < a\[i\].这里又分两种情况。第一是a = a\[k\](k < i)  
那么我们从第二堆取走b - b\[k\]就行了。  
第二是a = b\[k\]这样的话由于两堆火柴是没有区别的,所以我们把b变成a\[k\]就行了,也即是从第二堆火柴中取走b - a\[k\]就变成了失败态  
至于怎么判断一个状态是否是失败态.我们可以用下面的方法来判断  
a\[i\] = \[i\*(1+√5)/2\](这里的中括号表示向下取整) b\[i\] = a\[i\]+i;  
那么这就是一个失败态,

#include<stdio.h>
    #include<math.h>
    int main()
    {
    int n,k,j;
    
    scanf("%d",&n);
    while(n--)
    {
    scanf("%d",&k);
    
    j=(k*(1+sqrt(5)))/2.0;
    
    printf("%d %d\n",j,j+k);
    
    
    }
    return 0;
    }

来看最优程序：

#include<stdio.h>
    #define N 170001
    #define M 100001
    bool a[N];
    int  b[M];
    int main()
    {
    	int n,i,j;
    	for(i=1;i<=M;i++)
    	{
    		for(j=b[i-1]+1;a[j];j++);
    		b[i]=j;a[j]=1;
    		if(j+i<=N-1)	a[j+i]=1;
    	}
    	scanf("%d",&n);
    	while(n--)
    	{
    		scanf("%d",&i);
    		printf("%d %d\n",b[i],b[i]+i);
    	}	
    	return 0;
    }