最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

2009NOIP普及组 题解

来源：博客园


(相关资料图)

第一题第二题\(一二题太简单就不在此处提了\)\(直接看到\)第三题

细胞分裂

题目大意

\(有m1^{m2}个试管和n种细胞，第i种细胞初始有1个，每过1秒每一个会分裂成a_i个\)\(当有某种细胞可以平均分到试管中时开始实验，求开始实验的\)时间

\((顺便说一下，我一开始没看到是时间，以为是求哪一种细胞最先可以进行实验，可以过样例但是10分，调了好久，气死了)\)
数据范围

\(1\le n,m2\le 10000,1\le m1\le30000,1\le a_i\le 10^9\)\(当k个细胞能平均分到试管里时，显然有m1^{m2}|k\)\(用sumk_i表示k的质因数中含有sumk_i个第i个质数\)\(用summ_i表示m1^{m2}的质因数中含有summ_i个第i个质数\)\(如果对于每一个i,都有sumk_i\ge summ_i，则一定满足m1^{m2}|k\)\(因为此时k一定能表示成p\cdot m1^{m2}的形式,且p为大于等于1的整数\)\(所以可以先预处理出summ\)\(再对于每一个a_i求出一个最小的d使得{a_i}^d满足m1^{m2}|{a_i}^d\)\(根据前面的推理，可以得出d=max_{summ_i\ne0}(\frac{summ_i}{suma_i}向上取整)\)\(复杂度O(n\sqrt{m1})，但是因为是枚举质因数，所以根本不可能跑满\)附上代码

点击查看代码
#includeusing namespace std;int n,m1,m2;int zi[30009],q[2009],top,nd[2009];int chai(int x,int p){int now=0;while(x%p==0){now++;x/=p;}return now;}int main(){cin>>n>>m1>>m2;if(m1==1){cout<<0;return 0;}for(int i=2;i*i<=m1;i++){if(zi[i]==1)continue;for(int j=2;j*i<=m1;j++)zi[j*i]=1;}for(int i=2;i<=m1;i++){if(m1%i==0&&zi[i]==0){q[++top]=i;nd[top]=chai(m1,i)*m2;}}int wei=-1,ans=2100000000;for(int i=1;i<=n;i++){int x;cin>>x;int flag=0,now=0;for(int j=1;j<=top;j++)if(x%q[j]!=0){flag=1;break;}else{if(nd[j]%chai(x,q[j])==0)now=max(now,nd[j]/chai(x,q[j]));elsenow=max(now,nd[j]/chai(x,q[j])+1);}if(now=0)cout<

再看到第四题

道路游戏

题目大意

\(有一个n点的首尾相接的环，第i条边指连接第i个点和第i+1个点的边，特别的，第n条边指连接第n个点和第1个点的边\)\(第i条边在第j秒存在a_{i,j}个金币，每秒可以选择\)在任意一个点花费w_i购买一个机器人并删除原有的机器人或 保留原有的机器人\(接下来机器人会顺时针移动一步并获得走过的边上的金币，而且每个机器人最多走p步\)\(问m秒后最大收益是多少（收益指机器人捡到的金币减去买机器人花掉的金币）\)

数据范围

\(2\le n\le 1000,1\le m\le 1000,1\le p\le m\)\(用f_{i,j,k}表示第k秒最后一个机器人刚走完第i条边，此机器人总共走了j条边时最大收益\)\(f_{i,j,k}=\begin{cases}max(f_{l,r,k-1})+a_{i,k}-w{i} & j==1,此处为直接购买一个新机器人\\f_{i-1,j-1,k-1}+a_{i,k} & 1

点击查看代码
#includeusing namespace std;int f[1009][1009][2],n,m,p,maxn;int a[1009][1009],w[1009];int main(){cin>>n>>m>>p;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];}memset(f,-0x3f,sizeof(f));maxn=-1e9;for(int i=1;i<=n;i++){cin>>w[i];f[i][1][1]=a[i][1]-w[i];maxn=max(maxn,f[i][1][1]);}for(int k=2;k<=m;k++){int t=k&1;for(int i=1;i<=n;i++){int l=i-1;if(l==0)l=n;f[i][1][t]=maxn+a[i][k]-w[i];for(int j=2;j<=p;j++){f[i][j][t]=f[l][j-1][t^1]+a[i][k];}}maxn=-1e9;for(int i=1;i<=n;i++)for(int j=1;j<=p;j++)maxn=max(maxn,f[i][j][t]);}maxn=-1e9;for(int i=1;i<=n;i++)for(int j=1;j<=p;j++)maxn=max(maxn,f[i][j][m&1]);cout<

关键词：