10.05T2 二项式展开+二分答案+差分数组

2021-05-17 21:28

阅读:378

标签:情况   图片   告诉   iostream   答案   review   shu   code   分享图片   

Description

御坂美琴正在进行能力测试
御坂美琴正在进行能力测试,她手上有 k 枚硬币,她面前 50 米有 n 个相邻放置的自动售货机,编号为 1 到 n,且每个售货机都有一个耐久度 vi ,为了使测试更有难度,考官钦定了一个值 m 。御坂美琴可以精准击中任意一个售货机,且排在被命中的售货机前的售货机也会受到溅射伤害。
具体来说,若御坂美琴使用 p 的攻击力取投掷硬币,被击中的售货机 i 会受到 p 的伤害,且排在此售货机前的第 j 个售货机会受到max(0,p(ij)m), 的伤害。
为了完成能力测试,她需要在最小化 p 的情况下,合理使用这些硬币使得每一个售货机的耐久度都小于0 。
你能告诉御坂美琴这个最小的 p 为多少吗?

Input

第一行三个整数分别表示 n,m ,k 。
第二行 n 个整数表示 vi 。

Output

一行一个整数表示最小的 p。

Sample Input

样例输入 1
3 2 1
1 4 5
样例输出1
6
样例解释 1
使用6的攻击力击中编号为3的售货机, 1号售货机会受到2的溅射伤害; 2号售货机会受到5的溅射伤害; 3号售货机会受到6的直接伤害。

Sample Output

 

Hint

技术分享图片
技术分享图片

Source

from liuxiao Trr
 
 
 
 
 
官方题解等于没有!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
技术分享图片
 
我的心态:
技术分享图片
算了不提了,这题我现在都没搞懂手抄的代码
等我懂了再来写题解吧(误
code:
 1 #include 2 #include 3 #include 4 #include 5 #define N 500005
 6 using namespace std;
 7 const long long inf=1e18;
 8 long long read(){
 9     long long s=0,f=1;
10     char t=getchar();
11     while(t‘0||t>9){
12         if(t==-)f=-1;
13         t=getchar();
14     }
15     while(t>=0&&t‘9){
16         s=(s1)+(s3)+t-0;
17         t=getchar();
18     }
19     return s*f;
20 }
21 long long ksm(long long a,long long b){
22     long long ans=1;
23     while(b){
24         if(b&1)ans=ans*a;
25         b>>=1;a=a*a;
26     }
27     if(ans0)return inf;
28     return ans;
29 }
30 long long c[30][30],n,m,k;
31 void pre(){
32     c[0][0]=1;
33     for(long long i=1;i3;i++){
34         c[i][i]=c[i][0]=1;
35         for(long long j=1;j1][j]+c[i-1][j-1];
36     }
37 }
38 long long add[N],val[N],Pow[N],S[N],T[N][4],siz[N];
39 bool check(long long p){
40     long long used=0,Siz=0,sum,dis=ceil(pow(p,1.0/m));
41     if(m>3){
42         memset(add,0,sizeof add);
43         for(long long i=n,x;i>=1;i--){
44             if(add[i]>val[i])continue;
45             x=(val[i]-add[i])/p+1;
46             used+=x;if(used>k)return false;
47             for(long long j=i-1;j>=1&&Pow[i-j]

){ 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.html


评论


亲,登录后才可以留言!