模拟赛一 题解与分析

发布于 2019-04-05  13 次阅读


这是一篇咕咕咕咕了一点时间的分析。
该文章有关校内模拟赛,是关于模拟赛的题目及变式。
Problem 1
题面:

定义阶乘:n!=1,2…*n 给定n,求n!末尾的0的个数。 例如:当n=10,n!=3628800,末尾0的个数为2。

分析:
递归可解。当你给定的数<5时不可能出现0(要不然你就自己试试),当n>=5的时候就直接递归解就完事了。
Code:

#include <iostream>
#define LL long long
using namespace std;
LL m;
int qwq(int n){
    if (n<5){
        return 0;
    }
    else{
        return(n/5+qwq(n/5));
    }
}
int main(){
    cin>>m;
    cout<<qwq(m)<<endl;
    return 0;
}

变式:

定义阶乘:n!=1,2…*n 给定n,求n!在b进制下末尾的0的个数。

Problem 1
题面:

为了响应学校的号召,模范好学生王队长决定晨跑。不过由于种种原因,每天都早起去跑步不太现实,所以王队长决定每a天晨跑一次。换句话说,假如王队长某天早起去跑了步,之后他会休息a-1天,然后第a天继续去晨跑,并以此类推。 王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞,并决定自己也要坚持晨跑。小钦决定每b天早起跑步一次,而小针决定每c天早起跑步一次。 某天早晨,王队长、小钦和小针在早起跑步时相遇了,他们非常激动、相互鼓励,共同完成了一次完美的晨跑。 为了表述方便,我们把三位同学相遇的这天记为第0天,他们想知道,下一次三人在跑步时相遇是第几天。由于三位同学都不会算,所以希望由你来告诉他们答案。

分析:
很早的原题,详见洛谷P4057 晨跑,在旧博客上有详解。
Code:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

long long gcd(long long a,long long b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

long long lcm(long long a,long long b){
    return a*b/gcd(a,b);
}

int main(){
    long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    cout<<lcm(lcm(a,b),c);
    return 0;
}

Problem 2
题面:

给出一个n*n的网格,有一些格子是障碍,再给出一对起点终点,求从起点到终点需要的最小步数,每次可以从一个格子走到上下左右4相邻的四个格子里。

分析:
BFS板子题。
Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#define LL long long 
#define maxn 1001
using namespace std;
int n,a[maxn][maxn],sx,sy,tx,ty,dx[]={0,0,1,-1},dy[]={1,-1,0,0},s[maxn][maxn];
queue<int> q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    cin>>sx>>sy>>tx>>ty;
    q.push(sx);
    q.push(sy);
    while(!q.empty()){
        int xx=q.front();
        q.pop();
        int yy=q.front();
        q.pop();
        if(xx==tx&&yy==ty){
            cout<<s[xx][yy]<<endl;
            return 0;
        }
        for(int i=0;i<4;i++){
            int qx=xx+dx[i];
            int qy=yy+dy[i];
            if(qx<=n&&qy<=n&&qx>=1&&qy>=1&&a[qx][qy]==0){
                s[qx][qy]=s[xx][yy]+1;
                a[qx][qy]=1;
                q.push(qx);
                q.push(qy);
            }
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

变式:用图论算法解决这个题。


一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。