题解：AT_arc182_b [ARC182B] |{floor(A_i/2^k)}|

lkjzyd20 · 2024-08-22 09:33:22 · 题解

题意

给定两个正整数 N 和 K，然后让你得出一个使得序列中的 \large \left\lfloor\frac{A_i}{2^k} \right\rfloor 表示的不同约数的个数越多。对于每个测试用例，输出这个序列。

思路

最大得分意味着你需要尽可能多的不同数值。从 1 到 2^K - 1 之间的数值越分散，得分可能越高。则可以转换成给一个节点个数为 2^K-1 的满二叉树，覆盖尽可能多的节点。

简单模拟一下递归过程即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)

const int N = 1e5 + 5;
int n, k, x, tot, Q, a[N];
void dfs(int p,int s)
{ 
    if(!s) return;
    if(p * 2 >= 1 << k) 
    { 
        for(; s; -- s) a[++ tot] = p;
        return;
    }
    dfs(p * 2, s / 2); 
    dfs(p * 2 + 1, s - s / 2);
}
main()
{
    scanf("%d", &Q);
    for(; Q; -- Q)
    {
        scanf("%d %d", &n, &k);
        tot = 0;
        dfs(1, n);
        rep(i, 1, tot) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}