【CF781D】Axel and Marston in Bitland

震惊!OIer们都转疯啦!这种神奇方法竟能凭空优化掉一个\(log\)!男OIer看了沉默,女OIer看了流泪!绝密档案!不学后悔一辈子!

这道题做法挺简单的。。就是倍增预处理

然而一算复杂度好像不大对呀。。\(n^3logn\)怎么过啊。。

王队比赛时AC了说:我有办法可以优化掉一个\(log\)

???这怎么优化呀

然后竟然是\(bitset\)。。赶紧来学习一个

 

\(bitset\)把一个长度为\(N\)的二进制串压成一个数进行各种位运算。具体实现应该是每若干位压成一个整数。

声明一个大小为\(N\)的\(bitset\):

bitset <N> a; 得到一个每位均为\(0\)的\(bitset\)。

bitset <N> a(val); 得到一个用\(val\)转为二进制数的每一位初始化的\(bitset\)。

bitset <N> a(str); 得到一个用字符串\(str\)每一位初始化的\(bitset\)。

逻辑运算符和位运算符可以直接使用,和整数的没有很大区别。

可以直接使用\([]\)访问\(bitset\)中的某一位。

a.count() 返回\(a\)中\(1\)的个数。

a.any() 相当于\((bool)a.count()\)。

a.none() 相当于\(!a.any()\)。

a.set(x) 将第\(x\)位设置为\(1\)。如果不指定\(x\)则将所有位设为\(1\)。

a.reset(x) 将第\(x\)位设置为\(0\)。如果不指定\(x\)则将所有位设为\(0\)。

a.to_string() 将\(a\)转为表示这个\(bitset\)的字符串。

a.to_ulong() 将\(a\)转为表示这个\(bitset\)的整数,类型为\(unsigned\ long\)。

a.to_ullong() 将\(a\)转为表示这个\(bitset\)的整数,类型为\(unsigned\ long\ long\)。

 

于是这道题还是挺水的。。

说点什么

1 评论 在 "【CF781D】Axel and Marston in Bitland"

提醒
排序:   最新 | 最旧 | 得票最多
成员

沙发&火钳刘明

wpDiscuz