题目描述

输入描述

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

输出描述

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

整体思路

首先对题意进行分析：从n组数据中，每组（ ~）选一个数进行平方相加，最终记录不同的平方和数量。

如何表示不同的平方和？

我们想到桶排序的方式：若该和存在，就将对应下标位置值1；反之置0。由于每个数只有1,0（存在，不存在）两种情况，可以考虑使用biteset类型。bitset容器可以视为每一种每个元素只占1位的数组，只有当元素值只可能是0或1时才可以使用。

ans[i] = 1代表存在平方和为i；ans[i] = 0代表不存在平方和为i。

如何表示数字相加

通过对ans数组的整体左移可以实现加的功能。eg：0011 表示和可以是1和0；左移一位后 0110 表示和可以是2和1。即：左移多少位就代表在原有的和上加多少。由于最大和可以达到100 100 100，所以设置数组大小为100 100 100。

左移后得到的新的数组与元素组相或，即可得所有的和的可能性。（若与原数组的某个和相同，由于1 | 1 = 1，或运算后直接可达到去重的效果）。

由于每组数据只取其中的一个数的平方，所以在遍历（ ~）时需要设置临时数组temp。

完整代码

#include<iostream>
#include<bitset>
#define IOS ios::sync_with_stdio(false);
using namespace std;
const int maxn = 100*100*100+6;
bitset<maxn>ans, temp;
int main()
{
    IOS;
    int n, l, r;
    cin>>n;
    cin>>l>>r;
    for(int i=l; i<=r; i++)
    {
        ans[i*i] = 1;
    }
    for(int i = 2; i <=n; i++) 
    {
        cin>>l>>r;
        temp.reset();
        for(int i=l; i<=r; i++)
        {
            temp |= ans << i*i;
        }
        ans = temp;
    }
    cout<<ans.count()<<endl;
    return 0;
}

总结

通过今天题目的学习，我初步认识了bitset的用法，也接触到了状态压缩数组（用二进制形式表示数组下标的状态）的思想。
另外，学到了ios::sync_with_stdio(false);的用法（简单来说就是减少cin/cout的时间）。
题目最后确定算法思想无误后仍一直出错的原因，是 maxn 定义的太大了，以后要注意对数组容量进行合理估计。