本文参考自: 原文地址
题目链接：贪玩难约,一个你没有做过的船新算法题
题目描述
一共有 n个数，第 i 个数是 x
i
x
i 可以取 [l
i , r
i] 中任意的一个值。
设 ，求 S 种类数。
输入描述:
第一行一个数 n。 然后 n 行，每行两个数表示 li,ri。
输出描述:
输出一行一个数表示答案。
示例1
输入
5 1 2 2 3 3 4 4 5 5 6
输出
26
备注:
1 ≤ n , li , ri ≤ 100
题意：这个题意很好懂，就是在那些区间里面选出xi，求 Σ xi^2 的种类数
题解：
数据范围较小，100 个数都是100 ，最大也只不会超过 1e6
可以用 1e6 个每个01来模拟，
具体方法就是, 第 i 号位置代表数字 i
然后一个数 + A ,就是左移 A 位,最后统计 1 的个数就是答案
那这个题可以利用一个 bitset 来做
首先要知道 bitset 就是一个固定长度的 vector<bool>，自带很多函数
所以对于 01 来模拟比较方便
细节见代码：
#include<bits/stdc++.h>using namespace std;
const int inf = 0x3f3f3f3f;
const int M =1e6 + 50;#define mst(a,b) memset(a,b,sizeof(a))
#define rush() int T;cin>>T;while(T--)bitset<M> ans,t;
int main() {int n,l,r;scanf("%d",&n);ans[0] = 1;for(int i=0;i<n;i++) { // 对于每个区间 scanf("%d %d",&l,&r);for(int j=l;j<=r;j++) { // 对于某个可能的 xi t |= ans<<(j*j);// ans 是一个 01 串,如果某一位为 1,表示那一位可能被取到 } // ans << j*j , 表示 ans(原来某些位可能的情况) // + xi(区间内某一个值) 所产生的新情况// t 每次 | ans,就统计了这个区间对于原来 ans 贡献的所有情况 ans = t; // 然后更新 ans,重置 t,重复完所有区间 t.reset();} cout<<ans.count(); // 最后情况上只要某一位是 1 ,说明该情况可取 ，count()统计所有 1
}