T1

考场打了个$O(n^2)$的暴力，成功水到70分，由于数据范围是假的，所以被干掉了15分，正解很优秀，要用到其他人正常$O(n^2)$旋转中心的思路，我这么说当时是因为我的$O(n^2)$很清奇咯，我们很容易知道对于一个旋转区间，如果他的两个端点被翻转之后都不能变为固定点，那我们完全可以缩小区间范围，毕竟翻转区间越长，你破坏原本固定点的概率越大，所以我们从头到尾先扫一遍，记录可以使这个点翻转之后成为固定点的区间，把旋转中心是同一个的扔进同一个$vector$中，由于旋转中心是$frac{l+r}{2}$，不是整数不可做的样子，所以我们就不除2了，一样的用，其实事实上每个$vector$的$size$代表了区间个数，我们可以翻一个，翻两个，翻$size$个，所以说，我们按区间长度由小到大让元素有序，枚举$size$时候的贡献就是$sum[n]-(sum[r]-sum[l-1])+j+1$，$sum[i]$代表前$i$个点中固定点的个数，对所有的贡献取$max$既可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<algorithm>
 5 #define maxn 500100
 6 using namespace std;
 7 struct node{
 8     int num,pos;
 9 }a[maxn];
10 bool operator < (const node &a,const node &b)
11 {
12     return (a.pos-a.num)<(b.pos-b.num);
13 }
14 int n,ans;
15 int sum[maxn];
16 vector <node> b[maxn*2];
17 int main()
18 {
19     scanf("%d",&n);
20     for(int i=1;i<=n;++i)
21     {
22         scanf("%d",&a[i].num);  a[i].pos=i;
23         if(a[i].num>a[i].pos)  swap(a[i].num,a[i].pos);
24         if(a[i].num==a[i].pos)  sum[i]++;
25         sum[i]+=sum[i-1];  b[a[i].num+a[i].pos].push_back(a[i]);
26     }
27     for(int i=1;i<=2*n;++i)  sort(b[i].begin(),b[i].end());
28     for(int i=1;i<=2*n;++i)
29         for(int j=0;j<b[i].size();++j)
30         {
31             int da=sum[n]-(sum[b[i][j].pos]-sum[b[i][j].num-1])+j+1;
32             ans=max(da,ans);
33         }
34     printf("%d
",ans);
35     return 0;
36 }

View Code

T2

这题在$Lrefrain$说建边跑最短路之后我瞬间就清醒了，什么sbzz题啊，qnmd吧，太可怕了，bfs搜每一个墙，给每个空白地四面的四面墙之间连边，注意一一对应关系，直接跑$SPFA$就可以了

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<vector>
  5 #include<queue>
  6 #include<cmath>
  7 #define maxn 510
  8 #define bh(i,j,m)  ((i-1)*m+j)
  9 using namespace std;
 10 int n,m,js,qd,zd;
 11 int head[maxn*maxn],to[maxn*maxn*20],xia[maxn*maxn*20],w[maxn*maxn*20],dis[maxn*maxn];
 12 int a[maxn][maxn];
 13 int c[maxn][maxn][6];
 14 bool pd[maxn*maxn];
 15 char b[maxn];
 16 vector <int> hang;
 17 vector <int> lie;
 18 void add(int x,int y,int z)
 19 {
 20     to[++js]=y;  xia[js]=head[x];  w[js]=z;  head[x]=js;
 21 }
 22 void search(int x,int y)
 23 {
 24     int xx=x,yy=y,bhh=bh(x,y,m);
 25     while(1)
 26     {
 27         ++xx;
 28         if(a[xx][yy]==1||xx>n)  break;
 29         c[xx][yy][++c[xx][yy][0]]=bhh;
 30     }
 31     xx=x;  yy=y;
 32     while(1)
 33     {
 34         --xx;
 35         if(a[xx][yy]==1||xx<1)  break;
 36         c[xx][yy][++c[xx][yy][0]]=bhh;
 37     }
 38     xx=x;  yy=y;
 39     while(1)
 40     {
 41         --yy;
 42         if(a[xx][yy]==1||yy<1)  break;
 43         c[xx][yy][++c[xx][yy][0]]=bhh;
 44     }
 45     xx=x;  yy=y;
 46     while(1)
 47     {
 48         ++yy;
 49         if(a[xx][yy]==1||yy>m)  break;
 50         c[xx][yy][++c[xx][yy][0]]=bhh;
 51     }
 52 }
 53 void spfa(int xx)
 54 {
 55     memset(dis,0x7f,sizeof(dis));
 56     queue <int> que;  dis[xx]=0;  que.push(xx);  pd[xx]=1;
 57     while(!que.empty())
 58     {
 59         int ls=que.front();  que.pop();  pd[ls]=0;
 60         for(int i=head[ls];i;i=xia[i])
 61         {
 62             int lss=to[i];
 63             if(dis[ls]+w[i]<dis[lss])
 64             {
 65                 dis[lss]=dis[ls]+w[i];
 66                 if(!pd[lss])  {que.push(lss);  pd[lss]=1;}
 67             }
 68         }
 69     }
 70 }
 71 int main()
 72 {
 73     scanf("%d%d",&n,&m);
 74     for(int i=1;i<=n;++i)
 75     {
 76         scanf("%s",b+1);
 77         for(int j=1;j<=m;++j)
 78         {
 79             if(b[j]=='#')  {a[i][j]=1;  hang.push_back(i);  lie.push_back(j);}
 80             else
 81             {
 82                 if(b[j]=='C')  qd=bh(i,j,m);
 83                 if(b[j]=='F')  zd=bh(i,j,m);
 84                 a[i][j]=2;
 85                 int bh1=bh(i,j,m);
 86                 if(a[i][j-1]==2)
 87                     {int bh2=bh(i,j-1,m);  add(bh1,bh2,1);  add(bh2,bh1,1);}
 88                 if(a[i-1][j]==2)
 89                     {int bh2=bh(i-1,j,m);  add(bh1,bh2,1);  add(bh2,bh1,1);}
 90             }
 91         }
 92     }
 93     for(int i=0;i<hang.size();++i)  search(hang[i],lie[i]);
 94     for(int i=1;i<=n;++i)
 95     {
 96         for(int j=1;j<=m;++j)
 97         {
 98             if(a[i][j]==1)  continue;
 99             for(int o=1;o<=4;++o)
100                 for(int p=o+1;p<=4;++p)
101                 {
102                     int x1,y1,x2,y2,bhh=bh(i,j,m),jl1,jl2,zd1,zd2;
103                     if(c[i][j][o]%m)  {x1=c[i][j][o]/m+1;  y1=c[i][j][o]%m;}
104                     else  {x1=c[i][j][o]/m;  y1=m;}
105                     if(c[i][j][p]%m)  {x2=c[i][j][p]/m+1;  y2=c[i][j][p]%m;}
106                     else  {x2=c[i][j][p]/m;  y2=m;}
107                     if(x1==i)
108                     {
109                         jl1=abs(j-y1);
110                         if(y1>j)  zd2=bh(x1,y1-1,m);
111                         else zd2=bh(x1,y1+1,m);
112                     }
113                     if(y1==j)
114                     {
115                         jl1=abs(i-x1);
116                         if(x1>i)  zd2=bh(x1-1,y1,m);
117                         else  zd2=bh(x1+1,y1,m);
118                     }
119                     if(x2==i)
120                     {
121                         jl2=abs(j-y2);
122                         if(y2>j)  zd1=bh(x2,y2-1,m);
123                         else  zd1=bh(x2,y2+1,m);
124                     }
125                     if(y2==j)
126                     {
127                         jl2=abs(i-x2);
128                         if(x2>i)  zd1=bh(x2-1,y2,m);
129                         else  zd1=bh(x2+1,y2,m);
130                     }
131                     add(bhh,zd1,jl1);  add(bhh,zd2,jl2);
132                 }
133         }
134     }
135     spfa(qd);
136     printf("%d
",dis[zd]);
137     return 0;
138 }

View Code

T3

又是道看不懂题解的好题，太棒了，然后我就更棒的颓了标程，不过由于我不会证明单谷函数，除此之外就是恶心的数据结构乱搞，我又还想看一看dj继续颓一会，所以扔个板子就跑了，啊不，再扔个题解的链接

  1 //三分以该点为屋顶的屋顶高度
  2 //两个树状数组分别维护h[i]-i和h[i]+i
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<cstdio>
  6 #include<cmath>
  7 #define int long long
  8 #define maxn 100100
  9 using namespace std;
 10 int n,Ans=0xfffffffffffffff,maxx;
 11 int a[maxn],rankl[maxn],rankr[maxn];
 12 int lowbit(int x)
 13 {
 14     return x&(-x);
 15 }
 16 struct szsz{
 17     int c_cnt[maxn],c_sum[maxn];
 18     void add(int x,int w_num,int w_cnt)
 19     {
 20         for(;x<=n;x+=lowbit(x))  {c_cnt[x]+=w_cnt;  c_sum[x]+=w_num;}
 21     }
 22     pair <int,int> quary_qz(int x)
 23     {
 24         pair <int,int> ans=make_pair(1ll*0,1ll*0);
 25         for(;x>=1;x-=lowbit(x))  {ans.first+=c_sum[x];  ans.second+=c_cnt[x];}
 26         return ans;
 27     }
 28     pair <int,int> quary_qj(int x,int y)
 29     {
 30         if(x>y)  return make_pair(1ll*0,1ll*0);
 31         else
 32         {
 33             pair <int,int> ans1=quary_qz(x-1);  pair <int,int> ans2=quary_qz(y);
 34             return make_pair(ans2.first-ans1.first,ans2.second-ans1.second);
 35         }
 36     }
 37 }Left,Right;
 38 struct node{
 39     int num,pos;
 40     bool operator < (const node &a)const
 41     {
 42         return num<a.num;
 43     }
 44 }l[maxn],r[maxn];
 45 inline int read()
 46 {
 47     register int e=0,f=1;  register char ch=getchar();
 48     while(ch<'0'||ch>'9')
 49     {
 50         if(ch=='-')  f=-1;
 51         ch=getchar();
 52     }
 53     while(ch>='0'&&ch<='9')  {e=(e<<3)+(e<<1)+(ch^48);  ch=getchar();}
 54     return e*f;
 55 }
 56 int ef(node *p,int w)
 57 {
 58     int l=1ll*1,r=n;
 59     while(l+1<r)
 60     {
 61         int mid=(l+r)>>1;
 62         if(p[mid].num>w)  r=mid;
 63         else  l=mid;
 64     }
 65     if(p[r].num<=w)  return r;
 66     else if(p[l].num<=w)  return l;
 67     else  return 0;
 68 }
 69 int hf(int pos,int height)
 70 {
 71     int ans=abs(height-a[pos]);
 72     pair <int,int> sum_c;  int efpos;
 73     efpos=ef(l,height-pos);
 74     sum_c=Left.quary_qz(efpos);
 75     ans+=sum_c.second*(height-pos)-sum_c.first;
 76     sum_c=Left.quary_qj(efpos+1,n);
 77     ans+=sum_c.first-sum_c.second*(height-pos);
 78     efpos=ef(r,height+pos);
 79     sum_c=Right.quary_qz(efpos);
 80     ans+=sum_c.second*(height+pos)-sum_c.first;
 81     sum_c=Right.quary_qj(efpos+1,n);
 82     ans+=sum_c.first-sum_c.second*(height+pos);
 83     return ans;
 84 }
 85 main()
 86 {
 87     n=read();
 88     for(int i=1;i<=n;++i)  {a[i]=read();  maxx=max(maxx,a[i]);}
 89     for(int i=1;i<=n;++i)  {l[i]=(node){a[i]-i,i};  r[i]=(node){a[i]+i,i};}
 90     sort(l+1,l+n+1);  sort(r+1,r+n+1);
 91     for(int i=1;i<=n;++i)  {rankl[l[i].pos]=i;  rankr[r[i].pos]=i;}
 92     for(int i=1;i<=n;++i)  {Right.add(rankr[i],r[rankr[i]].num,1ll*1);}
 93     for(int i=1;i<=n;++i)
 94     {
 95         Right.add(rankr[i],-r[rankr[i]].num,-1ll*1);
 96         int hi_min=max(i,n-i+1),hi_max=maxx+n;
 97         while(hi_min+1<hi_max)
 98         {
 99             int mid=(hi_min+hi_max)>>1;
100             int cost1=hf(i,mid-1),cost2=hf(i,mid);
101             if(cost1>=cost2)  hi_min=mid;
102             else  hi_max=mid;
103         }
104         Ans=min(Ans,hf(i,hi_min));  Ans=min(Ans,hf(i,hi_max));
105         Left.add(rankl[i],l[rankl[i]].num,1ll*1);
106     }
107     printf("%lld
",Ans);
108     return 0;
109 }

View Code