BZOJ 4724: [POI2017]Podzielno – [二分]


题目传送门(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 
#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const 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原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注