感受
苦苦针扎，一直想不到题目有什么暗示优化的地方。
做着做着把题目当成 来做，然后用树状数组优化，好不容易搞出了一个3e8的复杂度，准备测试样例时，卧槽，这求的和我做的不一样。
索性放弃了，看完题解，感叹bitset优化这么牛吗？整体移动可以达到,n是Bitset容器大小
知道bitset的优秀复杂度，就可以直接愉快地状态转移了。
bitset<100> bit; bit << 5 相当于原来状态的值 + 5
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
bitset<maxn> ans(1), tmp;
int n;
int main(){
scanf("%d", &n); int l, r;
for(int i = 1; i <= n; i++){
scanf("%d%d", &l, &r);
tmp.reset();
for(int j = l; j <= r; j++){
tmp |= (ans << (j * j));
}
ans = tmp;
}
cout << ans.count() << endl;
return 0;
}
/*
bitset<10> bs1;
cout << bs1 << endl;///每一位都是 false
bitset<10> bs2(5);
cout << bs2 << endl;/// 设为 val 的二进制形式。
bitset<10> bs3("101");
cout << bs3 << endl;///设为 串 str
cout << (bs2 == bs1) << endl;
cout << (bs2 != bs1) << endl;/// 比较两个 bitset 内容是否完全一样
cout << bs2[3] << endl;///访问其特定的一位。
///&/&=/|/| =/^/^=/~ 操作符只能针对bitset之间
///count() : 返回 true 的数量。
///size() : 返回 bitset 的大小。
///test(pos) : 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
///any() : 若存在某一位是 true 则返回 true ，否则返回 false 。
///none() : 若所有位都是 false 则返回 true ，否则返回 false 。
///all() : C++11 ，若所有位都是 true 则返回 true ，否则返回 false 。
///set() : 将整个 bitset 设置成 true 。
///set(pos, val = true) : 将某一位设置成 true / false 。
///reset() : 将整个 bitset 设置成 false 。
///reset(pos) : 将某一位设置成 false 。相当于 set(pos, false) 。
///flip() : 翻转每一位。（ 0 - 1 ，相当于异或一个全是 1的 bitset ）
///flip(pos) : 翻转某一位。
///to_string() : 返回转换成的字符串表达。
///to_ulong() : 返回转换成的 unsigned long 表达 ( long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。
///to_ullong() : C++11 ，返回转换成的 unsigned long long 表达。
*/
京公网安备 11010502036488号