【牛客算法周周练5】E-简单瞎搞题
简单瞎搞题
https://ac.nowcoder.com/acm/contest/5556/E
简单？瞎搞？搞我？
题目描述：
一共有 n个数，第 i 个数是 xi
xi 可以取 [li , ri] 中任意的一个值。
输入描述：
第一行一个数 n。
然后 n 行，每行两个数表示 li，ri。
输出描述：
输出一行一个数表示答案。
题目
题目描述：一共有 n个数，第 i 个数是 xi
xi 可以取 [li , ri] 中任意的一个值。
设S=∑xi2，求 S 种类数。
第一行一个数 n。
然后 n 行，每行两个数表示 li，ri。
输出描述：
输出一行一个数表示答案。
解析
虽说简单，但这道题其实也不简单，这道题主要用到了bitset容器（详情见专栏）和递推。
题目啥意思呢？
- 题目告诉了我们S=∑xi2：简单来说就是，我们每次输入一组边界，从其中选一个数取平方和。求这个和有多少种。
递推咋推呢？
- 在我们上面赏析了我们的题目之后呢，我们就知道了，我们要的每个平方和只能保留一次：简单来说就是只有存在和不存在两种关系。
- 既然只有两种关系，我们这里就可以用bitset容器来保存每一个数字。用来记录每一位数字时存在还是不存在。（简单来说就是，我们bitset容器的第pos位是0/1就表示，pos这个数字所表示的平方和是否存在。）
- 然后我们就是怎么将选到某个区间的所有sum值保存下来了。我们这里就可以用到或运算，我们循环遍历每一种情况，将所有的sum值或起来（这样的话，只要存在，无论出现了多少次，数组中的这一位都一定是1）。
for (int j = l; j <= r; j++) tmp |= x << j * j;
从这里我们可以看出我们用了两个数组（x和tmp）x用来保存上一次所有S值，tmp保存这一次的所有tmp值。
打代码咯：
- 首先我们要输入我们该输入的东西。
- 然后我们要先得到我们第一组的数值（因为第一组要初始化，不能直接参与后面的递推）。
- 然后就开始递推，外层循环用作遍历n个区间（对n个区间进行累加求值，求到每一个sum）。
- 内层循环用作遍历区间范围内的所有xi值，用来得到累加到当前的所有S值是否存在。
- 强调：这里要额外开一个bitset容器数组用来保存累加到某一区间时的情况（因为这里的情况都是并行的，都要用到上一组区间计算的结果，所以不能让x数组在计算中被覆盖了）。
- 详情看代码吧~
bitset容器
这个容器说难也不难，主要是有一些方便的操作。
- bitset容器本质上是一个数组：而且是一个每一位只能是0或1。（可以认为是一个布尔类型数组，或二进制数组）
那这个容器有什么优点呢？
- 这个容器的占用空间小，每一个元素只占用1b的空间。
- 这个容器重载了一些运算符，比如&和 | 都是按位操作然后放到每一位上，<<和>>就是数组左移位和右移位（自动补0）。
- 然后还有一些内置函数：比如reset可以用来数组清0，其他的就不赘述（我也不是很清楚，可以百度）。
本题运用：
- 这道题我们因为是要判断每一个数字的情况，就用数组的每一位代表了一个数字。
- 同时因为每一个数字只有两种情况我们才用上的（这点重要哦）。
AC代码
#include <iostream>
#include <bitset>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
const int MAX = 1e2 + 7;
bitset<MAX * MAX * MAX> x, tmp;//x保存每个数字是否存在
//全局变量区
int main() {
IOS;
int n; cin >> n;
int l, r; cin >> l >> r;
for (int i = l; i <= r; i++) x[i * i] = 1;
for (int i = 2; i <= n; i++) {
cin >> l >> r;
tmp.reset();
for (int j = l; j <= r; j++) tmp |= x << j * j;
//求或值表示，只要x中
x = tmp;
}
cout << x.count() << endl;
return 0;
}
//函数区比赛 文章被收录于专栏
憨憨的专栏
曼迪匹艾公司福利 121人发布
投递哔哩哔哩等公司6个岗位