牛客练习赛22 C 简单瞎搞题

  • 2018-07-16
  • 26
  • 1

题目:

一共有 n个数,第 i 个数是 xi

xi 可以取 [l_i , r_i] 中任意的一个值。

S=\sum{{x_{i}}^{2}}​,求S种类数。

Input:

第一行一个数n

然后n行,每行两个数表示l_ir_i

(1 ≤ , l_i , r_i ≤ 100)

Output:

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

Sample Input:

5
1 2
2 3
3 4
4 5
5 6

Sample Output:

26

题目链接

这题目暴力肯定会超时,赛后看大佬们代码都用的bitset来优化动态规划,被队友讲懂。

不知道bitset的话先看

C++基础——简单而强大的bitset

先用AC代码主函数改成

以便观察bitset用法跑一遍

2
1 2
1 2

这个数据,结果输出

2
1 2
s1=1000000000
s2=0100000000
s2=0100100000
1 2
s1=0100100000
s2=0010010000
s2=0010010010
3

可以观察这个做法的核心思想就是用二进制中1的个数来记录种类数。

s1是结果,s2是中间变量,首先s1除首位外全为0,s2在每次循环重置全为0。

对于上述数据:

第一组区间是1~2,在for循环中,当i为区间第一个数1时s2和s1向左移动(bitset按下标输出的是倒序,所以在上面数据输出中表现为向右移动)i^2i^2代表S=\sum{{x_{i}}^{2}}中的{x_1}^{2})(这里i^2=1)位的结果做或运算,被记录到s2[1]第一位,当i为区间第二个数2时s2和s1向左移动i^2(这里i^2=4)位的结果做或运算,这里的i^2被记录到s2[4],当这个区间遍历完后交换s1,s2的值(这里是dp的思想,每一个区间之和上一个区间结果相关),将s2所做的记录赋值给s1,按照数据输出可知s1=0100100000,这里第一个区间的两个数1和4就被记录上了。

再接着循环便利第二个区间,在for循环中,当i为区间第一个数1时s2和s1向左移动i^2(这里i^2=1)位的结果做或运算,按照数据输出可知s2=0010010000,当i为区间第二个数2时s2和s1向左移动i^2(这里i^2=4)位的结果做或运算,s1向左移动4位之前:s1=0100100000,s1向左移动4位之后:s1=0000010010,在for循环i=1执行之后:s2=0010010000

我们对比一下做或运算时的两个数

0000010010

0010010000

这里有两个1的位置重合了,因为上面那个数中的第一个1是经过先向左移动一位后又向左移动4位所抵达的位置(代表两组区间中第一组区间选择了数字1,第二组区间选择了数字2)而下面那个数的第二个1是先经过向左移动4位后又向左移动1位所抵达的位置(代表两组区间中第一组区间选择了数字2,第二组区间选择了数字1),这两种情况下1^2+2^2=2^2+1^2S相等,所以两个数的或运算就起到了去重的作用,0000010010和0010010000两个数或运算的结果按照数据输出可知是0010010010,序列中有3个1,所以上面的数据最终结果就是3。

AC代码:

评论