题解：P5956 [POI 2017] Podzielno

pengziyippp · 2025-07-21 20:13:40 · 题解

题目大意

给出一个 B 进制的数 X，每个数字 i \in [0,B) 有 a_i 个。用数字组成最大 X 使其是 B-1 的倍数，并回答 q 个第 k 位是什么的询问。

思路简述

水题但赛时没有想出来，果然我是废物捶石了。
思考观察在 B 进制下一个数是 B - 1 的倍数有什么性质。
由于我们知道，在 B 进制下，一个数由由多个 B^{x} 组成，若我们使用 ans[i] 表示 X 第 i 位的大小，则可得：

这里我们可以观察到 B^{x} 一定不为 B-1 的倍数，所以要想使 X 为 B-1 的倍数，我们只能将所有 ans[i] 的和控制为 B-1 的倍数。
如何控制为 B - 1 的倍数呢，由于 a[i]\ge1，即 0 ~ B-1 每个数都至少给出了一个，所以我们只需要判断一下所有给出的数字之和是不是 n-1 的倍数，若不是，删去 sum 多余的部分即为最小代价，因为我们要保证最大时 X 的位数应该尽可能的多。
再考虑如何最大化，我们容易想到将数字大的放前面，小的放后面，最后判断一下位置输出答案即可。
完结撒花。

代码实现

马蜂良好。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N], sum[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int b, q; cin >> b >> q;
    int summ = 0, maxx = 0;
    for (int i = 0; i <= b - 1; i ++ ) {
        cin >> a[i];
        summ += (a[i] * i); // 统计和 
        maxx += a[i]; // 统计出最多有多少位 
    }  
    if (summ % (b - 1)) a[summ % (b - 1)] --, maxx --; // 处理掉多余的数 
    sum[0] = a[0];
    for (int i = 1; i <= b - 1; i ++ ) {
        sum[i] = sum[i - 1] + a[i];
    } // 计算到数字i有多少个数位 
    for (int i = 1; i <= q; i ++ ) {
        int k; cin >> k;
        k ++; // 处理第0位 
        if (k > maxx) {
            cout << -1 << "\n"; // 判断是否存在 
        } else {
            cout << lower_bound(sum, sum + b - 1, k) - sum << "\n"; // 找出答案 
        }
    }
}