比较复杂的一题..
不管是二分答案还是直接做, 都需要压缩树链
- /*
- 给定 n 种怪物, 每个怪物有属性 a[i]
- 打死第 i 种怪物后, 第 i 只怪物会分裂成 a[i] 个第 i-1 种怪
- 如果打死的是第 1 种, 那么获得经验 a[1]
- 现在遇到的是一只第 n 种怪, 有体力 w, 打死一只怪要一点体力, 问最多获得多少经验
- 直接求比较麻烦, 由于答案具有单调性, 所以二分答案即可
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define INF 1000000007
- #define maxn 100005
- ll a[maxn],c[maxn],s[maxn],g[maxn],n,q,w;
- int main(){
- int tn;
- cin>>q>>tn;
- cin>>a[1];
- c[1]=1,n=1;
- for(int i=2;i<=tn;i++){
- ll ta;
- scanf("%lld",&ta);
- if(ta>1){a[++n]=ta;c[n]=1;}
- else ++c[n];
- }
- s[1]=c[1],g[1]=a[1];
- tn=n;
- for(int i=2;i<=tn;i++){
- ll t=(ll)s[i-1]*a[i]+c[i];// 第 i 层的规模
- if(t>=INF){
- for(int j=i+1;j<=tn;j++)
- c[i]+=c[j];
- n=i;
- s[n]=g[n]=INF;
- break;
- }
- s[i]=t;
- g[i]=g[i-1]*a[i];
- }
- while(q--){
- int k;
- scanf("%d",&k);
- if(k>s[n]){
- cout<<g[n]<<endl;
- continue;
- }
- ll ans=0;
- for(int i=n;k>=c[i] && i>1;i--){
- k-=c[i];
- ans+=(k/s[i-1])*g[i-1];
- k%=s[i-1];
- }
- cout<<ans<<endl;
- }
- int a;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2992174.html