Description:

一共有 n个数,第 i 个数是 xi

xi 可以取 [ l i , r i ] [l_i , r_i] [li,ri] 中任意的一个值。

S = x i 2 S=\sum{{x_{i}}^{2}}​ S=xi2,求S种类数。

Input:

第一行一个数 n n n

然后n行,每行两个数表示 l i l_i li r i r_i ri

(1 ≤ , l i l_i li , $ r_i$ ≤ 100)

Output:

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

Sample Input:

5
1 2
2 3
3 4
4 5
5 6

Sample Output:

26

题目链接

这题目暴力肯定会超时,赛后看大佬们代码都用的bitset来优化动态规划,被队友讲懂。

不知道bitset的话先看C++基础——简单而强大的bitset

先用AC代码主函数改成

int main() {
    //fre();
	read(n);
	s1.set(0);
	while (n--) {
		read(a);
		read(b);
		s2.reset();
		cout << "s1=";
		for (int i = 0; i < 10; ++i) {
			cout << s1[i];
		}
		cout << endl;
		for (int i = a; i <= b; ++i) {
			s2 |= s1 << (i * i);
			cout << "s2=";
			for (int i = 0; i < 10; ++i) {
				cout << s2[i];
			}
			cout << endl;
		}
		swap(s1, s2);
	}
	printf("%d\n", (int)s1.count());
    return 0;
}

以便观察bitset用法跑一遍

2
1 2
1 2

这个数据,结果输出

2
1 2
s1=1000000000
s2=0100000000
s2=0100100000
1 2
s1=0100100000
s2=0010010000
s2=0010010010
3

可以观察这个做法的核心思想就是用二进制中1的个数来记录种类数。

s1是结果,s2是中间变量,首先s1除首位外全为0,s2在每次循环重置全为0。

对于上述数据:

第一组区间是1~2,在for循环中,当i为区间第一个数1时s2和s1向左移动(bitset按下标输出的是倒序,所以在上面数据输出中表现为向右移动) i 2 i^2 i2 i 2 i^2 i2代表 S = x i 2 S=\sum{{x_{i}}^{2}} S=xi2中的 x 1 2 {x_1}^{2} x12)(这里 i 2 i^2 i2=1)位的结果做或运算,被记录到s2[1]第一位,当i为区间第二个数2时s2和s1向左移动 i 2 i^2 i2(这里 i 2 i^2 i2=4)位的结果做或运算,这里的 i 2 i^2 i2被记录到s2[4],当这个区间遍历完后交换s1,s2的值(这里是dp的思想,每一个区间之和上一个区间结果相关),将s2所做的记录赋值给s1,按照数据输出可知s1=0100100000,这里第一个区间的两个数1和4就被记录上了。

再接着循环便利第二个区间,在for循环中,当i为区间第一个数1时s2和s1向左移动 i 2 i^2 i2(这里 i 2 i^2 i2=1)位的结果做或运算,按照数据输出可知s2=0010010000,当i为区间第二个数2时s2和s1向左移动 i 2 i^2 i2(这里 i 2 i^2 i2=4)位的结果做或运算,s1向左移动4位之前:s1=0100100000,s1向左移动4位之后:s1=0000010010,在for循环i=1执行之后:s2=0010010000

我们对比一下做或运算时的两个数

0000010010

0010010000

这里有两个1的位置重合了,因为上面那个数中的第一个1是经过先向左移动一位后又向左移动4位所抵达的位置(代表两组区间中第一组区间选择了数字1,第二组区间选择了数字2)而下面那个数的第二个1是先经过向左移动4位后又向左移动1位所抵达的位置(代表两组区间中第一组区间选择了数字2,第二组区间选择了数字1),这两种情况下 1 2 + 2 2 = 2 2 + 1 2 1^2+2^2=2^2+1^2 12+22=22+12S相等,所以两个数的或运算就起到了去重的作用,0000010010和0010010000两个数或运算的结果按照数据输出可知是0010010010,序列中有3个1,所以上面的数据最终结果就是3。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 102;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
inline void fre() {freopen("in.txt", "r", stdin);/*freopen("out.txt", "w", stdout);*/}

int n, a, b;
bitset<1000005> s1, s2;
 
int main() {
    //fre();
	read(n);
	s1.set(0);
	while (n--) {
		read(a);
		read(b);
		s2.reset();
		for (int i = a; i <= b; ++i) {
			s2 |= s1 << (i * i);
		}
		swap(s1, s2);
	}
	printf("%d\n", (int)s1.count());
    return 0;
}