题目传送门(BZOJ)

题解 :

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

-1 相当于在最低位 -1,
在某位 -1 若不发生退位, S-1,
若发生退位, 下一位会 -1, S-1, 这一位会 +(B-1), S 不会改变,
-1S 在任意情况下的影响都是 +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原创, 转载必须以链接形式注明>原文链接<