本文共 1013 字，大约阅读时间需要 3 分钟。

题目地址：https://ac.nowcoder.com/acm/problem/17193

闲话：这个题目是一个状压dp，不过我的dp一向很垃圾，状压也没怎么练过，做的时候属实看不出来，看了别人的题解才会做。不过我现在也有了一些思考：当只有存在或不存在两种状态时我就可以联想到状态压缩了。 对于这个题目其实到现在也不是特别懂了，还是有些不太明白的先记录下来。

题解

这个题目中最重要的就是bitset的运用。首先我们需要知道bitset是什么。

bitset本质上可以看作是一个数组，不过每一位只能是0或1，即一个支持位运算的二进制数组 这个题目中我们定义了两个bitset容器dp和tep。dp保存上一次所有的S值，tmp保存这一轮所有的S值，并将dp[0]的的初始值设为1，方便之后的转移。

就下来就是递推公式的推导了了。

1.在这个题目中，可以用bitset容器来保存数字。记录每一个数字的平方是否可以存在。 2.外层循环代表n个区间的遍历,内层循环用来表示遍历一个区间中所有可能取到的值。 3.每次转移与要用到位运算<<和|，因为在区间里增加上了一个平方的可能取值，这意味着tmp容器要更新当前s的值。而只需要dp<<j*j就可以表示上一次的s值增加了新的量，在进行或运算就消除了相同的结果，存进了tmp中。（不过对于为什么左移多少位就代表增加我还没有想的特别清楚） 那么转移如下：

for(int j=l;j<=r;j++) tmp|=dp<<jj;

代码：

#include 
   
    #define INF 0x3f3f3f3f;//const int maxn=;using namespace std;typedef long long ll;bitset<1000005>dp,tmp;int main (){
       //freopen("D:\\input.txt", "r", stdin);    //freopen("D:\\output.txt", "w", stdout);    int n,l,r;    cin>>n;    dp[0]=1;    for(int i=1;i<=n;i++){
           cin>>l>>r;       tmp.reset();        for(int j=l;j<=r;j++)            tmp|=dp<
   

转载地址：https://blog.csdn.net/u011612364/article/details/106226407 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！