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 DEBUGfreopen("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 DEBUGprintf("Time cost : %lf sn",(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 DEBUGfreopen("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 DEBUGprintf("Time cost : %lf sn",(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 DEBUGfreopen("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("%dn",a[r]-a[l-1]);}#ifdef DEBUGprintf("Time cost : %lf sn",(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 DEBUGfreopen("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 DEBUGprintf("Time cost : %lf sn",(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 DEBUGfreopen("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("%dn",ans);}#ifdef DEBUGprintf("Time cost : %lf sn",(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 DEBUGfreopen("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 DEBUGprintf("Time cost : %lf sn",(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 %dn",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 DEBUGfreopen("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 DEBUGprintf("Time cost : %lf sn",(double)clock()/CLOCKS_PER_SEC);
#endif//cout << "Hello world!" << endl;return 0;
}