题干：

题目描述

输入格式

第一行一个数 n。
然后 n 行，每行两个数表示 ai​,bi​。

输出格式

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

样例

样例输入

5
1 2
2 3
3 4
4 5
5 6

样例输出

26

数据范围与提示

解题报告：

  注意到要求统计种类数，所以输入a,b分别为10,11的时候我们可以看成是可以增加的范围就是11*11-10*10，所以我们先预处理一下，都减去a*a，就是我们的可到达范围（当然这时候已经不是对应的真实值了，但是对于统计种类数这样是没有什么大问题的）

AC代码：

#include <algorithm>
#include <bitset>
#include <cstdio>
const int N = 105;
bool f[2][1000050];
int main() {
	int n, a, b;
	scanf("%d", &n);
	int maxv = 0;
	bool *x = f[0], *y = f[1];
	x[0] = 1;
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &a, &b);
		int siz = b * b - a * a;
		for (register int j = maxv + siz; ~j; --j) {
			y[j] = 0;
			for (int k = a; k <= b && j >= k * k - a * a && !y[j]; ++k)
				y[j] |= x[j - k * k + a * a];
		}
		std::swap(x, y);
		maxv += siz;
	}
	int ans = 0;
	for (register int i = 0; i <= maxv; ++i)
		if (x[i]) ++ans;
	printf("%d\n", ans);
	return 0;
}

AC代码2：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 1000000 + 5;
bitset<MAX> bs[2];
int main()
{
	int n;
	cin>>n;
	bs[0][0]=1;
	int flag = 0;
	for(int x,y,i = 1; i<=n; i++) {
		scanf("%d%d",&x,&y);
		flag ^=1;
		for(int j = x; j<=y; j++) bs[flag] |= bs[flag^1]<<(j*j);
		bs[flag^1].reset();
	}
	printf("%lld\n",bs[flag].count());
	return 0 ;
}

注意MAX不能2e6，，不然就TLE了。。复杂度O(100*100*1e6/64)

TLE代码：

#include<bits/stdc++.h>
using namespace std;
int dp[2][1000001];
int main() {
	//clock_t start = clock();
	int n, m; scanf("%d", &n);
	int l, r;
	dp[0][0] = 1;
	for (int i = 1; i <= n; i ++) {
		scanf("%d %d", &l, &r); m += r * r;
		for (int j = 0; j <= m; j ++){
			dp[(i % 2)][j] = 0;
			for (int k = l; !dp[(i % 2)][j] && k * k <= j && k <= r; k ++)
				dp[(i % 2)][j] += dp[1 - (i % 2)][j - k * k];
		}
	}
	int ans = 0;
	for (int i = l * l; i <= m; i ++) ans += (bool)(dp[n % 2][i]);
	printf("%d\n", ans);
	//cout <<"Running Time : "<<(double)(clock() - start)/ CLOCKS_PER_SEC << endl;
	return 0;
}