爱丽丝·玛格特罗依德

爱丽丝·玛格特罗依德"/>

爱丽丝·玛格特罗依德

题目描述
在幻想乡中，爱丽丝·玛格特罗依德是一名居住在魔法森林的魔法使，擅长召唤人偶。一天她的姬友帕秋莉找到了她，要他防御雾雨魔理沙对巴瓦卢魔法图书馆的“破坏”。
她有n点魔法值，每召唤出一个『上海人形』就要消耗若干点（x），最后，它们造成的威力就是每个人形所消耗的魔法值的总积。
她为了知道能有多少威力，找到了全幻想乡唯一会编程的你，你不会让她失望吧？

Rewrote From Izayoi Sakuya

输入
n

输出
最大威力

样例输入
10
样例输出
36

本题易错点：
1.时间超限：要运用多次幂快速求解
2.内存溢出：已存在的类型内存太小，要运用高精度

本题题解：
与已知周长求最大面积类似，可层层拆分，例如
10—>5*5
5—>2*3
到2*3之后便不能拆分

但2*2*2<3*3,所以本题就要找更多的3
3*1<2*2,所以当a/3=1，a/3要减1，让原来的数*4

参考代码

#include<stdio.h>
#include<string.h>
#include<math.h>void cons(int x,int a[],int b[]){//判断余几，然后确定将3^y-1乘完之后要成几if(x==0){a[0]=3;b[0]=3;}if(x==1){a[0]=4;b[0]=3;}if(x==2){a[0]=6;b[0]=3;}
}
void mul(int *a,int *b,int k1,int k2){//高精度*高精度int i,j,c[60000],x;memset(c,0,sizeof(c));for(j=0;j<k1;j++){x=0;for(i=0;i<k2;i++){c[j+i]=c[j+i]+x+a[j]*b[i];x=c[j+i]/10;c[j+i]=c[j+i]%10;}c[j+i]=x;}memcpy(a,c,60000*sizeof(int));
}int main(){int n,x,y,i,j,f,k,t,k1,k2;int b[60000],d[60000],a[1];memset(d,0,sizeof(d));memset(b,0,sizeof(b));d[0]=1;scanf("%d",&n);if (n==0) printf("%d",0);else if (n==1) printf("%d",1);else if(n==2)printf("%d",2);else{x=n%3;y=n/3;f=y-1;t=1;k1=k2=1;cons(x,a,b);while(f>1){//快速幂算法if(f&1==1){mul(d,b,k2,k1);if(d[k1+k2-1]!=0){k2=k1+k2;}else{k2=k1+k2-1;};//k2表示d[]数组表示的数的位数}mul(b,b,k1,k1);f=f/2;t=t*2;k1=(int)(t*log10(3.0)+1);//k2表示表示的3^t所表示的数的位数}mul(d,b,k2,k1);if(d[k1+k2-1]!=0){k2=k1+k2;}else{k2=k1+k2-1;};x=0;//最后在*3^y-1乘完之后要成要乘的数for(i=0;i<k2;i++){d[i]=x+d[i]*a[0];x=d[i]/10;d[i]=d[i]%10;}if(x!=0){d[i]=x;}else{i--;}for(i;i>=0;i--){printf("%d",d[i]);}}
}