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

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

题目链接: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存储数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Author: Tanky Woo
// Blog:   www.WuTianQi.com
// Problem: HDOJ 2211 杀人游戏
#include <iostream>
#include <cmath>
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;
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注