占座位

· · 个人记录

先特判 k=0 时显然能坐满所有座位。

设 f_n 为 n 个座位能坐的人数。

当 1\le n <2 \times k + 2 时，显然只能坐 1 个人。

当 n\ge 2\times k + 2 时，设第 2 个人坐到 x 号座位，可以想象将 1 和 x 号座位移到一起，发现座位被分成左右两部分，按照这个方式递归求解即可。

f(\left\lfloor\dfrac{n}{2}\right\rfloor) + f(n-\left\lfloor\dfrac{n}{2}\right\rfloor)&n \ge 2 \times k + 2\end{cases}

但这样当 x 为奇数时 f(x) 就会递归到两个子函数去，实际上这样会导致很多次重复计算，所以当 n=10^{18} 时会 \text{TLE}。

可以发现过程中最多只会递归到 2\times log_2^n 个数，所以记忆化搜索。

最简单的做法是用 \text{map} 记录 f_x。

要是真不会用 \text{map} 的话，反正递归到的数还不到 120 个，用数组暴力排序应该也能过。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define LL long long
map<LL,LL>mp;
LL n, k;
LL f( LL x ) {
    if( x < 2 * k  + 2 ) return 1;
    if(mp[x]) return mp[x];
    return mp[x] = f(x/2) + f(x-x/2);
}

int main() { 
    cin >> n >> k;
    if( !k ) {
        cout << n;
        return 0;
    }
    cout << f(n);
}