Project Euler 16~20

16

#include<bits/stdc++.h>
using namespace std;

const int ten[4]={1,10,100,1000};//辅助压位 压四位 这样乘法不会超int
const int maxl=1000; //最大位数

struct BigNumber{
    int d[maxl];//每4位压位 d[0]为压位后的位数 d[1]为原先的最低四位
    BigNumber (string s){
        int len=s.size();
        d[0]=(len-1)/4+1;
        int i,j,k;
        for(i=1;i<maxl;++i) d[i]=0;
        for(i=len-1;i>=0;--i){
            j=(len-i-1)/4+1;
            k=(len-i-1)%4;
            d[j]+=ten[k]*(s[i]-'0');
        }
        while(d[0]>1 && d[d[0]]==0) --d[0];//去除前导零
    }
    BigNumber(){
        *this=BigNumber(string("0"));
    }
    string toString(){
        string s("");
        int i,j,temp;
        //先处理高1位
        for(i=3;i>=1;--i) if(d[d[0]]>=ten[i]) break;
        temp=d[d[0]];
        for(j=i;j>=0;--j){
            s=s+(char)(temp/ten[j]+'0');
            temp%=ten[j];
        }
        //再处理剩下的位
        for(i=d[0]-1;i>0;--i){
            temp=d[i];
            for(j=3;j>=0;--j){
                s=s+(char)(temp/ten[j]+'0');
                temp%=ten[j];
            }
        }
        return s;
    }
}zero("0"),d,mid1[15];//d为作除法时的余数(可看做是高精度模高精度) mid1辅助作除法


bool operator <(const BigNumber &a,const BigNumber &b){
    if(a.d[0]!=b.d[0]) return a.d[0]<b.d[0];
    int i;
    for(i=a.d[0];i>0;--i) if(a.d[i]!=b.d[i]) return a.d[i] < b.d[i];
    return false;
}

//一定没有前导零
BigNumber operator +(const BigNumber &a,const BigNumber &b){
    BigNumber c;
    c.d[0]=max(a.d[0],b.d[0]);
    int i,x=0;
    for(i=1;i<=c.d[0];++i){
        x=a.d[i]+b.d[i]+x;
        c.d[i]=x%10000;
        x/=10000;
    }
    while(x!=0)
    {
        c.d[++c.d[0]]=x%10000;
        x/=10000;
    }
    return c;
}

BigNumber operator - (const BigNumber &a,const BigNumber &b){
    BigNumber c;
    c.d[0]=a.d[0];
    int i,x=0;
    for(i=1;i<=c.d[0];++i){
        x=10000+a.d[i]-b.d[i]+x;
        c.d[i]=x%10000;
        x=x/10000-1;
    }
    while((c.d[0]>1)&&(c.d[c.d[0]]==0)) --c.d[0];
    return c;
}

BigNumber operator *(const BigNumber &a,const int &k){//乘以较小数
    BigNumber c;
    c.d[0]=a.d[0];
    int i,x=0;
    for(i=1;i<=a.d[0];++i){
        x=a.d[i]*k+x;
        c.d[i]=x%10000;
        x/=10000;
    }
    while(x>0)
    {
        c.d[++c.d[0]]=x%10000;
        x/=10000;
    }
    while((c.d[0]>1) && (c.d[c.d[0]]==0) ) --c.d[0];
    return c;
}

int main()
{
    BigNumber ans("1");
    for(int i=1;i<=1000;++i){
        ans=ans*2;
    }
//    cout<<ans.toString()<<endl;
    int sum=0;
    string tp=ans.toString();
    for(int i=0;i<tp.size();++i){
        sum+=tp[i]-'0';
    }
    cout<<sum<<endl;
    return 0;
}

17

#include<bits/stdc++.h>
using namespace std;

vector<string> ans;

string dir[11]=
{
    "",
    "one",
    "two",
    "three",
    "four",
    "five",
    "six",
    "seven",
    "eight",
    "nine",
    "ten"
};

string dir1[11]=
{
    "",
    "eleven",
    "twelve",
    "thirteen",
    "fourteen",
    "fifteen",
    "sixteen",
    "seventeen",
    "eighteen",
    "nineteen"
};

string dir2[11]=
{
    "",
    "",
    "twenty",
    "thirty",
    "forty",
    "fifty",
    "sixty",
    "seventy",
    "eighty",
    "ninety",
    "hundred"
};

void fun(int n)//将n转为英文表示(n<=100)
{
    if(n<=10)
    {
        ans.push_back(dir[n]);
        return ;
    }
    if(n<20)
    {
        ans.push_back(dir1[n-10]);
        return ;
    }
    if(n<100){
        if(n%10==0){
            ans.push_back(dir2[n/10]);
            return ;
        }
        else{
            ans.push_back(dir2[n/10]+"-"+dir[n%10]);
            return ;
        }
    }
    if(n==1000){
        ans.push_back("one thousand");
        return ;
    }
    if(n%100==0){
        ans.push_back(dir[n/100]+" hundred");
        return ;
    }
    string tp;
    int tmp;
    tmp=n%100;
    if(tmp<=10){
        tp=dir[tmp];
    }
    else if(tmp<20){
        tp=dir1[tmp-10];
    }
    else if(tmp<100){
        if(n%10==0){
            tp=dir2[tmp/10];
        }
        else{
            tp=dir2[tmp/10]+"-"+dir[tmp%10];
        }
    }
    ans.push_back(dir[n/100]+" hundred and "+tp);
}

int main()
{
    for(int i=1;i<=1000;++i){
        fun(i);
    }
//    for(int i=0;i<11;++i)
//        cout<<dir[i]<<endl;
    int sum=0;
    for(int i=0;i<ans.size();++i){
        cout<<ans[i]<<endl;
        for(int j=0;j<ans[i].size();++j){
            if(ans[i][j]!=' '&&ans[i][j]!='-'){
                sum++;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

18

#include<bits/stdc++.h>
using namespace std;

const int maxn=200;

int mapp[maxn][maxn];

int dp[maxn][maxn];

int dfs(int i,int j)
{
    if(i==0||j==0) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    return dp[i][j]=max(dfs(i-1,j-1),dfs(i-1,j))+mapp[i][j];
}

int main()
{
    freopen("in.txt","r",stdin);
    int row;
    row=15;
    for(int i=1;i<=row;++i){
        for(int j=1;j<=i;++j){
            cin>>mapp[i][j];
            //cout<<mapp[i][j]<<' ';
        }
        //cout<<endl;
    }
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=row;++i){
        dp[row][i]=dfs(row,i);
    }
    int maxx=-1;
    for(int i=1;i<=row;++i){
        maxx=max(maxx,dp[row][i]);
    }
    cout<<maxx<<endl;
    return 0;
}

another solution

#include<bits/stdc++.h>
using namespace std;

const int maxn=200;

int mapp[maxn][maxn];

int main()
{
    freopen("in.txt","r",stdin);
    int row;
    row=100;
    memset(mapp,-0x3f,sizeof(mapp));
    for(int i=1;i<=row;++i){
        for(int j=1;j<=i;++j){
            cin>>mapp[i][j];
            //cout<<mapp[i][j]<<' ';
        }
        //cout<<endl;
    }
    for(int i=row;i>1;--i){
        for(int j=i;j>=1;--j){
            mapp[i-1][j-1]+=max(mapp[i][j],mapp[i][j-1]);
        }
    }
    cout<<mapp[1][1]<<endl;
    return 0;
}

all is $O(n^2)$

19

#include<bits/stdc++.h>
using namespace std;

bool run(int y)
{
    if(y%4!=0 || (y%100==0&&y%400!=0)) return false;
    return true;
}

int dir[2][15]={{0,31,28,31,30,31,30,31,31,30,31,30,31}
,{0,31,29,31,30,31,30,31,31,30,31,30,31}};

int main()
{
    //freopen("in.txt","r",stdin);
    //due to 1900 is not leap year so it has 365 days
    //means
    int d;//1.1 .1901 what day?
    d=(1+365%7)%7;
    //cout<<d<<endl;
    int ans= d==0? 1:0 ;
    for(int i=1901;i<=2000;++i){
        for(int j=1;j<=12;++j){
            d=(d+(dir[run(i)][j])%7)%7;
            if(i==2000&&j==12 ) continue;
            if(d==0) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

20

#include<bits/stdc++.h>
using namespace std;

const int ten[4]={1,10,100,1000};//辅助压位 压四位 这样乘法不会超int
const int maxl=1000; //最大位数

struct BigNumber{
    int d[maxl];//每4位压位 d[0]为压位后的位数 d[1]为原先的最低四位
    BigNumber (string s){
        int len=s.size();
        d[0]=(len-1)/4+1;
        int i,j,k;
        for(i=1;i<maxl;++i) d[i]=0;
        for(i=len-1;i>=0;--i){
            j=(len-i-1)/4+1;
            k=(len-i-1)%4;
            d[j]+=ten[k]*(s[i]-'0');
        }
        while(d[0]>1 && d[d[0]]==0) --d[0];//去除前导零
    }
    BigNumber(){
        *this=BigNumber(string("0"));
    }
    string toString(){
        string s("");
        int i,j,temp;
        //先处理高1位
        for(i=3;i>=1;--i) if(d[d[0]]>=ten[i]) break;
        temp=d[d[0]];
        for(j=i;j>=0;--j){
            s=s+(char)(temp/ten[j]+'0');
            temp%=ten[j];
        }
        //再处理剩下的位
        for(i=d[0]-1;i>0;--i){
            temp=d[i];
            for(j=3;j>=0;--j){
                s=s+(char)(temp/ten[j]+'0');
                temp%=ten[j];
            }
        }
        return s;
    }
}zero("0"),d,mid1[15];//d为作除法时的余数(可看做是高精度模高精度) mid1辅助作除法


bool operator <(const BigNumber &a,const BigNumber &b){
    if(a.d[0]!=b.d[0]) return a.d[0]<b.d[0];
    int i;
    for(i=a.d[0];i>0;--i) if(a.d[i]!=b.d[i]) return a.d[i] < b.d[i];
    return false;
}

//一定没有前导零
BigNumber operator +(const BigNumber &a,const BigNumber &b){
    BigNumber c;
    c.d[0]=max(a.d[0],b.d[0]);
    int i,x=0;
    for(i=1;i<=c.d[0];++i){
        x=a.d[i]+b.d[i]+x;
        c.d[i]=x%10000;
        x/=10000;
    }
    while(x!=0)
    {
        c.d[++c.d[0]]=x%10000;
        x/=10000;
    }
    return c;
}

BigNumber operator - (const BigNumber &a,const BigNumber &b){
    BigNumber c;
    c.d[0]=a.d[0];
    int i,x=0;
    for(i=1;i<=c.d[0];++i){
        x=10000+a.d[i]-b.d[i]+x;
        c.d[i]=x%10000;
        x=x/10000-1;
    }
    while((c.d[0]>1)&&(c.d[c.d[0]]==0)) --c.d[0];
    return c;
}

BigNumber operator *(const BigNumber &a,const int &k){//乘以较小数
    BigNumber c;
    c.d[0]=a.d[0];
    int i,x=0;
    for(i=1;i<=a.d[0];++i){
        x=a.d[i]*k+x;
        c.d[i]=x%10000;
        x/=10000;
    }
    while(x>0)
    {
        c.d[++c.d[0]]=x%10000;
        x/=10000;
    }
    while((c.d[0]>1) && (c.d[c.d[0]]==0) ) --c.d[0];
    return c;
}

int main()
{
    BigNumber ans("1");
    for(int i=1;i<=100;++i){
        ans=ans*i;
    }
//    cout<<ans.toString()<<endl;
    int sum=0;
    string tp=ans.toString();
    for(int i=0;i<tp.size();++i){
        sum+=tp[i]-'0';
    }
    cout<<sum<<endl;
    return 0;
}


上一篇:   project euler 21~25

下一篇:   Project Euler 11~15



评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)