首页 > 代码库 > zoj 2313 Chinese Girls' Amusement 解题报告
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 = 2000 + 10;int num[maxn];char str[maxn];inline int CharToInt(char i){ return (i - ‘0‘);}void Div(int num[], int len){ int i = 0, f = 1; while (i < len) { if (num[i] & 1) num[i+1] += 10; num[i++] = (num[i] == 0 && f ? 0 : num[i]>>1); // 第一位有可能是1 f = 0; }}void Minus(int num[], int len){ int i = len-1; while (i >= 0 && num[i] == 0) // 防止类似100000的情况 num[i--] = 9; num[i] -= 1; // 末尾不是0的话，直接从最后一位减1即可。}inline void Print(int num[], int len){ int i = 0; if (num[i] == 0) // 过滤前导零 i++; for ( ; i < len; i++) printf("%d", num[i]); printf("\n");}int main(){ int T; while (scanf("%d", &T) != EOF) { while (T--) { memset(num, 0, sizeof(num)); scanf("%s", str); // 如果前面用getchar()再用gets(str)会OutputlimitExceeded int len = strlen(str); for (int i = 0; i < len; i++) num[i] = CharToInt(str[i]); if (num[len-1]&1) // 奇数直接等于n/2; { Div(num, len); Print(num, len); } else { Div(num, len); Minus(num, len); // 偶数分情况讨论 if (num[len-1] & 1) Print(num, len); else { Minus(num, len); Print(num, len); } } if (T) puts(""); } } return 0;}
对于 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 解题报告