当垃圾已经成为一种常态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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
const int N=;
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<y.len):(x.l+x.r<y.l+y.r);
}
int main()
{
scanf("%d",&n);
for(re int i=;i<=n;i++)
{
scanf("%d",&a[i]);
q[i].l=min(i,a[i]),q[i].r=max(i,a[i]),q[i].len=q[i].r-q[i].l+,q[i].id=i;
if(a[i]==i)sum[i]=sum[i-]+;
else sum[i]=sum[i-];
}
sort(q+,q+n+,cmp);
int last=;
for(re int i=;i<=n;i++)
{
if(q[i].l+q[i].r!=last)
{
last=q[i].l+q[i].r;
q[i].rk=;
continue;
}
q[i].rk=q[i-].rk+;
}
for(re int i=;i<=n;i++)
ans=max(ans,sum[q[i].l-]+q[i].rk+sum[n]-sum[q[i].r]);
cout<<ans<<endl;
return ;
}
话说这题你们为什么要用vector啊？
B.走格子
考场第一眼：可以疯狂连边跑最短路
第二眼：第一眼想的是什么玩意这么复杂的规则显然是暴搜剪枝题
第三眼：那么我们开始搜叭！
然后正解就是建图跑最短路。
没什么可说的，预处理每个格子上下左右的第一面墙，以及离最近的墙的距离，建图dj。很考验码力的英语作文题
(只要你别像博主一样打错最短路其实没那么难调)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define pa pair<int,int>
using namespace std;
int n,m,mp[][],sx,sy,ex,ey;
int dx[]={,,,-},
dy[]={,,-,};
int len[][],U[][],D[][],L[][],R[][];
int id(int i,int j)
{
return (i-)*m+j;
}
int S,T;
queue<pa> q;
void ins(int x,int y,int ds)
{
if(mp[x][y]==&&!len[x][y])
len[x][y]=ds,q.push(make_pair(x,y));
}
int to[],nxt[],head[],tot,d[];
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,);
}
void bfs()
{
while(!q.empty())
{
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=;i<;i++)
ins(x+dx[i],y+dy[i],len[x][y]+);
}
}
void graph()
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]==)
{
if(mp[i][j-]==)L[i][j]=id(i,j);
else L[i][j]=L[i][j-];
if(mp[i-][j]==)U[i][j]=id(i,j);
else U[i][j]=U[i-][j];
}
for(int i=n;i;i--)
for(int j=m;j;j--)
if(mp[i][j]==)
{
if(mp[i][j+]==)R[i][j]=id(i,j);
else R[i][j]=R[i][j+];
if(mp[i+][j]==)D[i][j]=id(i,j);
else D[i][j]=D[i+][j];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]==)
{
if(mp[i][j+]==)add(id(i,j),id(i,j+),,);
if(mp[i+][j]==)add(id(i,j),id(i+,j),,);
if(L[i][j]!=id(i,j))add(id(i,j),L[i][j],len[i][j],);
if(R[i][j]!=id(i,j))add(id(i,j),R[i][j],len[i][j],);
if(U[i][j]!=id(i,j))add(id(i,j),U[i][j],len[i][j],);
if(D[i][j]!=id(i,j))add(id(i,j),D[i][j],len[i][j],);
}
}
int vis[],dis[];
void dj()
{
priority_queue<pa> Q;
memset(dis,0x3f,sizeof(dis));
Q.push(make_pair(,S));
dis[S]=;
while(!Q.empty())
{
int x=Q.top().second;
Q.pop();
if(vis[x])continue;
vis[x]=;
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[];
for(int i=;i<=n;i++)
{
scanf("%s",str+);
for(int j=;j<=m;j++)
{
if(str[j]=='#')mp[i][j]=,q.push(make_pair(i,j));
else mp[i][j]=;
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<<mp[i][j]<<' ';
puts(" ");
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<R[i][j]<<' ';
puts(" ");
}*/
if(dis[T]==0x3f3f3f3f)puts("no");
else cout<<dis[T]<<endl;
return ;
}
玄学数组大小
C.柱状图
感觉看出屋顶高度与总代价的关系是一个单峰函数这点确实是瓶颈，只要得到这个性质直接上三分+暴力统计答案就能拿到60分。
剩下的还是戳上方题解吧，树状数组维护$h_i-i$和$h_i+i$确实想不到啊……绝对值不好处理可以排个序按照与屋顶的关键值($h_x-x||h_x+x$)的大小关系分成两类处理，屋顶左侧和右侧的点都是这样，所以要分四类。
随着屋顶的右移，右侧点的信息要拿出来放到左侧，一个小细节。复杂度$O(nlog^nlog^{maxh})$
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define pa pair<ll,ll>
const int N=;
int n;
ll h[N],ans=2e15;
struct info
{
ll val;int id;
friend bool operator < (info x,info y)
{
return x.val<y.val;
}
}L[N],R[N];
int lrk[N],rrk[N];
#define lb(x) ( (x) & (-x) )
struct bit
{
ll sum[N],cnt[N];
ll add(int x,ll sumv,ll cntv)
{
for( ;x<=n;x+=lb(x))
sum[x]+=sumv,cnt[x]+=cntv;
}
pa query(int x)
{
pa res=make_pair(,);
for( ;x;x-=lb(x))
res.first+=sum[x],res.second+=cnt[x];
return res;
}
pa qjquery(int x,int y)
{
if(x>y)return make_pair(,);
pa tmp1=query(y),tmp2=query(x-);
return make_pair(tmp1.first-tmp2.first,tmp1.second-tmp2.second);
}
}lbit,rbit;
int sch(info *x,ll val)
{
int l=,r=n;
while(l+<r)
{
int mid=l+r>>;
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 ;
}
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+,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+,n);
res+=cost.first-(he+1LL*x)*cost.second;
return res;
} int main()
{
//freopen("dt.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld",&h[i]);
for(int i=;i<=n;i++)
{
L[i].val=h[i]-i,R[i].val=h[i]+i;
L[i].id=R[i].id=i;
}
sort(L+,L+n+);sort(R+,R+n+);
for(int i=;i<=n;i++)
lrk[L[i].id]=i,rrk[R[i].id]=i;
for(int i=;i<=n;i++)
rbit.add(rrk[i],R[rrk[i]].val,); for(int i=;i<=n;i++)
{
rbit.add(rrk[i],-R[rrk[i]].val,-);
ll lside=max((ll)i,(n-i+)*1LL),rside=2e9;
while(lside+<rside)
{
ll mid=lside+rside>>,lmid=mid-,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,);
}
cout<<ans<<endl;
return ;
}
疯狂make_pair