专栏文章

题解：P5956 [POI 2017] Podzielno

ppengziyippp
P5956题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miosyhqj
此快照首次捕获于
2025/12/03 00:38
3 个月前
此快照最后确认于
2025/12/03 00:38
3 个月前
查看原文

题目大意

给出一个 BB 进制的数 XX，每个数字 i∈[0,B)i \in [0,B) 有 aia_i 个。用数字组成最大 XX 使其是 B−1B-1 的倍数，并回答 qq 个第 kk 位是什么的询问。

思路简述

水题但赛时没有想出来，果然我是废物捶石了。
思考观察在 BB 进制下一个数是 B−1B - 1 的倍数有什么性质。
由于我们知道，在 BB 进制下，一个数由由多个 BxB^{x} 组成，若我们使用 ans[i]ans[i] 表示 XX 第 ii 位的大小，则可得：
X=B0×ans[0]+B1×ans[1]+B2×ans[2]+⋯X = B^{0} \times ans[0] + B^{1} \times ans[1] + B^{2} \times ans[2] + \cdots
这里我们可以观察到 BxB^{x} 一定不为 B−1B-1 的倍数，所以要想使 XX 为 B−1B-1 的倍数，我们只能将所有 ans[i]ans[i] 的和控制为 B−1B-1 的倍数。
如何控制为 B−1B - 1 的倍数呢，由于 a[i]≥1a[i]\ge1，即 00 ~ B−1B-1 每个数都至少给出了一个，所以我们只需要判断一下所有给出的数字之和是不是 n−1n-1 的倍数，若不是，删去 sumsum 多余的部分即为最小代价，因为我们要保证最大时 XX 的位数应该尽可能的多。
再考虑如何最大化，我们容易想到将数字大的放前面，小的放后面，最后判断一下位置输出答案即可。
完结撒花。

代码实现

马蜂良好。
CPP
#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"; // 找出答案 
		}
	}
}

评论

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

正在加载评论...