当垃圾已经成为一种常态233333

A.旋转子段

考场上的$n^2$手残少了20分，555  (主要是因为实在打不出来$n^3$的做法所以写不了对拍？ccc为什么考场上没有想起有reverse()这么毒瘤的操作啊)

很显然要反转的区间两端一定是一对$i,a[i]$(具体谁在左谁在右看大小关系)，因为如果不是的话它俩没啥用就完全可以去掉。

所以枚举所有的i和a[i]不断更新最优解就能得到答案，那么只要能够$O(1)$查询答案复杂度就可以保证了。不妨设当前枚举到的i<a[i]，那么我们要查询的固定点个数可以分成三部分：$[1,i-1],[i,a[i]],[a[i]+1,n]$。前后两部分的贡献是静态的，直接预处理一个前缀和就行。中间这段需要考虑反转后哪些点成为了固定点，我们可以将所有的${i,a[i]}$二元组按照中轴分类，对于每类按照区间长度排序，这样就能查区间内又包含多少个能作出贡献的区间了。怎么按照中轴分类？第一关键字按$i+a[i]$排序就好了。

#include
      
       #include
       
        #include
        
         #include
         
          #define re registerusing namespace std;const int N=500005;int a[N],pos[N],sum[N],ans,n,maxx;int posl,posr;struct qj{    int l,r,len,rk,id;}q[N];bool cmp(qj x,qj y){    return x.l+x.r==y.l+y.r?(x.len
          
         
        
       
      

B.走格子

考场第一眼：可以疯狂连边跑最短路

第二眼：第一眼想的是什么玩意这么复杂的规则显然是暴搜剪枝题

第三眼：那么我们开始搜叭！

 

然后正解就是建图跑最短路。

没什么可说的，预处理每个格子上下左右的第一面墙，以及离最近的墙的距离，建图dj。很考验码力的英语作文题

(只要你别像博主一样打错最短路其实没那么难调)

#include
      
       #include
       
        #include
        
         #include
         
          #define pa pair
          
           using namespace std;int n,m,mp[505][505],sx,sy,ex,ey;int dx[5]={
    0,1,0,-1},    dy[5]={
    1,0,-1,0};int len[505][505],U[505][505],D[505][505],L[505][505],R[505][505];int id(int i,int j){    return (i-1)*m+j;}int S,T;queue
           
             q;void ins(int x,int y,int ds){ if(mp[x][y]==2&&!len[x][y]) len[x][y]=ds,q.push(make_pair(x,y));}int to[3200005],nxt[3200005],head[3200005],tot,d[3200005];void add(int x,int y,int z,int op){ to[++tot]=y; nxt[tot]=head[x]; d[tot]=z; head[x]=tot; if(op)add(y,x,z,0);}void bfs(){ while(!q.empty()) { int x=q.front().first,y=q.front().second; q.pop(); for(int i=0;i<4;i++) ins(x+dx[i],y+dy[i],len[x][y]+1); }}void graph(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]==2) { if(mp[i][j-1]==1)L[i][j]=id(i,j); else L[i][j]=L[i][j-1]; if(mp[i-1][j]==1)U[i][j]=id(i,j); else U[i][j]=U[i-1][j]; } for(int i=n;i;i--) for(int j=m;j;j--) if(mp[i][j]==2) { if(mp[i][j+1]==1)R[i][j]=id(i,j); else R[i][j]=R[i][j+1]; if(mp[i+1][j]==1)D[i][j]=id(i,j); else D[i][j]=D[i+1][j]; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]==2) { if(mp[i][j+1]==2)add(id(i,j),id(i,j+1),1,1); if(mp[i+1][j]==2)add(id(i,j),id(i+1,j),1,1); if(L[i][j]!=id(i,j))add(id(i,j),L[i][j],len[i][j],0); if(R[i][j]!=id(i,j))add(id(i,j),R[i][j],len[i][j],0); if(U[i][j]!=id(i,j))add(id(i,j),U[i][j],len[i][j],0); if(D[i][j]!=id(i,j))add(id(i,j),D[i][j],len[i][j],0); }}int vis[1000005],dis[1000005];void dj(){ priority_queue
            
              Q; memset(dis,0x3f,sizeof(dis)); Q.push(make_pair(0,S)); dis[S]=0; while(!Q.empty()) { int x=Q.top().second; Q.pop(); if(vis[x])continue; vis[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(dis[y]>dis[x]+d[i]) { dis[y]=dis[x]+d[i]; Q.push(make_pair(-dis[y],y)); } } }}int main(){ scanf("%d%d",&n,&m); char str[505]; for(int i=1;i<=n;i++) { scanf("%s",str+1); for(int j=1;j<=m;j++) { if(str[j]=='#')mp[i][j]=1,q.push(make_pair(i,j)); else mp[i][j]=2; if(str[j]=='C')sx=i,sy=j; else if(str[j]=='F')ex=i,ey=j; } } S=id(sx,sy);T=id(ex,ey); bfs();graph();dj(); /*for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<
             
              <<' '; puts(" "); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<
              
               <<' '; puts(" "); }*/ if(dis[T]==0x3f3f3f3f)puts("no"); else cout<
               
                <
               
              
             
            
           
          
         
        
       
      

 

C.柱状图

感觉看出屋顶高度与总代价的关系是一个单峰函数这点确实是瓶颈，只要得到这个性质直接上三分+暴力统计答案就能拿到60分。

剩下的还是戳上方题解吧，树状数组维护$h_i-i$和$h_i+i$确实想不到啊……绝对值不好处理可以排个序按照与屋顶的关键值($h_x-x||h_x+x$)的大小关系分成两类处理，屋顶左侧和右侧的点都是这样，所以要分四类。

随着屋顶的右移，右侧点的信息要拿出来放到左侧，一个小细节。复杂度$O(nlog^nlog^{maxh})$

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;#define pa pair
           
            const int N=100005;int n;ll h[N],ans=2e15;struct info{ ll val;int id; friend bool operator < (info x,info y) { return x.val
            
             y)return make_pair(0,0); pa tmp1=query(y),tmp2=query(x-1); return make_pair(tmp1.first-tmp2.first,tmp1.second-tmp2.second); }}lbit,rbit;int sch(info *x,ll val){ int l=1,r=n; while(l+1
             
              >1; if(x[mid].val>val)r=mid; else l=mid; } if(x[r].val<=val)return r; else if(x[l].val<=val)return l; else return 0;}ll cacl(int x,ll he){ ll res=abs(h[x]-he); int pos=sch(L,he-x); pa cost=lbit.query(pos); res+=(he-1LL*x)*cost.second-cost.first; cost=lbit.qjquery(pos+1,n); res+=cost.first-(he-1LL*x)*cost.second; pos=sch(R,he+x); cost=rbit.query(pos); res+=(he+1LL*x)*cost.second-cost.first; cost=rbit.qjquery(pos+1,n); res+=cost.first-(he+1LL*x)*cost.second; return res;}int main(){ //freopen("dt.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&h[i]); for(int i=1;i<=n;i++) { L[i].val=h[i]-i,R[i].val=h[i]+i; L[i].id=R[i].id=i; } sort(L+1,L+n+1);sort(R+1,R+n+1); for(int i=1;i<=n;i++) lrk[L[i].id]=i,rrk[R[i].id]=i; for(int i=1;i<=n;i++) rbit.add(rrk[i],R[rrk[i]].val,1); for(int i=1;i<=n;i++) { rbit.add(rrk[i],-R[rrk[i]].val,-1); ll lside=max((ll)i,(n-i+1)*1LL),rside=2e9; while(lside+1
              
               >1,lmid=mid-1,rmid=mid; ll lc=cacl(i,lmid),rc=cacl(i,rmid); if(lc>=rc)lside=mid; else rside=mid; } ans=min(ans,cacl(i,lside)); ans=min(ans,cacl(i,rside)); lbit.add(lrk[i],L[lrk[i]].val,1); } cout<
               
                <