专栏文章

题解：P12642 [KOI 2024 Round 1] 加倍

ccomplete_binary_tree
P12642题解参与者 8已保存评论 12

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
12 条
当前快照
1 份
快照标识符
@mip6ewt6
此快照首次捕获于
2025/12/03 06:55
3 个月前
此快照最后确认于
2025/12/03 06:55
3 个月前
查看原文
首先，任何使用 long long、unsigned long long 甚至 double 的暴力 ×2\times 2 做法肯定是过不了这题的。
稍微分析一下就可以知道出题人可以构造出 [1000000,999999,999998,… ][1000000,999999,999998,\dots] 这样的序列，而这样的序列操作次数是 1∼n1\sim n 的等差数列级别的（n2n^2 级别），操作出来的数是 2n2^n 级别的，long double 来了都存不下。
但是我们想到 double，我们可以发现 double 由指数位和真实数位组成。我们是否能像 double 一样把指数位存起来呢？
我们可以开一个结构体，一个存数字 aa，一个存指数 nn。那么这个数就能表示为 a×2na \times 2^n 的形式。
当数字读入进来，我们先将它的二进制下最高位 11 对齐到 1<<20 这位（方便比大小），然后计算它的指数（原来最高位的 11 是 22 的几次方就存几）。
由于它要大于等于前一个数，所以它最终的指数肯定要大于等于前一个数的指数，所以我们先加上这一段。
此时这个数可能还小于前面那个数。不过这好办，再乘一次 22 就行了。
代码：（拿下最优解）
CPP
#include<iostream>
using std::cout;
static char buf[1048576], * pa(buf), * pb(buf);
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 1048576, stdin), pa == pb) ? EOF : *pa++
int cnt=0,n,x;
long long ans;
struct node{
    int a,b;
}a[250001];
char ch;
inline void read(int&x) {
  x=0;
  ch=gc;
  while (!isdigit(ch)) {
    ch = gc;
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = gc;
  }
}
int main() {
    read(n);
    for (int i = 0; i < n; i++) {
        read(a[i].a);
        cnt=0;
        while(a[i].a>>cnt)++cnt;
        a[i].a<<=(20-cnt)+2,a[i].b=cnt;
        if(!i)continue;
        if(a[i-1].b>a[i].b)ans+=a[i-1].b-a[i].b,a[i].b=a[i-1].b;
        if(a[i-1].b==a[i].b&&a[i-1].a>a[i].a)a[i].b++,ans++;
    }
    cout<<ans;
    return 0;
}

评论

共 12 条评论，欢迎与作者交流。

正在加载评论...