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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3733][Pa2013]Iloczyn  

2014-10-10 00:01:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3733: [Pa2013]Iloczyn

看似是数学题……

但是有很明显的错误性质所以感觉可以暴力

然后懒得写……

结果今天还是写了

完全忘了一开始的想法所以T出翔

后来想起来了改完之后发现又WA又T一时爽……

改到放学终于只WA两个点

zky神犇:"贪心剪枝有没有可能是错的?"

我:"怎么可能,正确性显然啊。"

然后……就没有然后了

调了一下错误数据发现真的是错的。。

按照惯例题解在代码下方

我的代码好长啊……

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int N = 100+10;
int n,m,list[N],num[N],lin[5000];
map<int,bool>v;
bool ok;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
void get(int nn){
list[0] = 0;
num[0] = 0;
for(int i=2;(long long)i*i<=nn;i++)
if(nn%i ==0){
list[++list[0]] = i;
num[list[0]] = 0;
while(nn%i==0)num[list[0]]++,nn/=i;
num[0]+=num[list[0]];
}
if(nn > 1)list[++list[0]] = nn,num[list[0]] = 1,num[0]++;
}
int pow(int x,int k){
int re=1;
for(;k;x*=x,k/=2)
if(k&1)re*=x;
return re;
}
int last,lim,ans[N];
void dfs1(int y=1,int x=list[0],int now=1,int nown=0){
if(ok)return;//
if(num[0] < m-y)return;//*
if(nown > lim)return;
if(nown==lim)x=0;
if(!x){
if(now==1 || v[now])return;
int tmp,sl;
if(now < last)return;
if(y+1 == m){
tmp = 1;
v[now] = 1;//*
for(int i=1;i<=list[0];i++)
if(num[i])tmp*=pow(list[i],num[i]);
if(v[tmp]==0)
ok = 1;
v[now] = 0;
}else{
ans[y] = now;
tmp = last;
last = now;
v[now]=1;
dfs1(y+1);
sl = lim;
while(1){
lim++;
last = 0;
if(lim*(m - y) > num[0]) break;//这个很重要
else dfs1(y+1);
}
lim = sl;
v[now]=0;
last = tmp;
}
return;
}
int tmp = 1;
for(int i=0;i<=num[x];i++){
num[x]-=i;
num[0]-=i;
dfs1(y,x-1,now*tmp,nown+i);
tmp*=list[x];
num[0]+=i;
num[x]+=i;
}
}
int main(){
//freopen("ilo6.in","r",stdin);
int i,j;
int nn = scan();
lim=1;
//221184000 11 TAK
while(nn--){
n = scan();m = scan()-1;
//printf("%d %d\n",n,m);
if(n==1&&m>=n){printf("NIE\n");continue;}
if(m<=1){printf("TAK\n");continue;}
get(n);
ok = 0;
lin[0] = 0;
last = 0;
dfs1();
printf("%s\n",ok?"TAK":"NIE");
}
return 0;
}

题解:

暴力大法好。

首先对n分解质因数

然后每次从里面选出来一些因子

优化:

1.必然拆一个1出来,并且最后一个数直接可以得到不需要枚举。

2.因子从大到小循环,因子个数从少到多循环。

3.如果剩下的总因子个数少于剩下需要选的数就剪掉。

4.先选尽量少的因子个数,每个数设定一个上限lim,如果剩下的因子不够了就剪掉(这个很重要)

5.相同的因子个数设为”一层“的话,要求每一层的数是严格递增的(防止重复状态)

注意:

并不是能选因子数量尽量少的就选这样一定最优。

  评论这张
 
阅读(240)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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