10.05T2 二项式展开+二分答案+差分数组
2021-05-17 21:28
标签:情况 图片 告诉 iostream 答案 review shu code 分享图片 ){
48 add[j]+=x*(p-Pow[i-j]);
49 }
50 }
51 }
52 else{
53 memset(S,0,sizeof S);
54 memset(T,0,sizeof T);
55 memset(siz,0,sizeof siz);
56 for(long long i=n,x,now;i>=1;i--){
57 Siz+=siz[i];sum=Siz*p;now=1;
58 for(long long j=0;ji){
59 S[j]+=T[i][j];
60 sum-=now*S[j];
61 }
62 if(sum>val[i])continue;
63 x=(val[i]-sum)/p+1;used+=x;
64 if(used>k)return false;
65 long long lim=i-dis,fla=1;now=ksm(i,m);lim=max(lim,0ll);
66 for(long long j=0;j1,now/=i){
67 T[lim][j]-=fla*x*c[m][j]*now;
68 S[j]+=x*fla*c[m][j]*now;
69 }
70 Siz+=x;siz[lim]-=x;
71 }
72 }
73 return true;
74 }
75 long long ans;
76 int main(){
77 n=read(),m=read(),k=read();
78 pre();
79 for(long long i=1;iread();
80 for(long long i=1;iksm(i,m);
81 long long l=1,r=1000000;
82 while(lr){
83 long long mid=l+r>>1;
84 if(check(mid))r=mid-1,ans=mid;
85 else l=mid+1;
86 }
87 coutans;
88 return 0;
89 } over 10.05T2 二项式展开+二分答案+差分数组 标签:情况 图片 告诉 iostream 答案 review shu code 分享图片 原文地址:https://www.cnblogs.com/saionjisekai/p/9745898.htmlDescription
御坂美琴正在进行能力测试,她手上有 k 枚硬币,她面前 50 米有 n 个相邻放置的自动售货机,编号为 1 到 n,且每个售货机都有一个耐久度 vi ,为了使测试更有难度,考官钦定了一个值 m 。御坂美琴可以精准击中任意一个售货机,且排在被命中的售货机前的售货机也会受到溅射伤害。
具体来说,若御坂美琴使用 p 的攻击力取投掷硬币,被击中的售货机 i 会受到 p 的伤害,且排在此售货机前的第 j 个售货机会受到max(0,p−(i−j)m), 的伤害。
为了完成能力测试,她需要在最小化 p 的情况下,合理使用这些硬币使得每一个售货机的耐久度都小于0 。
你能告诉御坂美琴这个最小的 p 为多少吗?
Input
第二行 n 个整数表示 vi 。Output
Sample Input
Sample Output
Hint
Source
1 #include
下一篇:初识c++