暑期人生测试一总结

发布于 2018-12-06  798 次阅读

 

 

暑期测试一

数学作业

（homework.cpp）

【问题描述】

求：方程x1+2x2+„+nxn=m的所有非负整数解（x1,x2,„,xn）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、……、（0,0,0,0,1）。

 【输入数据】(homework.in)

2个整数n，m

【输出数据】(homework.out)

方程非负整数解的个数ans，如果解超过10^9，只需输出ansmod 10^9。

【输入样例】 55

【输出样例】 7

【数据范围】

1≤n≤5000；0≤m≤5000。

这道题可以将方程中的x1x2.....看作n个有价值的物品，要使这个方程刚好有解，则我们可以联想到完全背包问题中找方案类型的题目。抽象出来则可以描述为：有n件物品，重量依次为1到n，要将这些物品放入背包且刚好装满背包，求总方案数。接着粘上标准代码，AC；

注意！！！！！！每次状态转移后记得将求解的子问题答案Mod 10^9！！

否则变量爆掉！！

 

#include
#include
#include
using namespace std;
int n,m;
long long f[10000];
int main()
{
    freopen("homework.in","r",stdin);
    freopen("homework.out","w",stdout);
    scanf("%d%d",&n,&m);
    if(m==0){
        printf("1");
        return 0;
    }
            
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=m;j++)//分配i到m个空间 
            f[j]=(f[j]+f[j-i])%1000000000;     
    printf("%lld",f[m]);
    
    return 0;
}

魔法石的诱惑

（rob.cpp）

问题描述

修罗魔王远远地看见邪狼王狂奔而来，问道：“慌慌张张干什么？”

邪狼王大口大口初期：“我路过一家魔法石店，看到摆着那么多高阶魔法石，我就去抢了一大袋。”

修罗王怒道：“光天化日之下，朗朗乾坤，众目睽睽之下，你也敢抢？”

狼王：“我只看到了魔法石，没有看到人。。。”

修罗王：“。。。。。”

其实邪狼王的贪婪也很容易理解，因为高阶魔法石有一个特征，即它的重量进行阶乘运算后末尾有几个0，就拥有同等重量普通魔法石几倍的法力，例如5！=54321=120,所以120有一个0，这意味着该魔法石拥有同等重量的普通魔法石1倍的魔法力，你的任务是找到最小的自然数N，使N！在十进制下有Q个0结尾。

 

输入格式(rob.in)

一个数Q（0≤Q≤10^8）

输出格式(rob.out)

如果无解，输出”No solution”，否则输出N

输入样例

2

输出样例

10

二分枚举答案，同时算出该数的阶乘所包含的0的个数

如何算阶乘中0的个数：10由2*5组成，阶乘中2远远大于5，所以只用关注5的个数，注意25 125等数中包含多个5，需要另行判断

枚举答案后还获得最优解，要进行判断处理才得出最优解

 

#include
#include
#include
#include
using namespace std;
int Q;

int DuiShu(int n){//取以5为底，n的对数 
    int pre=1,nxt=5;
    for(int i=0;i<=20;i++){
        if(n>=pre&&nreturn i;
        pre*=5; nxt*=5;
    }
}

int calc(int n){//计算n的阶乘有多少个5
    int ds=DuiShu(n),sum=0;//取对数
    
    int pre=5,nxt=25;
    for(int i=1;i<=ds;i++){//每5^i个数产生一个0
        sum+=n/pre;
        pre*=5; nxt*=5;
    }
    return sum;
} 

int BinarySearch(int s,int e){//二分查找最佳答案 
    int mid,ans;
    while(s<=e){
        mid=(s+e)/2;
        ans=calc(mid);
        if(ans==Q)
            return mid;
        else if(ans>Q)//0多了 
            e=mid-1;
        else if(ans//0少了
            s=mid+1;
    }
    return -1;
}

int FindBest(int ans){
    if(ans%5!=0)//如果不是最优解
        ans=ans-(ans%5);
    return ans;
}

int main()
{
    freopen("rob.in","r",stdin);
    freopen("rob.out","w",stdout);
    scanf("%d",&Q);
    if(Q==0){
        printf("1");
        return 0;
    }
    int ans=BinarySearch(5,200000000);
    if(ans==-1)
        printf("No solution");
    else
        printf("%d",FindBest(ans));

//   printf("%d",DuiShu(30));//测试 
    
    return 0;
}