约瑟夫环有 \(\mathcal O(n)\) 做法相信大家都知道。这里就不在介绍了,这里给出一个不知道这个结论的 \(\mathcal O(n\log n)\) 简单做法。
考虑直接模拟题意,每次循环往后数 \(k\) 个然后把这个数给删掉,如果采用链表的话找 \(k\) 个是要超时的,考虑换个数据结构比如平衡树,支持 \(\mathcal O(\log n)\) 求排名,插入或删除。于是就打了个平衡树上去。
#include<ext/pb_ds/assoc_container.hpp>
namespace pbds=__gnu_pbds;
pbds::tree<int,pbds::null_type,std::less<>,pbds::rb_tree_tag,pbds::tree_order_statistics_node_update>s;
int n,k;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++)s.insert(i);
for(int i=1;--n;){
i=(i+k-2)%(n+1)+1;
s.erase(s.find_by_order(i-1));
}
cout<<*s.begin();
return 0;
}
发现 pbds 的平衡树跑不过去,难道是太慢超时了?这该怎么办呢?众所周知基础平衡树的所有题都可以离线下来用树状数组去解决,那这里 find_by_order
这个操作就要用到树状数组上二分这个做法去实现。
代码:
constexpr int N=2e6+1;
int n,k;
struct{
int d[N];
void add(int x){for(;x<N;x+=x&-x)d[x]++;}
void del(int x){for(;x<N;x+=x&-x)d[x]--;}
int kth(int x){
int p=1<<std::__lg(N);
for(int i=std::__lg(N)-1;~i;i--)
if(d[p-(1<<i)]>=x)p-=(1<<i);
else x-=d[p-(1<<i)];
return p;
}
}s;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++)s.add(i);
for(int i=1;--n;){
i=(i+k-2)%(n+1)+1;
s.del(s.kth(i));
}
cout<<s.kth(1);
return 0;
}
这里简单介绍一下树状数组上二分这个算法:先把当前位置调整成整个数组总和的位置(也就是 1..0000
,这样才能保证 \([1,n]\) 都被 \(p\) 包含,为了方便,空间开两倍),从高位向低位考虑,如果左儿子比 \(k\) 大表示答案一定在左儿子,进入左儿子就行了,否则就在右儿子里面,把排名 \(k\) 减去左儿子的总和就行了。
CF1354D 这题也是采取树状数组去代替平衡树,也要用到树状数组上二分这个办法,可以去做一做。
原文地址:http://www.cnblogs.com/bxjz/p/P8671.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性