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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ4135][FJOI2015]世界树  

2015-06-17 22:51:54|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4135: [FJOI2015]世界树

感觉挺傻逼的题但是搞了好久= =、

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E4/2+10;
const int BIT = 1E8;
short rt[int(1e4+100)];
const short biao[20] = {0,0,0,0,1,1,0,1,1,1,1,1,2,2,2,2};
struct Num{
int d[N];
Num(int a=0){
if(!a){d[0]=1;d[1]=0;}
else{
d[0]=0;
for(;a;a/=BIT)d[++d[0]] = a%BIT;
}
}
void init(){
d[0] = 0;
int cot=0,tmp=0,len=0,ten=1;
char cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
while('0'<=cc&&cc<='9'){
rt[++len] = cc-'0';
cc=getchar();
}
for(int i=len;i;i--){
cot++;
tmp = tmp+ten*rt[i];
ten*=10;
if(cot == 8){
d[++d[0]] = tmp;
tmp=0;cot=0;ten=1;
}
}
if(tmp)d[++d[0]] = tmp;
if(!d[0]){d[0] = 1;d[1] = 0;}
}
void print(){
int i,j;
printf("%d",d[d[0]]);
for(i=d[0]-1;i;i--)
printf("%08d",d[i]);
printf("\n");
}
}t[3],d[51],*data[51];
Num operator + (const Num&a,const Num&b){
Num c;
c.d[0] = max(a.d[0],b.d[0])+1;
for(int i=1;i<=c.d[0];i++)c.d[i]=0;
for(int i=1;i<=c.d[0];i++){
if(i <= a.d[0])c.d[i] += a.d[i];
if(i <= b.d[0])c.d[i] += b.d[i];
if(c.d[i] >= BIT){
c.d[i+1] += c.d[i]/BIT;
c.d[i] %= BIT;
}
}
while(c.d[0] > 1 && !c.d[c.d[0]])c.d[0]--;
return c;
}
bool cmp(const Num *a,const Num *b){
if(a[0].d[0]!=b[0].d[0])return a[0].d[0] < b[0].d[0];
for(int i=a[0].d[0];i;i--)
if(a[0].d[i]!=b[0].d[i])
return a[0].d[i] < b[0].d[i];
return 1<1;
}
int n,ans[100];
int main(){
// freopen("in.txt","r",stdin);
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++){
d[i].init();
data[i] = &d[i];
}
sort(data,data+n,cmp);
Num *a,*b,*c;
a = &t[0];b = &t[1];c = &t[2];
a[0] = 0;
b[0] = 1;
j = 0;

for(;j<n && (data[j][0].d[0] == 1 && data[j][0].d[1]<=15);j++){
ans[data[j]-d] = biao[data[j][0].d[1]];
}
for(i=2;i;i++){
c[0] = a[0] + b[0] + Num(1);
for(;j<n && cmp(data[j],c);j++){
i--;
ans[data[j]-d] = i-(i/2+1);
i++;
}
// printf("[%d]",i);c[0].print();
swap(a,b);
swap(b,c);
if(j == n)break;
}
for(i=0;i<n;i++){
printf("%d\n",ans[i]);
}
return 0;
}

题解:
首先怎么考虑构造树
设f[i]表示最大深度为i的树构成至少需要多少节点,可以发现这棵树也是所有最大深度为i的树中最小深度最小的树
显然f[i] = f[i-2] + f[i-1] + 1
mindeep[i] = mindeep[i-2]+1
(对于i=0~2要手动输入
然后对于输入的点数x找到一个i使得f[i]≤x<f[i+1]
答案就是i-mindeep[i]
用python写一下发现i<1e5而且似乎暴力找出所有的f[i]不会T,但是会MLE
所以先把所有东西读进来排序,然后暴力计算f[i],每次判断最小的输入是否满足
然后交上去……wa了?
为什么呢……
原来在f[i]≤x<f[i+1]的x不一定满足mindeep和f[i]的时候一样,会逐渐递增
我们设l[i]为最多到f[i]+l[i]个点的时候还能满足“mindeep和f[i]的时候一样”
all[i]为深度为i的满二叉树的节点个数
l[i] = l[i-2] + (all[i-1] - f[i-1])
然后我们很高兴地发现大约在f[i]>15之后,就有f[i]+l[i]>f[i+1]。
所以x≤15打表,后面可以用一开始的方法搞
  评论这张
 
阅读(87)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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