NOIP2009普及组
阅读原文时间:2023年07月08日阅读:2

【算法】数论

【题解】均分的本质是A整除B,A整除B等价于A的质因数是B的子集

1.将m1分解质因数,即m1=p1^a1*p2^a2*…*pk^ak

所以M=m1^m2=p1^(a1*m2)*p2^(a2*m2)*…*pk^(ak*m2)

2.如果s[i](细胞初始个数)不能被M分解出来的质因数(即p1,p2…pn)中的某一个整除的话,这种细胞就永远不可能装入M个瓶子中

换句话说,如果s[i]分解出来的质因数不能包含M的所有质因数的话,就永远不能整除M(即使乘方(分裂)后)。

当然并不需要真的把s[i]分解为质因数,只要有一个s[i]%pj(j=1..k)!=0就说明是-1。

3.确定不是-1后,需要计算最小分裂时间。

当s[i]^ans中包含的每个pi的个数(假设为bi)比M中包含的pi的个数(即ai*m2)多时,就能被M整除。

所以就是找到最小的ans,使每个bi>=(ai*m2)(i=1…n)。

这个ans=ceil(a[i]*m2/b[i]) (只适用于a[i]*m2比b[i]大时)(ceil表示向上取整)

在所有s[i]中寻找最小的ans就是答案。

#include
#include
#include
#include
#include
//https://www.cnblogs.com/onioncyc/p/5766587.html
//其实是一个数论的题目,质因数分解
using namespace std;
const int maxm=30010,maxn=10010,inf=0x3f3f3f3f,eps=1e-6;
int pri[maxm],num[maxm],num2[maxm],s[maxn],tot=0,n,m,m2,ans;
int main(){
scanf("%d %d %d",&n,&m,&m2);
/*
将m1分解质因数,即m1=p1^a1*p2^a2*…*pk^ak
所以M=m1^m2=p1^(a1*m2)*p2^(a2*m2)*…*pk^(ak*m2)
*/
for(int i=2;i*i<=m;i++){
if(m%i==0){
pri[++tot]=i;
while(m%i==0){
m/=i;
num[tot]++;
}
}
}
if(m!=1) {
pri[++tot]=m;num[tot]=1;
}
for(int i=1;i<=tot;i++) num[i]*=m2;
ans=inf;
/*
如果s[i](细胞初始个数)不能被M分解出来的质因数(即p1,p2…pn)中的某一个整除的话,这种细胞就永远不可能装入M个瓶子中

换句话说,如果s[i]分解出来的质因数不能包含M的所有质因数的话,就永远不能整除M(即使乘方(分裂)后)。

当然并不需要真的把s[i]分解为质因数,只要有一个s[i]%pj(j=1..k)!=0就说明是-1。
*/
for(int i=1;i<=n;i++){ scanf("%d",&s[i]); bool f=0; memset(num2,0,sizeof(num2)); for(int j=1;j<=tot;j++){ if(s[i]%pri[j]!=0) f=1; } if(f) continue; /* 3.确定不是-1后,需要计算最小分裂时间。 当s[i]^ans中包含的每个pi的个数(假设为bi)比M中包含的pi的个数(即ai*m2)多时,就能被M整除。 所以就是找到最小的ans,使每个bi>=(ai*m2)(i=1…n)。
这个ans=ceil(a[i]*m2/b[i]) (只适用于a[i]*m2比b[i]大时)(ceil表示向上取整)
在所有s[i]中寻找最小的ans就是答案。
*/
for(int j=1;j<=tot;j++){ while(s[i]%pri[j]==0){ num2[j]++; s[i]/=pri[j]; //s[i]中包含pi的个数 } } int maxs=0; for(int j=1;j<=tot;j++){ if(num[j]>num2[j]){
//num[j]是a[i]*m2 num2[j]是b[i]
maxs=max(maxs,(int)(ceil(1.0*num[j]/num2[j])+eps));
}
}
ans=min(ans,maxs);
}
if(ans==inf) ans=-1;
printf("%d",ans);
return 0;
}

听起来比较复杂

但是看得出来数据范围不太大,可以试一试暴力,用二维数组存

其实有点像dp,用f[i]表示i这个时刻能够得到的最大值

最外层枚举时间,第二次枚举结尾的地方,第三层枚举走过的时间,就自然得出了出发的地方,在出发的地方买就能得到一个比较的值

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
int cost[maxn];
int value[maxn][maxn]; //地点对应时间出现的价值
int f[maxn]; //状态压缩至一维的,表示时间i能够取得的最大值,枚举到达结尾和走过的距离k,然后找到最大值
int n,m,p;
int main(){
scanf("%d %d %d",&n,&m,&p);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) scanf("%d",&value[i][j]);
}
for(int i=1;i<=n;i++) scanf("%d",&cost[i]);
memset(f,0x9f,sizeof(f));
f[0]=0;
for(int i=1;i<=m;i++){ //时间
for(int j=1;j<=n;j++){ //结尾的地点
int summ=0; //直接增加枚举从j走到d的值,不用数组存,也不用数组计算,不然太麻烦
for(int k=1;k<=p&&k<=i;k++){
int d=j-k;
if(d<=0) d=d%n+n;
summ+=value[d][i-k+1];
f[i]=max(f[i],f[i-k]+summ-cost[d]); //从d买,然后走k
}
}
}
printf("%d\n",f[m]);
return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章