“华为杯”中国矿业大学程序设计学科竞赛

Problem A 细胞分裂

https://ac.nowcoder.com/acm/contest/948/A

题意：

题解：

C++版本一

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<int,int>
#define PCC pair<char,char>
#define PDD pair<double,double>
#define PSI pair<string,int>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e5+7;
const int INF=1e6,mod=1e9+7;
int n,m1,m2;
int a[N];
vector<int>p;
vector<PII>v;
int main()
{
    for(int i=2;i<=30000;i++){
        if(!a[i]){
            p.PB(i);
            for(int j=i*2;j<=30000;j+=i){
                a[j]=1;
            }
        }
 
    }
    cin>>n;
    cin>>m1>>m2;
    if(m1==1){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<p.size();i++){
        if(p[i]>m1)break;
        if(m1%p[i]==0){
            int cnt=0;
            while(m1%p[i]==0){
                cnt++;
                m1/=p[i];
            }
            v.PB(PII(p[i],cnt*m2));
        }
 
    }
    int ans=INF;
    int x;
    for(int i=1;i<=n;i++){
        int num=0;
        scanf("%d",&x);
        for(int j=0;j<v.size();j++){
            if(x%v[j].FI){
                num=INF;
                break;
            }
            int cnt=0;
            while(x%v[j].FI==0){
                cnt++;
                x/=v[j].FI;
            }
            num=max(num,v[j].SE/cnt+(v[j].SE%cnt!=0));
        }
        ans=min(ans,num);
    }
    if(ans==INF)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

Problem B A题

https://ac.nowcoder.com/acm/contest/948/B

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=1000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],b[N],vis[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)vis[i]=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&b[i]);
        queue<int>q;
        q.push(1);
        vis[1]=1;
        while(!q.empty()&&!vis[m]){
            int u=q.front();
            q.pop();
            if(a[u])for(int i=u+1;i<=n;i++)if(a[i]&&!vis[i])vis[i]=1,q.push(i);
            if(b[u])for(int i=1;i<u;i++)if(b[i]&&!vis[i])vis[i]=1,q.push(i);
        }
        cout<<(vis[m]?"YES":"NO")<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 均分糖果

https://ac.nowcoder.com/acm/contest/948/C

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    while(~scanf("%d",&n)){
        sum=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
        flag=sum/n;
        ans=0;
        temp=0;
        for(int i=1,j=n;i<=j;i++,j--){
            if(a[i]!=flag){
                ans++;
                a[i+1]+=a[i]-flag;
            }
            if(a[j]!=flag){
                ans++;
                a[j-1]+=a[j]-flag;
            }
        }
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D B题

https://ac.nowcoder.com/acm/contest/948/D

题意：

题解：

C++版本一

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<int,int>
#define PCC pair<char,char>
#define PDD pair<double,double>
#define PSI pair<string,int>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e5+7;
const int INF=1e6,mod=1e9+7;
int n;
vector<int>v[101];
int a[101][101];
int s[101];
int ans;
void dfs(int x,int y,int z){
    //cout<<x<<' '<<y<<endl;
    s[x]=1;
    if(z==n-1){
        ans=y+a[x][1];
        return;
    }
    if(s[v[x][0]]==0){
        dfs(v[x][0],y+a[x][v[x][0]],z+1);
    }
    else{
        dfs(v[x][1],y+a[x][v[x][1]],z+1);
    }
 
}
int main()
{
    while(cin>>n){
        memset(s,0,sizeof(s));
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)v[i].clear();
        int x,y,z;
        int ss=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&x,&y,&z);
            v[x].PB(y),v[y].PB(x);
            a[y][x]=z;
            ss+=z;
        }
        s[1]=1;
        if(a[1][v[1][0]]==0)dfs(v[1][0],0,1);
        else dfs(v[1][0],a[1][v[1][0]],1);
        //cout<<ss<<' '<<ans<<endl;
        cout<<min(ans,ss-ans)<<endl;
    }
    return 0;
}

Problem E 很简单的题。。。。。。

https://ac.nowcoder.com/acm/contest/948/E

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int check(int x){
    int res=0;
    while(x){
        res+=(x%10==2);
        x/=10;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    for(int i=1;i<=10000;i++)
        a[i]=a[i-1]+check(i);
    while(~scanf("%d%d",&l,&r)){
        printf("%d\n",a[r]-a[l-1]);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F 最大公约数和最小公倍数问题

https://ac.nowcoder.com/acm/contest/948/F

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int prime[N],pre[N],f[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    prime[0]=prime[1]=1;
    for(int i=2;i<N;i++){
        if(!prime[i]){
            pre[++cnt]=i;
            f[i]=1;
        }
        for(int j=1;j<=cnt&&i*pre[j]<N;j++){
            prime[i*pre[j]]=1;
            f[i*pre[j]]=f[i]+1;
            if(i%pre[j]==0){
                f[i*pre[j]]=f[i];
                break;
            }
        }
        //ans=max(ans,f[i]);
    }
    //cout<<ans<<endl;
    while(~scanf("%d%d",&n,&m)){
        cout<<(m%n?0:pow(2,f[m/n]))<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G 毕业生的纪念礼物

https://ac.nowcoder.com/acm/contest/948/G

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,num;
int a[N],b[3],c[N];
char str;
struct node{};
priority_queue<int> q;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+n+1);num=0;
        for(int i=1;i<=n;i++){
            if(a[i]!=a[i-1]) c[++num]=1;
            else c[num]++;
        }
        for(int i=1;i<=num;i++) q.push(c[i]);
        while(q.size()>=3){
            for(int i=0;i<3;i++){
                b[i]=q.top();q.pop();
            }
            ans++;
            for(int i=0;i<3;i++){
                if(--b[i])q.push(b[i]);
            }
        }
        printf("%d\n",ans);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem H 毕业生的序列游戏

https://ac.nowcoder.com/acm/contest/948/H

题意：

题解：

C++版本一

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<int,int>
#define PCC pair<char,char>
#define PDD pair<double,double>
#define PSI pair<string,int>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e5+7;
const int INF=1e6,mod=1e9+7;
LL k,a,b,s;
LL POW(LL x,LL y){
    LL re=1;
    while(y){
        if(y&1)re=re*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return re;
}
LL f[2002][2002];
int main()
{
    cin>>k>>a>>b;
    s=POW(a+b,mod-2);
    f[1][0]=1;
    LL ans=0;
    for(int i=1;i<=k;i++){
        for(int j=0;j<=k;j++){
            if(i+j>=k){
                ans=(ans+f[i][j]*(i+j+a*POW(b,mod-2)%mod)%mod)%mod;
            }
            else
            {
                f[i+1][j]=(f[i+1][j]+f[i][j]*a%mod*s%mod)%mod;
                f[i][j+i]=(f[i][j+i]+f[i][j]*b%mod*s%mod)%mod;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Problem I 你的粪坑v1

https://ac.nowcoder.com/acm/contest/948/I

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
string A,B,X1,X2;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        cin>>A>>X1;
        cin>>B>>X2;
        if(X1==X2){
            cout<<"yi qi chi shi."<<endl;
        }else if((X1=="jiandao"&&X2=="bu")||(X1=="shitou"&&X2=="jiandao")||(X1=="bu"&&X2=="shitou")){
            cout<<B<<" chishi."<<endl;
        }else{
            cout<<A<<" chishi."<<endl;
        }
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J 你的粪坑v2

https://ac.nowcoder.com/acm/contest/948/J

题意：

题解：

C++版本一

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define FI first
#define SE second
#define POP pop_back()
#define PII pair<LL,LL>
#define PCC pair<char,char>
#define PDD pair<double,double>
#define PSI pair<string,int>
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
#define m(x) a[x].l+a[x].r>>1
const int N=1e2+7;
const int INF=1e6,mod=1e9+7;
int n,m;
int a[101][101];
int s[101][101][22][2];
int ans;
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                for(int k=0;k<=20;k++)
                s[i][j][k][1]=s[i][j][k][0]=INF;
            }
        }
        s[1][1][0][0]=s[1][1][0][1]=a[1][1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==1&&j==1)continue;
                s[i][j][0][1]=s[i-1][j][0][1]+a[i][j];
                s[i][j][0][0]=s[i][j-1][0][0]+a[i][j];
                for(int k=1;k<=20;k++){
                    s[i][j][k][1]=min(s[i-1][j][k][1],s[i-1][j][k-1][0]+(1<<k-1))+a[i][j];
                    s[i][j][k][0]=min(s[i][j-1][k][0],s[i][j-1][k-1][1]+(1<<k-1))+a[i][j];
                    //printf("%d %d %d %d %d\n",i,j,k,s[i][j][k][0],s[i][j][k][1]);
                }
            }
        }
        int ans=INF;
        for(int i=0;i<=20;i++){
            ans=min(ans,min(s[n][n][i][0],s[n][n][i][1]));
        }
        cout<<ans<<endl;
    }
    return 0;
}

Problem K 你的Alice

https://ac.nowcoder.com/acm/contest/948/K

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld%lld",&n,&k);
    cout<<((n/k)&1?"YES":"NO")<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}