题目传送门(BZOJ)

题解 :

一个重要的性质 : $B$进制数在$+B-1$后, 各位数字之和$S$在$\mod B-1$意义下答案不变
证明 :
$+B$ 相当于在第二位(从低位起) $+1$,
在某位 $+B$ 若不发生进位, $S$ 会 $+1$,
若发生进位, 下一位会 $+1$, $S$ 会 $+1$, 这一位会 $-(B-1)$, $S$ 不会改变,
故 $+B$ 对 $S$ 在任意情况下的影响都是 $+1$

$-1$ 相当于在最低位 $-1$,
在某位 $-1$ 若不发生退位, $S$ 会 $-1$,
若发生退位, 下一位会 $-1$, $S$ 会 $-1$, 这一位会 $+(B-1)$, $S$ 不会改变,
故 $-1$ 对 $S$ 在任意情况下的影响都是 $+1$

综上 $+B-1$ 不会对 $S$ 产生影响
所以可以推出 : 一个 $B$ 进制数字是 $B-1$ 的倍数的充要条件是各位数字加和是 $B-1$ 的倍数

题目中要求使 $x$ 尽可能的大, 我们直接贪心的让高位尽可能的大, 位数尽可能的多一定最优秀
我们先不管是不是 $B-1$ 的倍数, 直接把所有的数字都选上, 若这个数在 $\mod B-1$ 下的结果是 $x$, 那么我们直接扔掉一个 $x$即可
注意 题目有一个条件是 $a[i]\ge 1$, 所以直接删掉一个就行
然后做一个前缀和, 每次二分查找第 $k$ 位即可, 注意不到 $k$ 位的特判

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int N = 1000100;ll x, k, s[N];int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) scanf("%lld", &s[i]), x += (i-1)*s[i], s[i] += s[i-1]; x %= n-1; if(x) for(int i = x+1; i <= n; i ++ ) s[i] --; while(m -- ) { scanf("%lld", &k); printf(s[n] <= k ? "-1\n" : "%ld\n", lower_bound(s+1, s+n+1, k+1)-s-1); }}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<