UVA 11525 Permutation ——(线段树,脑筋急转弯)
2024-09-05 05:48:03
只要注意到对于譬如:S1*(k-1)! 因为后面k-1个数字的全排列个数刚好是(k-1)!,那么第一个数字就是没有取过的数字的第(S1+1)个即可。取走这个数字以后这个数字就不能再用了,依次类推即可得到整个排列了。
那么随便用线段树维护一下即可。
代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define t_mid (l+r>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
const int N = 5e4 + ; int c[N<<];
void up(int o) {c[o] = c[ls] + c[rs];}
int query(int o,int l,int r,int sum)
{
if(l == r && sum == )
{
return l;
}
if(sum <= c[ls]) return query(lson,sum);
else return query(rson,sum - c[ls]);
}
void update(int o,int l,int r,int pos,int f)
{
if(l == r)
{
c[o] = f;
return ;
}
if(pos <= t_mid) update(lson,pos,f);
else update(rson,pos,f);
up(o);
}
void build(int o,int l,int r)
{
if(l == r)
{
c[o] = ;
return ;
}
build(lson);
build(rson);
up(o);
} int T,n; int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
build(,,n);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
int t = query(,,n,x+);
printf("%d%c",t,i==n?'\n':' ');
update(,,n,t,);
}
}
return ;
}
最新文章
- [转]浅谈CSRF攻击方式
- POJ 3468 A Simple Problem with Integers(线段树 成段增减+区间求和)
- Android IOS WebRTC 音视频开发总结(八十二)-- VP8对VP9,质量还是码率?
- DISK 100% BUSY,谁造成的?
- 2013级软件工程GitHub账号信息
- js响应HTML客户端下拉列表的修改事件
- 设计模式:迭代器模式(Iterator)
- Jenkins构建Android项目持续集成之findbugs的使用
- Android开发——Fragment的简单使用总结
- 安卓自定义日期控件(仿QQ,IOS7)
- 小白的python之路10/30磁盘分区
- 转:MVC,MVP 和 MVVM 的图示
- entity framework core 2.0 &; sqlite 配置教程
- 移动端网页 rem css书写
- 859. Buddy Strings
- hdwiki 部署
- Bootstrap-Other:CSS编码规范
- 【MySQL安装】MySQL5.6在centos6.4上的安装
- Linux网卡命名enp3s0说明
- vue路由使用