LOJ515

题意：

一共有n个数，第i个数$x_i​$可以取$[a_i,b_i]​$中任意值。 设$S=\sum{x_i^2}​$，求S种类数。其中$1≤n,a_i,b_i≤100​$。

思路：

刚开始想到的是DP，但是100^4会爆炸，所以就用bitset来暴力一下。

每一位表示的是有没有该答案，这是一个集合，如果这个集合中的每个数要与一个数x相加怎么办呢？就是把这个集合左移x位然后再与集合或运算就可以了。

代码：

bitset<1000100>ans[110];
int main()
{
    int n,l,r;
    scanf("%d",&n);
    ans[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&l,&r);
        for(int j=l;j<=r;j++)
            ans[i]|=ans[i-1]<<(j*j);
    }
    printf("%d\n",ans[n].count());
    return 0;
}

51nod1573

题意：

我们现在有n个多重集合，第i个集合最开始都有一个元素ai(1≤i≤n)。

一个多重集合的价值为子集中不同的和的个数。

例如一个多重集合{1,2}，那么会存在有4个不同的和{0,1,2,3}。其价值为4。

一个多重集合{2,2}，那么会有3个不同的和{0,2,4},其价值为3。

现在我们有两种操作：

1、合并最开始时多重集合i现在所在的多重集合与多重集合j现在所在的多重集合，成为一个新的多重集合。

2、询问最开始多重集合i现在所在多重集合的价值。

数据保证合并两个最开始时的多重集合所在的多重集合时它们当前不是同一个多重集合。

思路：

用并查集来进行启发式合并（小的并到大的），对于每个集合元素都存在一个vector里，如果i所在的集合要和j所在的集合合并了，先找到i和j各自的根，对于小的那个集合，每个元素放到大的那个vector里，每个小的集合里的元素和大的集合相加（左移x）。询问的时候找根然后把1的个数输出即可。

代码：

int par[1010];
vector<int>v[1010];
bitset<100010>a[1010];
int Find(int x)
{
    if(par[x]==x)return x;
    return par[x]=Find(par[x]);
}
void Unite(int x,int y)
{
    if(v[x].size()<v[y].size())swap(x,y);   //y合并到x
    for(int i=0;i<v[y].size();i++)
    {
        v[x].push_back(v[y][i]);
        a[x]|=(a[x]<<v[y][i]);
    }
    //cout<<a[x]<<endl;
    par[y]=x;
}
int main()
{
    int n,x,q,op,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        a[i].set(0);a[i].set(x);
        par[i]=i;
        v[i].push_back(x);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            x=Find(x);y=Find(y);
            Unite(x,y);
        }
        else if(op==2)
        {
            scanf("%d",&x);
            x=Find(x);
            printf("%d\n",a[x].count());
        }
    }
    return 0;
}

总结

类似集合合并，或者每个状态就是01(yes or no)的题目，可以考虑用bitset来搞。复杂度可以降低到原来的1/32或者1/64（视计算机而定）。