刷题记录:牛客NC17193简单瞎搞题

传送门;牛客

题目描述:
一共有 n个数，第 i 个数是 xi
xi 可以取$[li,ri]$ 中任意的一个值。
设 $S=\sum {x_i}^2$
，求 S 种类数。
输入:
5
1 2
2 3
3 4
4 5
5 6
输出:
26

这道题目还是挺有意思的.首先我们看到这道题目想到的应该是区间dp的想法

想法一:

1. 我们使用$dp[i][j]$来记录枚举完前$i$个数字能否组成$j$的值.我们使用bool来存储
2. 这样的话我们就有一种比较简单的转移方案,我们可以判断前面的已经可以组成的数字来加上我们此时的可以加上的$xi$的值来进行转移.具体代码如下

for(int i=1;i<=n;i++){
    scanf("%d%d",&l,&r);
    for(int j=r;j>=l;j--){
        for(int k=sum;k>=0;k--){
           f[i][k+j*j]=f[i-1][k];   
        }    
    }
    sum+=r*r;
}
1
2
3
4
5
6
7
8
9

3. 但是我们发现如果这样进行转移的话需要的复杂度将是$N^4$,这样子的话肯定是会超时的,所以我们需要将此代码进行一个优化.我们发现我们主要的判断是否能组成一个数字时是可以使用二进制来进行优化的.仔细想一下,原来对于第i个区间来说,我们是在前i-1个区间已有的情况下进行操作的,举个例子也就是假设前面的情况是(1001),也就是1和4是已有的,那么对于现在假设又是加1和4,那么就是将前面的(1001)左移1个位置和4个位置,分别得到(10010和10010000,也就是经过第i个区间之后可能的数字).也就是将我们的加法操作改成位运算左右移动.然后我们再将移动后的01串和我们原来的01串进行或操作来合并即可(或可以解决重复的问题),但是我们发现这样的话我们又需要$100\ast 100\ast 100\ast 100$的长度的01串,那么此时一般的存储方式就无法方便的解决这个问题了
4. 但是c++中的$stl$为我们提供了$bitset$这样的巧妙的类型.这个类的作用就是给你一个长度更长的01串,并且这个类型存储的内存只占$bool$类型的$1/8$,这样的话我们就可以通过这道题了
5. 对于bitset,我们此题涉及以下函数

$btiset<length>dp[100]$
$dp[0].set(0):代表将我们的第一个01串的第0个位置置为1$
(注意我们的bitset是从右往左进行移动的)
$dp[n].count(),用来输出我们的01串中的1的个数$在本题中就是不同数字的是否可行性

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000010
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
bitset<maxn>dp[110];
int main() {
	n=read();int l,r;
	dp[0].set(0);
	for(int i=1;i<=n;i++) {
		l=read();r=read();
		for(int j=l;j<=r;j++) {
			dp[i]|=(dp[i-1]<<(j*j));
		}
	}
	cout<<dp[n].count()<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41