Blog·Tanky WooABOUTRSS

HDU/HDOJ 2211 杀人游戏(找规律)

14 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

这题不好定位,暂定为找规律。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2211

这题我是看了wiskey的分析才会的~~~:

用计算机先测试几个小数据得到结论的,假设N个人,每次找剩下的人中的第K个,那么N在一段连续的范围内有一个固定的值,那么我们这里就需要构造这些固定的值,第一个就一定是K(N==K),以后假设前一个是F1,则后一个是F2,如果F1*K/(K-1)正好是整数,即F1整除(K-1),那么F2=F1*K/(K-1)-1,如果F1不整除(K-1),那么F2=F1*K/(K-1)取整。对于K=3时,有如下的序列: 3,4,5,7,10,…… 所以对于7到9之间的数字N,最后一定是7,就这个规律。

AC代码:

我先开始是每次输入N,K就计算当前K的规律,不过TLE了,看来数据很多,先一次性打表,可以用__int64存储数据。

// Author: Tanky Woo
// Blog:   www.WuTianQi.com
// Problem: HDOJ 2211 杀人游戏
#include 
#include 
using namespace std;

__int64 arr[110][100000];
long T, N, K;


int main()
{
    __int64 _max= 1;
    _max = _max << 32;
    for(int i=3; i<110; ++i)
    {
        arr[i][0] = i;
        for(int j=1; arr[i][j-1]<_max; ++j)
            if(arr[i][j-1] % (i-1) == 0)
                arr[i][j] = arr[i][j-1] * i/(i-1) - 1;
            else
                arr[i][j] = abs((arr[i][j-1] * i * 1.0)/(i-1));
    }
    cin >> T;
    while(T--)
    {
        cin >> N >> K;
        for(int i=0;; ++i)
            if(arr[K][i] > N)
            {
                printf("%I64d\n", arr[K][i-1]);
                break;
            }

    }
    return 0;

}