BZOJ 4724 Podzielno

发表于 | 更新于

Link

Solution

显然， 所以问题就是在这些数字中选出尽量多的数使得和为B−1B-1的倍数，在最多的情况下字典序最大。 我又想DP了，233...似乎跟Bird的思维过程惊人相似。。好吧 因为对于任何数字，有a[i]≥1a[i]\ge 1，所以肯定至少可以取到∑a[i]−1\sum a[i]-1个。而且这样肯定也是最优的。 剩下的数字排个序就是答案要求的数了。。 然后询问在前缀和里面二分就好了(然而这个二分我还费了好大的劲才转过弯来。。)

Tips

std::partial_sum的等价代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class InputIterator, class OutputIterator>
   OutputIterator partial_sum (InputIterator first, InputIterator last,
                               OutputIterator result)
{
  if (first!=last) {
    typename iterator_traits<InputIterator>::value_type val = *first;
    *result = val;
    while (++first!=last) {
      val = val + *first;   // or: val = binary_op(val,*first)
      *++result = val;
    }
    ++result;
  }
  return result;
}

没错，中间值是用输入数据的类型计算的！！不要问我怎么知道的！！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//Code by Lucida
#include<bits/stdtr1c++.h>
typedef long long int64;
namespace IO
{
	template <class T> inline void get(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
	}
	template <> inline void get<char>(char &x) {
		while(x=getchar(),((x<'0' || '9'<x) && (x<'a' || 'z'<x) && (x<'A' || 'Z'<x)));
	}
	template <> inline void get<char*>(char *&x) {
		char *cp=x;
		while(*cp++=getchar(),(*cp!=' ' && *cp!='\r' && *cp!='\n' && *cp!=EOF));
		*--cp=0;
	}

	template <class T> inline void put(T x) {
		if(!x)
			putchar('0');
		else {
			if(x<0) {
				putchar('-');
				x=-x;
			}
			static char stack[30]={0};
			char *top=stack;
			for(;x;x/=10) *++top=x%10+'0';
			while(*top) putchar(*top--);
		}
	}
	template <> inline void put<char>(char x) {
		putchar(x);
	}
	template <> inline void put<char*>(char* x) {
		while(*x)
			putchar(*x++);
	}
}

template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

using std::swap;
using std::max;
using std::min;
using IO::get;
using IO::put;


using std::upper_bound;
using std::partial_sum;

const int MAXN=1e6+11;
int main() {
//	freopen("input","r",stdin);
	static int64 pref[MAXN],a[MAXN];
	int K,Q;get(K),get(Q);
	int64 sum=0;
	for(int i=0;i<K;++i) {
		get(a[i]);
		(sum+=(int64)a[i]*i%(K-1))%=(K-1);
	}
	if(sum!=0) {
		a[sum]--;
	}
	partial_sum(a,a+K,pref);
	for(int i=1;i<=Q;++i) {
		int64 x;get(x);
		int p=upper_bound(pref,pref+K,x)-pref;
		p=p==K?-1:p;
		put(p),put('\n');
	}
	return 0;
}