P3988 [SHOI2013]发牌
2024-08-28 11:00:33
题目
做法
我们切牌时的状态:
手玩几次后我们发现切\(K\)次牌就是求堆顶一下的\(K+1\)大值,套上主席树就好了
My complete code
#include<cstdio>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL maxn=2000000;
inline LL Read(){
LL x(0),f(1);char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
LL n,m,top,nod,root;
struct Tree{
LL son[2],sum;
}T[maxn];
inline void Build(LL &now,LL l,LL r){
now=++nod;
T[now].sum=r-l+1;
if(l==r)
return;
LL mid(l+r>>1);
Build(T[now].son[0],l,mid);
Build(T[now].son[1],mid+1,r);
}
inline LL Query(LL now,LL l,LL r,LL K){
--T[now].sum;
if(l==r)
return l;
LL mid(l+r>>1);
if(T[T[now].son[0]].sum>=K)
return Query(T[now].son[0],l,mid,K);
else
return Query(T[now].son[1],mid+1,r,K-T[T[now].son[0]].sum);
}
int main(){
m=n=Read(),
Build(root,1,n),
top=1;
while(m--){
LL r(Read());
top=(top+r)%(m+1);
if(top==0) top=(m+1);
LL now(Query(root,1,n,top));
printf("%lld\n",now);
}
}/*
*/
最新文章
- UEFI+GPT引导实践篇(一):切换到UEFI启动,准备安装介质
- 基础01 dos命令
- CE5 中断
- 关于帝国cms 列表页SEO优化的问题
- NYOJ 540
- CentOS6-釋放ip重新分配,centos7 ifconifg没有ip
- C# 通过豆瓣网络编程API获取图书信息
- Linux内核分析(四)----进程管理|网络子系统|虚拟文件系统|驱动简介
- css3制作导航栏
- PHP的数组值传入JavaScript的数组里
- (转)log4j(二)——如何控制日志信息的输出?
- Spring AOP中 args和arg-names的区别
- Volley的基本使用
- Java7 和 Java8 中的 ConcurrentHashMap 原理解析
- 浮点型和BigDecimal的使用
- CSS的基本语法
- shell编程第二天
- python字典操作和内置方法
- ES6封装原生ajax请求
- C#里面获取web和非web项目路径
热门文章
- Eclipse配色利器
- hdu 1398 Square Coins 分钱币问题
- [译]GLUT教程 - 移动镜头2
- member access within misaligned address 0x000000000031 for type &#39;struct ListNode&#39;, which requires 8 byte alignment
- COM线程模型 套间概念
- DFS应用——查找强分支
- 解决ubuntukylin下各种终端字母重叠的方案
- 谷歌浏览器console.log()失效,打印不出来内容
- ubuntu study
- mysql 不同库不同表字段数据复制