小学数学题_牛客博客

蛮不错的一题，很有意思

并不是独创的算法，说是解释了其他人的代码也不为过，虽然自己也想到了同样的解法

0x00 特殊构造

首先考虑一下 $2^0, 2^1, 2^2, 2^3 ,\dots, 2^n$ ，每种幂次的数各一个

显然可以获得 $0 \sim 2^{n+1} - 1$ 共 $2^{n+1}$ 个数

0x01 直接加数的情况

考虑在上述数列中添加一些数，显然不管怎么添加幂次小于等于 $n$ 的数，其能获得的数仍然是从0开始的连续自然数，求数列和 + 1即为答案

0x02 数列不连续，出现“断层”

跳过数 $2^{n+1}$ ,直接加入数 $2^{n+2}$ ，显然现在能获得的数不再是连续的了，而是两段连续的数

一段从0开始，另一段从 $2^{n+2}$ 开始，长度均为 $2^{n+1}$ ,答案为 $2*2^{n+1}$

我们继续加入新数，假设成为以下情况 $2^0, 2^1, 2^2, 2^3 ,\dots, 2^n,2^{n+2}, 2^{n+3}, 2^{n+4}, 2^{n+5} ,\dots, 2^{2n}$

前面的 $n+1$ 个数，能将一段连续的自然数覆盖，

后面 $n-1$ 个数，当我们把数轴上长度为 $2^{n+2}$ 的区间合并成一个点，并将坐标值除 $2^{n+2}$ 形成新数轴，在新数轴上也能覆盖连续的自然数区间

举个例子：

原数轴： $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$

合并区间长度为4

原数轴： $[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15],[16$

新数轴： $0,1,2,3,4$ 分别对应原坐标： $0,4,8,12,16$

例子结束，承接上文

对于新数轴，我们发现其中每一个点都对应原数轴一段以该点为起始的区间，

对于原数轴，我们每段长为 $2^{n+2}$ 的区间，能覆盖到的数只有 $2^{n+1}$ 个（比如 $0 \sim 2^{n+2} -1$ 这个区间和 $2^{n+2} \sim 2^{n+3} -1$ 这个区间，都只覆盖了区间的前 $2^{n+1}$ 个数）

于是我们只要求得在新数轴上我们覆盖了多少个数，乘以之前求得的每段区间的数，就是答案，

显然又可以有新新数轴，总之可以递推下去，求得总答案

code:

#include<bits/stdc++.h>
using namespace std;

int n;
long long a[55];//十年OI一场空，不开long long 见祖宗

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) scanf("%lld", a + i);
    sort(a + 1, a + n + 1);//排序，显然要从小到大分析，否则无法准确考虑连续
    a[n+1] = 1e18;
    long long tot = 0, ans = 1, cnt = 0, base = 1;//tot：用于判断断层，对应最后一段连续区间的右端点的值;cnt 当前状态数轴的覆盖点数;base：当前状态数轴单点对应原数轴区间长度
    for(int i = 1; i <= n + 1; ++ i){
       if(tot >= a[i]){//直接加
           tot += a[i];//右端点更新
           cnt += a[i]/base;//数轴上新增覆盖点数
       }else{//断层
           ans = ans * (cnt + 1);//计算区间大小为a[i]时，每段区间的答案
           tot = a[i]; cnt = 1; base = a[i];//更新右端点，区间大小，覆盖点数
       }
    }
    //准确来说，我们获得了区间大小为1e18，每段区间的答案
    printf("%lld", ans);
    return 0;
}