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})，但是因为是枚举质因数，所以根本不可能跑满\)
附上代码
点击查看代码
#include<bits/stdc++.h>
using 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]));
else
now=max(now,nd[j]/chai(x,q[j])+1);
}
if(now<ans&&flag==0)
{
ans=now;
wei=i;
}
}
if(wei>=0)
cout<<ans;
else
cout<<-1;
return 0;
}
再看到第四题
道路游戏
题目大意
\(有一个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<j,i<1\\
f_{n,j-1,k-1}+a_{i,k} & 1<j,i==1
\end{cases}
\)
\(但是如果开了这个数组，空间为nmk,肯定是会寄的，但是发现整个式子转移时只用到了k-1,所以可以把k这维滚动掉\)
\(再在每层循环时把max(f_{l,r,k-1})预处理一下，总复杂度O(nmk)，常数较小，可以AC\)
点击查看代码
#include<bits/stdc++.h>
using 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<<maxn;
return 0;
}