文档章节

【codevs 2803】 爱丽丝·玛格特罗依德

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:58
字数 901
阅读 5
收藏 0

幸好这也是一张有图的题……

题目描述

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

输入描述

n

输出描述

最大威力

样例输入

10

样例输出

36

数据范围

n∈[0,1e5];

样例解释

10 = 2 + 2 + 3 + 3
2 * 2 * 3 * 3 = 36

小学奥数……?
多拆出3 要不就是2
听题解说是这样的
顺带一提,高精度

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int size=20010;
const int BASE=(int)1e9;
const int WIDTH=9;
typedef long long LL;
struct bign{
    int len,num[size];
    bign(){memset(num,0,sizeof(num)); len=1;}
    bign(LL x)
    {
        memset(num,0,sizeof(num)); len=0;
        do
        {
            num[++len]=x%BASE;
            x/=BASE;
        }while(x);
    }
};

void scanf(bign &ans)
{
    string in;
    cin>>in;
    int l=in.length();
    ans.len=(l-1)/WIDTH+1;
    for(int i=0;i<ans.len;i++)
    {
        int e=l-i*WIDTH;
        int s=max(0,e-WIDTH);
        sscanf(in.substr(s,e-s).c_str(),"%d",&ans.num[i+1]);
    }
}

void printf(const bign &ans)
{
    printf("%d",ans.num[ans.len]);
    for(int i=ans.len-1;i>=1;i--)
    {
        printf("%09d",ans.num[i]); 
    }
}

bool operator <(const bign &a,const bign &b)
{
    if(a.len!=b.len) return a.len<b.len;
    for(int i=a.len;i>=1;i--)
        if(a.num[i]!=b.num[i]) return a.num[i]<b.num[i];
    return false;
}

bool operator == (const bign &a,const bign &b)
{
    if(a.len != b.len)
        return false;
    for(int i = a.len;i >= 1;i --)
        if(a.num[i] != b.num[i])
            return false;
    return true;
}

bign operator +(const bign &a,const bign &b)
{
    bign ans;
    int i=1,x=0;
    while(i<=a.len||i<=b.len)
    {
        x=a.num[i]+b.num[i]+x;
        ans.num[i++]=x%BASE;
        x/=BASE;
    }
    ans.num[i]=x;
    ans.len=i;
    while(ans.len>1&&ans.num[ans.len]==0) ans.len--;
    return ans;
}

bign operator -(const bign &a,const bign &b)
{
    bign ans;
    ans.len=a.len;
    for(int i=1,x=0;i<=a.len;i++)
    {
        x=BASE+a.num[i]-b.num[i]+x;
        ans.num[i]=x%BASE;
        x=x/BASE-1;
    }
    while(ans.len>1&&ans.num[ans.len]==0) ans.len--;
    return ans;
}

bign operator *(const bign &a,const bign &b)
{
    bign ans;
    ans.len=a.len+b.len;
    for(int i=1;i<=a.len;i++)
    {
        LL x=0;
        for(int j=1;j<=b.len;j++)
        {
            x+=ans.num[i+j-1]+(LL)a.num[i]*(LL)b.num[j];
            ans.num[i+j-1]=x%BASE;
            x/=BASE;
        }
        ans.num[i+b.len]=x;
    }
    while(ans.len>1&&ans.num[ans.len]==0) ans.len--;
    return ans; 
}

bool smaller(const bign &a,const bign &b,int d)
{
    if(a.len+d!=b.len) return a.len+d<b.len;
    for(int i=a.len;i>=1;i--)
        if(a.num[i]!=b.num[i+d]) return a.num[i]<b.num[i+d];
    return true;
}

void jian(bign &a,const bign &b,int d)
{
    for(int i=1,x=0;i<=a.len-d;i++)
    {
        x=BASE+a.num[i+d]-b.num[i]+x;
        a.num[i+d]=x%BASE;
        x=x/BASE-1;
    }
    while(a.len>1&&a.num[a.len]==0) a.len--;
}

bign operator /(const bign &a,const bign &b)
{
    bign ans;
    ans.len=max(1,a.len-b.len+1);
    bign mid[32],num=a;
    mid[0]=b;
    for(int i=1;i<=30;i++) mid[i]=mid[i-1]*2;
    for(int i=a.len-b.len;i>=0;i--)
    {
        int tmp=1<<30;
        for(int j=30;j>=0;j--)
        {
            if(smaller(mid[j],num,i))
            {
                jian(num,mid[j],i);
                ans.num[i+1]+=tmp;
            }
            tmp>>=1;
        }
    }
    while(ans.len>1&&ans.num[ans.len]==0) ans.len--;
    return ans;     
}

bign operator %(const bign &a,const bign &b)
{
    bign ans;
    ans.len=max(1,a.len-b.len+1);
    bign mid[32],num=a;
    mid[0]=b;
    for(int i=1;i<=30;i++) mid[i]=mid[i-1]*2;
    for(int i=a.len-b.len;i>=0;i--)
    {
        int tmp=1<<30;
        for(int j=30;j>=0;j--)
        {
            if(smaller(mid[j],num,i))
            {
                jian(num,mid[j],i);
                ans.num[i+1]+=tmp;
            }
            tmp>>=1;
        }
    }
    return num;     
}
bign n;
bign four(4);
bign three(3);
bign two(2);
bign one(1);
bign zero(0);
bign ans(1);
void get(bign x)
{
    while(!(x == zero))
    {
        if(x == four)
        {
            x = x - four;
            ans = ans * four;
        }
        else if(x == two)
        {
            x = x - two;
            ans = ans * two;
        }
        else if(three < x || x == three)
        {
            x = x - three;
            ans = ans * three;
        }
        else if(n == one)
        {
            puts("1");
            exit(0);
        }
    }
}
int main()
{
    scanf(n);
    get(n);
    printf(ans);
    puts("");
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
2019奥斯卡谁是赢家 这里有一份来自AI的预测名单

网易智能(smartman163)编译 选自|Inverse 译者| Yuki 【网易智能讯 2月24日消息】近日,2019年奥斯卡金像奖共有八部影片获得最佳影片奖提名。 一家总部位于旧金山的科技公司在预测去年的奥...

网易智能
02/24
0
0
一周热门电影20170510

所有内容均由爬虫程序生成,对某方面有需求的同学可以留言或直接回复。 1. 银河护卫队2 Guardians of the Galaxy Vol. 2 (2017) 导演: 詹姆斯·古恩 主演: 克里斯·帕拉特 佐伊·索尔达娜 ...

u012175089
2017/05/10
0
0
百万级别二次元角色识别数据集 - 知乎

在上一篇专栏里,我们做了一个效果不错的动漫头像检测模型。这个模型本身并不复杂,但它可以帮助批量化处理数据,从而为更多彩的应用奠定基础。一个自然的问题就是,我们有没有可能做一个类似...

挖掘知乎里有趣的东西
10/21
0
0
达沃斯论坛第一天,马云带去的中国文化节目单火了

马不停蹄的马云老师,在第三届马云乡村教师奖现场,与100位中国乡村教师完成“重回课堂”的难忘一课后,转眼又现身瑞士达沃斯。 达沃斯论坛第一天,我们首先在国际货币基金组织总裁拉加德、卢...

阿里云云栖社区
2018/01/25
0
0
刚刚,阿里巴巴市值超5000亿美元!马云在达沃斯分享了什么

北京时间1月24日晚,阿里巴巴市值突破5000亿美元。盘中股价曾达198.86美元。 阿里巴巴市值超5000亿美元的时候,董事局主席马云正在达沃斯参加世界经济论坛。马云关心的,却似乎并不是阿里巴巴...

阿里云_云栖社区
2018/01/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

个人服务容器化和监控集成

1.前景 自己比较喜欢玩机器,目前手上有4台常用的机器 asw 1核1G 阿里云 1核2G 腾讯云 1核1G 百度云 2核4G

MrPei
8分钟前
2
0
Rancher源码编译

源码包准备 mkdir -p $GOPATH/src/github.com/ranchercd $GOPATH/src/github.com/ranchergit clone https://github.com/rancher/rancher.gitcd ranchergit checkout v2.2.3-rc9 注1......

深蓝苹果
12分钟前
3
0
7个理由,给你推荐这款“秒杀Excel”的分析神器!

谈到数据分析,自然离不开赖以使用的数据分析工具。 商业智能时代,可用于数据分析的工具有很多,Python、R......还有各式各样的专业工具。其中,Excel也是推荐的比较多的一种,尤其是刚入门...

朕想上头条
26分钟前
2
0
Spring5 源码分析-容器刷新-解析配置类-主流程

上一篇:Spring5 源码分析-容器刷新-invokeBeanFactoryPostProcessors()方法 此篇是上一篇方法中非常非常重要的功能,也是Spring核心功能,完成所有的BeanDefinition注册。 详细的主流程,如...

特拉仔
27分钟前
2
0
Python 3.8.0 正式发布 更新内容

Python是一种跨平台的计算机程序设计语言。是一种面向对象的动态类型语言,最初被设计用于编写自动化脚本(shell),随着版本的不断更新和语言新功能的添加,越来越多被用于独立的、大型项目的...

阮鹏
27分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部