CF1067D Computer Game

迷南。 2022-01-07 14:19 177阅读 0赞

[link][]

### 题意： ###

有 n 道题，每个题可以做很多次但只能领悟一次，一开没有领悟任何题。

对于第 i 个题，正确率为 $p\_i$ 。领悟之前，做对这个题可以提升 $a\_i$ 的能力值；领悟之后，做对这个题可以提升 $b\_i$ 的能力值。（保证 $a\_i<b\_i$ ）

做对一个题，还可以领悟任意一个题（任选）。做错题后，什么都不会发生。

现在可以做 t 次题（同一题算多次），问最大能力值？ $n\\leq 10^5,t\\leq 10^\{10\}$

### 题解： ###

【一些吐槽】 由于考试数据水现场各种水过。大家都猜了一个错误的结论：领悟之前和之后都各只做一道题。

事实上领悟之后确实是只做一道题，选的一定是 $b\_ip\_i$ 最大的那个题，记这个值为 $mx$ ，但领悟之前就不是了，需要 dp 。

设 $f\_t$ 表示 t 时刻的最大能力值，方程$$\\begin\{aligned\}f\_\{t+1\}&=\\max \\\{p\_i\\times (a\_i+mx\\times t)+(1-p\_i)\\times f\_t\\\}\\\\f\_\{t+1\}&=\\max \\\{p\_ia\_i+p\_i\\times(mx\\times t-f\_t)\\\}+f\_t\\end\{aligned\}$$

这里有个性质：由于一轮的贡献不会超过 mx ，所以有$$\\begin\{aligned\}f\_\{t+1\}-f\_t &\\leq mx \\\\ \\Longleftrightarrow t\\times mx-f\_t &\\leq (t+1)\\times mx-f\_\{t+1\}\\end\{aligned\}$$

即 $mx\\times t-f\_t$ 是单调不减的。

那么把 $p\_ia\_i$ 看成截距， $p\_i$ 看成斜率， $f$ 的转移就相当于取若干一次函数的最大值，求下凸壳即可。 dp 的时候从左往右扫每条直线，用矩阵乘法和倍增优化转移。复杂度 $\\mathcal\{O\}(n\\log T)$ 。

### code: ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define rep(i,x,y) for (int i=(x);i<=(y);i++)
     3 #define ll long long
     4 #define db double
     5 
     6 using namespace std;
     7 
     8 const int N=1e5+10;
     9 int n,m; db mx,ans; ll t,cnt;
    10 
    11 const db eps=1e-10;
    12 const int dcmp(db x){
         return fabs(x)<eps?0:x<-eps?-1:1;}
    13 
    14 struct line{
    15     db k,b;
    16     line(db k=0,db b=0):k(k),b(b){}
    17     friend bool operator < (line x,line y){
    18         return dcmp(x.k-y.k)==0?dcmp(x.b-y.b)>0:dcmp(x.k-y.k)<0;
    19     }
    20 }p[N],q[N];
    21 
    22 struct mat{
    23     int n,m; db a[3][3];
    24     mat(int n=0,int m=0):n(n),m(m){memset(a,0,sizeof(a));}
    25     friend mat operator * (mat x,mat y){
    26         mat z(x.n,y.m);
    27         rep (i,0,z.n-1)
    28             rep (j,0,z.m-1)
    29                 rep (k,0,x.m-1) z.a[i][j]+=x.a[i][k]*y.a[k][j];
    30         return z;
    31     }
    32 }A,B,trs[35];
    33 
    34 db inter_x(line x,line y){
         return (y.b-x.b)/(x.k-y.k);}
    35 
    36 int main(){
    37     scanf("%d%lld",&n,&t);
    38     rep (i,1,n){
    39         int a,b; db c;
    40         scanf("%d%d%lf",&a,&b,&c);
    41         mx=max(mx,b*c),p[i]=line(c,a*c);
    42     }
    43     sort(p+1,p+1+n);
    44     rep (i,1,n) if (i==1||dcmp(p[i].k-p[i-1].k)!=0) q[++m]=p[i];
    45     n=0;
    46     rep (i,1,m){
    47         while (n>=2&&dcmp(inter_x(q[i],p[n])-inter_x(p[n],p[n-1]))<=0) n--;
    48         p[++n]=q[i];
    49     }
    50     cnt=0;
    51     A=mat(3,1); A.a[2][0]=1;
    52     for (int i=1;i<=n&&cnt<t;i++){
    53         db R=mx*cnt-A.a[0][0];
    54         while (i<n&&dcmp(inter_x(p[i],p[i+1])-R)<=0) i++;
    55         if (i<n) R=inter_x(p[i],p[i+1]);
    56         trs[0]=mat(3,3);
    57         trs[0].a[0][0]=1-p[i].k,trs[0].a[0][1]=p[i].k*mx,trs[0].a[0][2]=p[i].b;
    58         trs[0].a[1][1]=trs[0].a[1][2]=trs[0].a[2][2]=1;
    59         rep (j,1,33) trs[j]=trs[j-1]*trs[j-1];
    60         for (int j=33;~j;j--)
    61             if (cnt+(1ll<<j)<t){
    62                 B=trs[j]*A;
    63                 if (i==n||dcmp((cnt+(1ll<<j))*mx-B.a[0][0]-R)<=0) A=B,cnt+=1ll<<j;
    64             }
    65         cnt++,A=trs[0]*A;
    66     }
    67     printf("%.10lf\n",A.a[0][0]);
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/bestFy/p/10748008.html

[link]: https://codeforces.com/contest/1067/problem/D
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/a543c37cc45549d49e2ae7b92dff25e6.png