《开采金钱》是《经营餐厅》系列中的一个经典游戏，他考验的是人的操作和策略。
游戏的开始会给出一块无限大的平原，玩家要在平原上采集金钱和建造开采矿物的矿塔。每一次操作可以是建造一座矿塔，或采集金币。采集金币的操作是在现有的每个矿塔中各采集一个金钱，比如现有10个矿塔，则可以采集到10个金币。现给出操作的次数s，求最多可以采集到的金币数量。
QDUOJ-20：开采金币（大数乘法）
发布时间：2020-12-14 03:55:08 所属栏目：大数据 来源：网络整理
导读：Problem 20: 开采金币 Time Limit: 1 Ms|? Memory Limit: 128 MB Difficulty: 1 Description 《开采金钱》是《经营餐厅》系列中的一个经典游戏，他考验的是人的操作和策略。 游戏的开始会给出一块无限大的平原，玩家要在平原上采集金钱和建造开采矿物的矿塔
Problem 20: 开采金币Time Limit:1 Ms|? Memory Limit:128 MB Difficulty:1 DescriptionInput
第一行只有一个正整数s，表示小Q有s次操作的机会。
Output
一个数，表示小Q最多能够开采的金币总数。
Sample Input
1
Sample Output
0
Hint
样例中，小Q要么建一座矿塔，要么让所有采一点金钱（但是没有矿塔），所以不可以获得金钱，输出0。
20% : s <= 20 40% : s <= 10000 100% : s <= 10^100
思路：
? ? 普通大数问题， 用到了大数的乘法(平方)和除法,难度不大,留作模板;
? ? 但这儿有一个小技巧,可以先平方,再除4,简化大数运算步骤.
代码:
#include <stdio.h>
#include <string.h>
#define N 100000
int main()
{
char a[N],re[N];
memset(re,sizeof(re));
scanf("%s",a); // 大数输入
int i,j,len = strlen(a),bz = 0,mx = 0;
int jw = 0,t,st = 0,nw = 0;
for(i = 0; i < len; i ++) a[i] -= '0';
for(i = len - 1; i >= 0; i --){ // 计算 re = a ^ 2
for(j = len - 1; j >= 0; j --){
jw += (a[i] * a[j] + re[nw]);
re[nw ++] = jw % 10;
jw /= 10;
}
while(jw){
re[nw ++] = jw % 10;
jw /= 10;
}
st ++;
if(nw > mx) mx = nw;
nw = st;
}
while(jw){
re[mx ++] = jw % 10;
jw /= 10;
}
jw = 0;
for(i = mx - 1; i >= 0; i --){ // 计算 re / 4
t = jw * 10 + re[i];
jw = t % 4;
re[i] = t / 4;
}
while(!re[--mx]) ; // 消除大数前边的0
for(i = mx; i >= 0; i --) printf("%c",re[i] + '0');
printf("n");
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |