哎呀~我的天哪~刚刚拿你的代码测试~输入6时输出6~正确答案应该是输出5~有时间我用队列做做看~你可以先试试改改代码~用数组要注意~我知道开不了10亿这么大~开个100000或者1000000~如果遇到重复算数就直接返回该数就行了~10亿/10万=10万~运算10万次应该不会超时的~感觉用数组虽然容易想到~但实现难度不少啊~不过你可以自己敲代码倒是很不错了虽然代码有点问题~

改了一下，不会超时
但是错了
#include <stdlib.h>
#include <math.h>
#include <string.h>
int d[100005];
int f(int n)
{
    if(n<=100000) return d[n];
    if(n>3)
    {
        if(n%2) return f((n-1)/2)+f((n+1)/2);
        else return f(n/2-1)+f(n/2+1);
    }
    else return 2;
}
void sol()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",f(n));
}
int main()
{
    d[3]=2,d[4]=3,d[5]=4,d[6]=5;
    for(int i=7;i<=100000;i++)
    {
        if(i%2) d[i]=d[(i-1)/2]+d[(i+1)/2];
        else  d[i]=d[i/2-1]+d[i/2+1];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    sol();
    return 0;
}

这种题卡着难受

我有时间去推敲一下思路有没有问题~如果可以要拿个标准答案对着看哪里出问题~逻辑错误除了要靠自己发现外就要靠标准答案了~

这种题算法应该不难~难就在自己哪里出问题了都不知道~不好说逻辑哪里出问题了~~

果然是我逻辑有问题~10个人7个卧底就够了~我再想想~

//敌方出1人，我方得出2人
//敌方出3人，我方得出4人 // 经过一轮后，就变成了“敌方出1人，我方得出2人”
//敌方出7人，我方得出8人 // 经过一轮后，就变成了“敌方出3人，我方得出4人”
//敌方出15人，我方得出16人 // 经过一轮后，就变成了“敌方出7人，我方得出8人”
//…………
//
//假设敌我共有5人，那么
//敌方1人 可以，我方只要2人就行了
//敌方3人 不可以，我方至少要4人
//
//假设敌我共有30人，那么
//敌方1人 可以，我方只要2人就行了
//敌方3人 可以，我方只要4人就行了
//敌方7人 可以，我方只要8人就行了
//敌方15人 不可以，我方至少要16人

因此有代码：

#include <stdio.h>

unsigned foo( unsigned n )
{
    unsigned x;
    for( x=1; (1u<<x)-1 <= n; ++x );
    return n-(1u<<(x-2))+1;
}

int main( void )
{
    for( unsigned n=1; n<=80; ++n )
        printf( "%u: %u\n", n, foo(n) );
}

前80个数是.
1: 1
2: 2
3: 2
4: 3
5: 4
6: 5
7: 4
8: 5
9: 6
10: 7
11: 8
12: 9
13: 10
14: 11
15: 8
16: 9
17: 10
18: 11
19: 12
20: 13
21: 14
22: 15
23: 16
24: 17
25: 18
26: 19
27: 20
28: 21
29: 22
30: 23
31: 16
32: 17
33: 18
34: 19
35: 20
36: 21
37: 22
38: 23
39: 24
40: 25
41: 26
42: 27
43: 28
44: 29
45: 30
46: 31
47: 32
48: 33
49: 34
50: 35
51: 36
52: 37
53: 38
54: 39
55: 40
56: 41
57: 42
58: 43
59: 44
60: 45
61: 46
62: 47
63: 32
64: 33
65: 34
66: 35
67: 36
68: 37
69: 38
70: 39
71: 40
72: 41
73: 42
74: 43
75: 44
76: 45
77: 46
78: 47
79: 48
80: 49

收到的鲜花

• 九转星河 于 2017-03-28 11:29 送鲜花  10朵   附言：好~

我以前写过类似的

发现 在2的n次幂-1的时候是2的n-1次幂 然后到2的n+1次幂-1到时递增为1的

但是交上去错了

主要问题在于敌方出偶数个人的时候 我方该出多少人

敌方出 2个人 我方出 4 个人是能赢的
敌方出 4个人 我方出 6个人

理论上是可以赢得 我就等他们选到多的人在一边的时候把他们淘汰掉

但是也有可能是一直僵局。。。。

有思路可以看看~
也是要分真正参赛者人数为奇数和偶数的时候讨论~
用递推思想~
设真正参赛者人数为n总人数至少为f(n)满足条件~
f(1)=3~
则当n为偶数时~f(n+1)=f(n)~
当n为奇数的时候f(n+1)=2*f((n+1)/2)+1~
具体点举个例子~当真正参赛者由一人增加到两人的时候要分别对掉两个1人而且还要另外加1个卧底~当真正参赛者由两人增加到三人的时候因为抽屉原理~就把原来一名多余的卧底去掉就行了~所以总人数不变~当真正参赛者从三人增加到四人的时候就是要分别对掉两个人~这时需要的卧底数为2*对掉两个人所需要的卧底数另外加1个卧底~以此类推~

另一半求总参赛者对应的真正参赛者应该为多少这个可以先去想想就先不写了~

f(n)
所以表示真正参赛者n人对应的至少总人数为f(n)~
g(n)表示对掉参赛人数所需要的最小卧底数~
f(1)=3  g(1)=2
f(2)=7  g(2)=5
f(3)=7  g(3)=4
f(4)=15 g(4)=11
f(5)=15 g(5)=10
f(6)=15 g(6)=9
f(7)=15 g(7)=8
f(8)=31 g(8)=23
f(9)=31 g(9)=22
f(10)=31 g(10)=21
f(11)=31 g(11)=20
f(12)=31 g(12)=19
f(13)=31 g(13)=18
f(14)=31 g(14)=17
f(15)=31 g(15)=16
f(16)=63 g(16)=47
~

[此贴子已经被作者于2017-3-28 13:55编辑过]