B. Build a Boat

首先求出每块船舱的面积$S$，然后进行$m$次二分，得到每个切割线的位置。

为了计算某个切割线形成的区域的面积，需要将多边形整理成上边界和下边界，分别二分出断点位置，中间部分用叉积前缀和$O(1)$回答。

时间复杂度$O(n+m\log^2n)$。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=400010;const double eps=1e-9;int n,i,j,k,o,b[N],c[N],cb,cc,ans,lim,loc[N][2];ll all;double each,s[N],mi,ma;inline int sgn(double x){  if(x>eps)return 1;  if(x<-eps)return -1;  return 0;}struct P{  double x,y;  P(){}  P(double _x,double _y){x=_x,y=_y;}  P operator+(const P&b){return P(x+b.x,y+b.y);}  P operator-(const P&b){return P(x-b.x,y-b.y);}  P operator*(double b){return P(x*b,y*b);}}a[N];inline double cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}inline P intersection(P a,P b,P p,P q){  double U=cross(p-a,q-p),D=cross(b-a,q-p);  return a+(b-a)*(U/D);}inline double cal(double x){  if(sgn(x-a[b[1]].x)<=0)return 0;//x>b[1]  if(sgn(x-a[b[cb]].x)>=0)return all;//x
        
         >1;    if(a[b[mid]].x
         
          >1;    if(a[c[mid]].x
          
           r)r+=n; double ret=s[r-1]-s[l-1]; P X=intersection(a[b[A]],a[b[A+1]],P(x,-1),P(x,1)), Y=intersection(a[c[B]],a[c[B+1]],P(x,-1),P(x,1)); ret+=cross(X,a[b[A]])+cross(a[c[B]],Y)+cross(Y,X); return ret;}inline double solve(double goal){ double l=mi,r=ma,mid; for(int i=0;i<60;i++){ mid=(l+r)/2; if(fabs(cal(mid))
           
            0)j=i; for(i=o=1;i<=n;i++)if(sgn(a[i].x-a[o].x)>0||sgn(a[i].x-a[o].x)==0&&sgn(a[i].y-a[o].y)>0)o=i; while(1){ b[++cb]=j; if(j==o)break; k=j-1; if(k<1)k+=n; j=k; } for(i=j=1;i<=n;i++)if(sgn(a[i].x-a[j].x)<0||sgn(a[i].x-a[j].x)==0&&sgn(a[i].y-a[j].y)<0)j=i; for(i=o=1;i<=n;i++)if(sgn(a[i].x-a[o].x)>0||sgn(a[i].x-a[o].x)==0&&sgn(a[i].y-a[o].y)<0)o=i; mi=1e9;ma=-mi; for(i=1;i<=n;i++)mi=min(mi,a[i].x),ma=max(ma,a[i].x); while(1){ c[++cc]=j; if(j==o)break; k=j+1; if(k>n)k-=n; j=k; } //for(i=1;i<=cb;i++)printf("(%.1f,%.1f) ",a[b[i]].x,a[b[i]].y);puts(""); //for(i=1;i<=cc;i++)printf("(%.1f,%.1f) ",a[c[i]].x,a[c[i]].y);puts(""); printf("%d\n",ans); for(i=1;i
           
          
         
        
       
      
     

　　

C. Compiler

只需要两个寄存器，设$f[i][j]$表示两个寄存器的值分别为$i,j$的最少步数，只有形如$a=a+kb(1\leq k\leq 2)$的操作有用，DP求出最优方案即可。

最坏情况下需要步数为$39$步，满足题目所给$40$步的限制。

时间复杂度$O(n^2)$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=260,K=2;int n=255,i,j,k,x,y,z,t,f[N][N],ans[N],mx;vector
         
          g[N][N],fin[N];int main(){  for(i=1;i<=n;i++)ans[i]=N;  for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=N;  f[1][1]=3;  g[1][1].push_back("ST X");  g[1][1].push_back("ST Y");  for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]
          
           z){ f[x][y]=z; g[x][y]=g[i][j]; g[x][y].push_back("PH X"); for(t=1;t<=k;t++)g[x][y].push_back("PH X"); for(t=1;t<=k;t++)g[x][y].push_back("AD"); g[x][y].push_back("PL X"); } } if(i+j*k<=n){ x=i+j*k,y=j; if(f[x][y]>z){ f[x][y]=z; g[x][y]=g[i][j]; g[x][y].push_back("PH X"); for(t=1;t<=k;t++)g[x][y].push_back("PH Y"); for(t=1;t<=k;t++)g[x][y].push_back("AD"); g[x][y].push_back("PL X"); } } if(j+i*k<=n){ x=i,y=j+i*k; if(f[x][y]>z){ f[x][y]=z; g[x][y]=g[i][j]; g[x][y].push_back("PH Y"); for(t=1;t<=k;t++)g[x][y].push_back("PH X"); for(t=1;t<=k;t++)g[x][y].push_back("AD"); g[x][y].push_back("PL Y"); } } if(j+j*k<=n){ x=i,y=j+j*k; if(f[x][y]>z){ f[x][y]=z; g[x][y]=g[i][j]; g[x][y].push_back("PH Y"); for(t=1;t<=k;t++)g[x][y].push_back("PH Y"); for(t=1;t<=k;t++)g[x][y].push_back("AD"); g[x][y].push_back("PL Y"); } } } if(ans[i]>f[i][j]){ ans[i]=f[i][j]; fin[i]=g[i][j]; fin[i].push_back("DI X"); } if(ans[j]>f[i][j]){ ans[j]=f[i][j]; fin[j]=g[i][j]; fin[j].push_back("DI Y"); } } for(i=1;i<=n;i++)if(ans[i]>mx)mx=ans[i]; fin[0].push_back("ZE X"); fin[0].push_back("DI X"); //printf("%d",mx); scanf("%d",&n); for(i=0;i
           
            <
            
             <
            
           
          
         
        
       
      
     

　　

G. Gondolas

首先可以将时间都模$2T$，并将时间离散化，得到$O(n)$个时间，显然只在这些时间放置缆车最优。

枚举最早的缆车的时间，从前往后考虑每个时间是否设置缆车，则相邻两个缆车间的贡献是确定的，可以用前缀和$O(1)$求出。

设$f[i][j]$表示考虑前$i$个时间，时间$i$放置缆车，且一共放了$j$个缆车时，等待时间总和的最小值。

枚举上一个缆车的时间进行转移，可以斜率优化，自然也满足决策单调性，分治求解即可。

时间复杂度$O(n^2g\log n)$。

#include
     
      #include
      
       const int N=405,inf=~0U>>1;int n,T,m,i,j,a[N],b[N],cnt,c[N],s[N],f[N][N],ans=inf;inline void up(int&a,int b){a>b?(a=b):0;}inline int cal(int l,int r){//[l..r] to r  return b[r]*(c[r]-c[l-1])-s[r]+s[l-1];}void solve(int l,int r,int dl,int dr,int p){  int m=(l+r)>>1,dm=dl,&dp=f[p][m];  for(int i=dl;i<=dr&&i
       
        
         m)solve(m+1,r,dm,dr,p);}inline void solve(int st){  int i,j;  for(i=1;st+i-1<=cnt&&i<=m;i++){    for(j=1;j<=cnt;j++)f[i][j]=inf;    if(i==1)f[1][st]=cal(1,st);else solve(st+i-1,cnt,1,cnt,i);    for(j=st+i-1;j<=cnt;j++)if(f[i][j]
         
          a[i-1])b[++cnt]=a[i];  for(i=1;i<=n;i++){    for(j=1;j<=cnt;j++)if(a[i]==b[j])break;    c[j]++,s[j]+=a[i];  }  for(i=1;i<=cnt;i++)c[i]+=c[i-1],s[i]+=s[i-1];  for(i=1;i<=cnt;i++)solve(i);  printf("%d",ans);}
         
        
       
      
     

　　

K. Compensation

对于正常以及延误两种情况分别预处理出$f[i][j]$表示于时刻$j$到达站点$i$，最早可以于什么时候到达站点$i+1$，那么可以在$O(n)$的时间内求出到达目的地的最早时间。

枚举每个起点为$1$的火车，计算第一步搭乘它且不延误时到达$n$的最早时间$A$以及与$S_i$时刻到达$1$号站点，在延误情况下到达$n$的最早时间$B$，若$A+1800\leq B$，则可以利用这辆火车延误进行索赔。

时间复杂度$O(nm)$。

#include
     
      const int N=110,M=173000,inf=1000000000;int n,m,i,e[M][4],ans=inf;inline void up(int&a,int b){a>b?(a=b):0;}struct P{  int f[N][M];  void init(){    for(int i=1;i<=n;i++)for(int j=0;j