可以说每个带多样例的有101810^{18}的超大空间单点询问都是有纯粹的数学逻辑和策略的。

题目目的是这样的

(不讲题意了,作为学习英文的一种必要训练)

给定nnkk,记一个已完成的量为xx,初始值x0=1x_0=1,每次倍增xx,当倍增数量超过2k2k时,就每次只递增kk个。

根据题意,首先,若nn本身是22的幂,那么显然只要knk\geq n,那么最终的操作次数就是log2n\log_2 n。而除此之外不满22的幂的,显然是向上补,即多出一个都要加一次。

故,这个方面的结果就是log2(n)\left\lceil \log _2(n)\right\rceil

然后是,关于kk的倍增情况,在xx倍增的基础上,需要kk的量也是同时倍增的。因此,和次数有关的关系就是一个 2pk2^p \le k 但已倍增的量相当于多乘一个22(一开始用一条线就传完两台机),故考虑这样的结果:

已完成的量为2q2k2^{q} \le 2 k。其实两者的关系指数上就差一,值的关系就差个两倍。

要求2pk2^p \le kpp

这里用一种概念来表示分别为lowbit\text{lowbit}highbit\text{highbit},但由于位和值的关系,我一般需要对应位上的值时,在后面补上一个'v',即lowbitv\text{lowbitv}等。

根据这些描述,一般来说可以知道p=log2(k)p=\left\lfloor \log _2(k)\right\rfloor,但是求log2(k)\log _2(k)很可能会发生浮点问题,对于该题来说,即使你使用long double相关的运算也无法保证算对。对于这种问题,提出了一系列基于进制的函数概念,首先,low和high其实就分别对应于最低与最高位的位置。一般定义-bit中正是将其定义为其仅保留最高或最低位的值的运算。

按我这里的概念就是说:

2p=highbitv(k)2^p=\text{highbitv}\left(k\right)

当然,要算已完成的,就是算$$\text{highbitv}\left(2k\right)$$

关于剩下的部分,如果kk不够倍增了,那么只能按kk递增处理,根据前面说的,多出一个都要增加次数,所以是向上取整的过程,加上已经倍增了的数量可得:

nhighbitv(2k)k+p+1\left\lceil \frac{n-\text{highbitv}(2k)}{k}\right\rceil+p+1

由于这个情况是倍增尽了的,所以说,既是倍增了p+1p+1次,也是要求nhighbitv(2k)n-\text{highbitv}(2k)故完全可以不用考虑pp,而是求p+1=log2(2k)p+1=\log_2(2k)以及2p+1=highbitv(2k)2^{p+1}=\text{highbitv}(2k)

Ext

公式一:

ab=a+b1b\left\lceil \frac{a}{b}\right\rceil =\left\lfloor \frac{a+b-1}{b}\right\rfloor

公式二:

log2(n)=log2(2n1)\left\lceil \log _2(n)\right\rceil =\left\lfloor \log _2(2 n-1)\right\rfloor

这两个公式是让计算机真正能算的一个关键步骤,由于log2(x)\log _2(x)在非22的幂中未必正确,因此需要确定整数级的算法计算,这就是highbitv\text{highbitv},其实质就是算log2(k)\left\lfloor \log _2(k)\right\rfloor,所以说,说到带high、low的实质是确定整数或进制运算去求某个本意上是实数函数的数学对象,他们都是进制函数。

使用公式一:

nhighbitv(2k)k+p+1\left\lceil \frac{n-\text{highbitv}(2 k)}{k}\right\rceil+p+1

等价于算:

(n - (1ull << (p + 1)) + k - 1) / k + p + 1

根据公式二,可以预先算出两个值,一个是 highbitv(2n1)\text{highbitv}(2 n-1) 记为k1k_1一个是 highbitv(2k)\text{highbitv}(2 k) 记为k2k_2

根据比较关系,当k1k2k_1\le k_2时,应输出log2(k1)\log_2\left(k_1\right)(考虑储存数制即可)

否则,输出(n - k2 + k - 1) / k + (ull)log2(k2)

Ext2

highbitv\text{highbitv}的算法:

一:一位位数,从最大位开始(如0x8000000000000000ull)可以只用1去位与(单个&运算符),第一个非零的即是。运算量为前导零的个数的四倍加三。

二:一位位数,但从小到大,会比较麻烦,首先初始值为-1(对应于无符号的所有位都为1),一直左移,直到位与(&)为0的前一个位。运算量为highbitv本身的四倍

三:使用lowbitv(x)==x&(-x)==x&(x-1)。逐位消除,运算量为二进制为1的个数的四倍。

这里举例方法三的代码:

ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

Last

综上可以写出一段代码:

typedef unsigned long long ull;
typedef long long ll;
ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

int main() {
    main_first;
    ull t, n, k; cin >> t;
    while (t--) {
        cin >> n >> k;
        ull k1 = hbv(k << 1), k2 = hbv((n << 1) - 1);
        if (k2 <= k1) {
            cout << (ull)log2(k2) << '\n';
        } else {
            cout << (n - k1 + k - 1) / k + (ull)log2(k1) << '\n';
        }
    }
    main_end;
}

可以根据自己需要自行实现

完整参考代码: VjudgeShared

#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t ulll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long long ll;
template<typename T>
T getuint() {
    T x = 0; char c = getchar(); while (c > '9' || c < '0') c = getchar();
    while (c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
    return x;
}
template<typename T>
T getint() {
    T x = 0; char c = getchar(); bool neg = false;
    while (c > '9' || c < '0') { if (c == '-')neg = true; c = getchar(); }
    while (c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();
    return x;
}
#define Unlock
#ifdef DEBUG
#define main_end cout << endl;system("pause");return 0
#else
#define main_end cout << flush;return 0
#endif
#ifdef Unlock
#define main_first ios::sync_with_stdio(false);cin.tie(nullptr)
#else
#define main_first cin.tie(nullptr)
#endif
#define range(i,n) for(ull i=0;i<n;++i)
#define bitelim(it,n) for(ull x=n,it=x&-x;x;x^=it,it=x&-x)
#define foreach(it,iterable) for(auto it=iterable.begin();it!=iterable.end();++it)
#define gcd __gcd
#define count_bits __builtin_popcountll
#define loop for(;;)
#define vecprint(vec) for(auto&&v:vec) cout<<v<<' ';cout

ull hbv(ull x) {
    ull y;
    do { y = x; x = x & (x - 1); } while (x);
    return y;
}

int main() {
    main_first;
    ull t, n, k; cin >> t;
    while (t--) {
        cin >> n >> k;
        ull k1 = hbv(k << 1), k2 = hbv((n << 1) - 1);
        if (k2 <= k1) {
            cout << (ull)log2(k2) << '\n';
        } else {
            cout << (n - k1 + k - 1) / k + (ull)log2(k1) << '\n';
        }
    }
    main_end;
}

0 comments

No comments so far...