lost cows
2020-02-12 16:00:45来源:博客园 阅读 ()
lost cows
这道题用树状数组做比较好,虽然树状数组能做的线段树也可以做到,但是树状数组更简洁方便,易操作
原理便是第x个数的二进制数最后一个“1”,决定tree的结点的长度
比如:
sum[3]=tree[3]+tree[2];
sum[4]=tree[4];
sum[5]=tree[5]+tree[4];
分割是位运算里的操作,一个数和它负数的补码(取反+1)用x&-x求得二进制数中为“1”的最小位
代码如下:
#include <iostream>
#include <cstdio>
#define lowbit(x) ((x)&-(x))
using namespace std;
const int MAX=10000;
int n;
int tree[MAX],pre[MAX],ans[MAX];
void add(int x,int d){//给x加d
while(x<=n){
tree[x]+=d;
x+=lowbit(x);
}
}
int sum(int x){
int ans=0;
while(x){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int findpos(int x){
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if(sum(mid)<x){
l=mid+1;
}
else{
r=mid;
}
}
return l;
}
int main()
{
scanf("%d",&n);
pre[1]=0;
for(int i=2;i<=n;i++){
scanf("%d",&pre[i]);
}
for(int i=1;i<=n;i++){//初始化不需要add()
tree[i]=lowbit(i);
}
for(int i=n;i>0;i--){
int x=findpos(pre[i]+1);
add(x,-1);
ans[i]=x;
}
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
return 0;
}
原文链接:https://www.cnblogs.com/sos3210/p/12298452.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P2858 [USACO06FEB]奶牛零食Treats for the Cows 2018-06-17
- P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows 2018-06-17
- 05:Cave Cows 1 洞穴里的牛之一 2018-06-17
- P2742 [USACO5.1]圈奶牛Fencing the Cows 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash