注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1978][BeiJing2010]取数游戏 game  

2014-12-25 11:37:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1978: [BeiJing2010]取数游戏 game

颓成屎了……一个周末把海猫的动漫看完,然后又和各种神犇一起打cs....
最蛋疼的是TM我颓废都会被虐

终于找到自己能做出来的题了……
仔细想想还是蛮水
题解在代码下方

#include<cstdio>
#include<cstdlib>
using namespace std;
const int N = 5e4+100;
const int M = 1E6+100;
int n,m,list[N],num[N];
int scan(){int i=0;scanf("%d",&i);return i;}
int f[M],la[M],pri[M];
short v[M];
typedef long long ll;
void pre(){
int n=1e6,i,j;
for(i=2;i<=n;i++){
if(!v[i]){
pri[++pri[0]] = i;
la[i] = i;
}
for(j=1;j<=pri[0]&&(ll)pri[j]*i<=n;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0){
la[i*pri[j]] = la[i];
break;
}else{
la[i*pri[j]] = pri[j];
}
}
}
}
void get(int x){
list[0]=0;
while(x>1){
if(list[0] == 0 || list[list[0]] != la[x]){
list[++list[0]] = la[x];
num[list[0]] = 1;
}else num[list[0]]++;
x/=la[x];
}
}
int best;
void dfs(short t=0,int x=1,int now=1){
if(x>list[0]){
//printf("[%d]",now);
if(now < m)return;
if(!t){
if(f[now] > best)best = f[now];
}else{
if(best > f[now])f[now] = best;
}
return;
}
int tmp=1;
for(int i=0;i<=num[x];i++){
dfs(t,x+1,now*tmp);
tmp*=list[x];
}
}
int main(){
int i,j,a,b;
pre();
n = scan(); m = scan();
int ans=0;
/*
get(24);
for(i=1;i<=list[0];i++){
printf("%d %d\n",list[i],num[i]);
}
dfs(2); return 0;*/
for(i=1;i<=n;i++){
//printf("[%d]",i);
a = scan();
get(a);
best=0;
dfs(0);
best++;
dfs(1);
if(best>ans)ans=best;
}
//printf("%d\n",f[24]);
printf("%d\n",ans);
return 0;
}

题解:
DP。
因为是gcd比较蛋疼,不满足什么单调性没法二分或者是用数据结构维护啥的……
但是注意到数据范围:ai≤1e6
所以通过枚举ai的所有约数来转移答案。
然后可以知道每个数的约数个数非常少所以不会T
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017