集训队日常训练20181201 C 1003 : 种类数

时间限制(普通/Java):2000MS/6000MS     内存限制:65536KByte
总提交: 8            测试通过:5

描述

一共有 n个数，第 i 个数是 x ，其中x 可以取 [l , r] 中任意的一个值。

设 ，求 S 种类数。

输入

第一行一个数n，接下来有n行，每行两个整数l，r。

1<=n，l，r<=100，数据保证l<=r。

输出

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

样例输入

5
1 2
2 3
3 4
4 5
5 6

样例输出

26

解析：用bitset优化，dp，每输入一个范围，就是在前面已经计算的基础上加上这次范围内的数，每一次都加上l 到 r的范围的值，用|代替加法，<<i*i把答案加入到数组中。状态转移方程是a[i]|=a[i-1]<<(i*i);

 #include "bits/stdc++.h"

 #define ll long long

 using namespace std;

 inline void read(int &x)

 {

     x=;char c=getchar();

     while(c<'' || c>'')c=getchar();

     while(c>='' && c<=''){

         x=x*+c-'';

         c=getchar();

     }

 }

 inline void write(int x)

 {

     int y=,len=;

     while(y<=x) {y*=;len++;}

     while(len--){y/=;putchar(x/y+);x%=y;}

 }

 bitset<>a,b;

 int main()

 {

     int n,l,r;

     read(n);

     b[]=;

     while(n--)

     {

         read(l);read(r);

         a.reset();

         //b.reset();

         //b[0]=1;

         for(int i=l;i<=r;++i)

         {

             a|=b<<(i*i);

         }

         b=a;

     }

     printf("%d\n",b.count());

 }