牛客算法周周练5

链接：https://ac.nowcoder.com/acm/contest/5556/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

一共有 n个数，第 i 个数是 x_i

x_i 可以取 [l_i , r_i] 中任意的一个值。

设S=∑x_i²，求S的种类数。

输入描述:

第一行一个数 n。
然后 n 行，每行两个数表示 l_i,r_i。

输出描述:

输出一行一个数表示答案。

示例1

输入

输出

备注:

1 ≤ n , l_i, r_i ≤ 100

不了解bitset的先看看这个：

https://www.cnblogs.com/magisk/p/8809922.html

题解：

这题用bitset来优化动态规划

bitset其实就相当于我们平时使用的vis[]数组，bitset中的某一位是1就相当于vis[]=true

bitset数组ans表示最后所有结果的集合，为什么要用bitset呢？因为在bitset中可以使用异或、左移，可以方便快速的进行集合取并集，和数的相加，可以显著降低时间复杂度。

状态转移方程：temp |= ans<<(x*x)

注意：

bitset中每一位的下标和我们看二进制数时是相反的

二进制数1101存到bitset中是{1,0,1,1}，根据bitset的size补齐0

bitset中使用<<和>>时想象成对这个bitset数组代表的二进制数进行操作就行了

 1 #include <bits/stdc++.h>
 2 #include <bitset>//用bitset要加这个头文件
 3 typedef long long LL;
 4 #define pb push_back
 5 const int INF = 0x3f3f3f3f;
 6 const double eps = 1e-8;
 7 const int mod = 1e9+7;
 8 const int maxn = 1e5+10;
 9 using namespace std;
10 
11 bitset<1000005> ans,temp;
12 
13 int main()
14 {
15     #ifdef DEBUG
16     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
17     #endif
18     
19     int n;
20     scanf("%d",&n);
21     ans.set(0); //为了后面更新值,最初让0在ans集合中
22     for(int i=1;i<=n;i++)
23     {
24         int l,r;
25         scanf("%d %d",&l,&r);
26         temp.reset();//让temp所有位都为0
27         for(int j=l;j<=r;j++)
28             temp |= ans << (j*j);
29         ans=temp;
30     }
31     printf("%d
",ans.count());//输出ans中位上是1的个数
32     
33     return 0;
34 }