zoj 2313 Chinese Girls' Amusement 解题报告

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1313

题目意思：有 N 个人（编号依次为1~N）围成一个圆圈，要求求出最大的 K （1 ≤ K ≤ N/2），表示从编号为1的人开始，将球传递给他后一个人数起的第K个人，第K个人又传递给往后数的第K个人......要求这样传递下去，且每个人都有机会接到球。也就是不存在当未使得全部人都接到一次球的情况下，某个人接收到两次以上的球。

详细的解题报告在这里：

http://blog.watashi.ws/623/andrew-stankevich-1-solutio/

而参考了这个人的写法，我也写出了属于自己的，happy ^_^~~~

http://www.xuebuyuan.com/1552889.html

比赛的时候，通过枚举小例子，只推出这个公式：

(1) N 为奇数的时候：

　　K = N / 2

(2) N 为偶数的时候

　　　　算出 (N-2)/2，分两种情况讨论。

(i) (N-2)/2 是奇数，K 就为 (N-2)/2

(ii) (N-2)/2 是偶数，K 就为 (N-2)/2 - 1。

例如：N = 16，K = (16-2)/2 = 7

N = 18，K = （18-2) / 2 - 1 = 7

因为 N 十分大，需要用到高精度处理。

其实我找出的规律也是正确的，只是不同表示而已~~~

对于代码中偶数需要分情况讨论，除了都需要将N/2 算完之后还需要减1操作，还要进一步讨论的原因。还是拿回16 和 18 来讲。16/2 - 1 之后是一个奇数，也就是结果啦，但是对于18，18/2 -1 = 8，正确结果应该是7，所以如果操作完第一次的除以2再减1之后发现最后那位是偶数，还需要继续执行多一步的减1操作。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

const int maxn =  + ;

int num[maxn];

char str[maxn];

inline int CharToInt(char i)

{

    return (i - '');

}

void Div(int num[], int len)

{

    int i = , f = ;

    while (i < len)

    {

        if (num[i] & )

            num[i+] += ;

        num[i++] = (num[i] ==  && f ?  : num[i]>>);  // 第一位有可能是1

        f = ;

    }

}

void Minus(int num[], int len)

{

    int i = len-;

    while (i >=  && num[i] == )  // 防止类似100000的情况

        num[i--] = ;

    num[i] -= ;   // 末尾不是0的话，直接从最后一位减1即可。

}

inline void Print(int num[], int len)

{

    int i = ;

    if (num[i] == )   // 过滤前导零

        i++;

    for ( ; i < len; i++)

        printf("%d", num[i]);

    printf("\n");

}

int main()

{

    int T;

    while (scanf("%d", &T) != EOF)

    {

        while (T--)

        {

            memset(num, , sizeof(num));

            scanf("%s", str);   // 如果前面用getchar()再用gets(str)会OutputlimitExceeded

            int len = strlen(str);

            for (int i = ; i < len; i++)

                num[i] = CharToInt(str[i]);

            if (num[len-]&)   // 奇数直接等于n/2;

            {

                Div(num, len);

                Print(num, len);

            }

            else

            {

                Div(num, len);

                Minus(num, len);    // 偶数分情况讨论

                if (num[len-] & )

                    Print(num, len);

                else

                {

                    Minus(num, len);

                    Print(num, len);

                }

            }

            if (T)

                puts("");

        }

    }

    return ;

}

对于 http://blog.watashi.ws/623/andrew-stankevich-1-solutio/ 这个人的写法中

int *Mul(int *num)

{

  for(int i=0;i<n;i++){

		if(num[i]&1) num[i+1]+=10;

		num[i]>>=1;

  }

  num[n]=0;        /* 这部分写得很妙，应该就是为了处理前导0的情况， 简洁方便 */

  while(*num==0){

   ++num;

   n--;

   }

   return num;

}

巴特西

zoj 2313 Chinese Girls' Amusement 解题报告

最新文章

热门文章