T1 旋转子段
这道题。。
我脑子进水了，一点点性质都没有看出来。
最基本的性质就是每个点到达固定点的方案一样。什么叫方案一样？就是它只能通过一种操作到达，实际上就是指它有固定的旋转中心。想到这一点，60分就拿到了。
考虑优化，这种做法哪里会出现问题呢？就是每次枚举旋转点时要枚举区间统计答案，而枚举区间的过程中又会有很多冗余计算，所以我们可以记录一下以某个点为坐标轴下，向两边扩展，只在ans改变处统计答案，用两个前缀和维护，一个统计旋转前固定点的个数，另一个代表旋转后。
小弟不才。
1 #include<cstdio> 2 #include<algorithm> 3 #include<vector> 4 #define HZOI std 5 using namespace HZOI; 6 const int N=1e6+5; 7 int n,res,ans; 8 int a[N],b[N],sm[N<<1]; 9 vector<int> vec[N<<1]; 10 inline void read(int &); 11 inline int max(int a,int b) { return a>b?a:b; } 12 int main() 13 { 14 int flag=0; 15 read(n); 16 for (int i=1; i<=n; ++i) 17 { 18 read(a[i]); 19 if (a[i]==i) b[2*i]=1,++res; 20 b[i*2]+=b[i*2-2]; 21 ++sm[a[i]+i]; 22 vec[a[i]+i].push_back(abs(a[i]*2-(a[i]+i))); 23 } 24 for (int i=1; i<=n*2; ++i) 25 { 26 sort(vec[i].begin(),vec[i].end(),greater<int>()); 27 for (int j=0; j<vec[i].size(); ++j) 28 { 29 int r=vec[i][j]; 30 ans=max(ans,b[n<<1]-b[i+r]+b[i-r-2]+sm[i]); 31 --sm[i]; 32 } 33 } 34 printf("%d",ans); 35 } 36 inline void read(int &a) 37 { 38 char ch=getchar(); 39 for (a=0; ch<'0' or ch>'9';ch=getchar()); 40 for (;ch>='0' and ch<='9'; a=(a<<3)+(a<<1)+(ch^48),ch=getchar()); 41 }
T2 走格子
大模拟，但也不是纯模拟。
思路非常好，很新奇。
对于每一个点，它可能通向上、下、左、右四个格子（如果是白格），如果想传送，必须要是走到一个墙边，再传送。题中要求的是最短距离，而不是说到达的位置，这不同与模拟，我们就想到了最短路。
顺着最短路的思路往下想，如何建边？想一个点，最多与八个点连边（上、下、左、右、上墙、下墙、左墙、右墙），然后如何建图。对于一个点想要i传送到远点，那么它必须先要走到一个墙处，这时我们遇到了问题：最近的墙的位置并不好求。我们想，既然我们要用最短路，只要保证每一个点是最优距离就行了（意思是不用考虑走到其他点的贡献，这样的话会算重，而且不好求），我们考虑一下局部最优解，那就是一个点就沿直线走，走到它最近的墙，然后通过这面墙转移到另外三个墙。
然而这只能算是yy出来的理想情况，处理要到的那个墙又是问题，具体操作，因为有Dij，我们不考虑走到的那堵墙再传到它本身是否需要花费（虽然这是合法的，但是这可以有效缩短代码量），也就是说，将走到的那个最近点和其他点一视同仁，都距离+1，这让不会使答案又误，毕竟是求的最短路，我只要保证每个点本身最优就可以了。
n^2处理最近的墙，建边然后跑Dij，解决了。
小弟不才。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<queue> 5 #include<algorithm> 6 #define HZOI std 7 using namespace HZOI; 8 const int N=555; 9 inline void read(int &); 10 struct DIJ{ 11 int num,dis; 12 friend bool operator < (DIJ a,DIJ b) 13 { 14 return a.dis>b.dis; 15 } 16 }poi[N*N<<1]; 17 int n,m; 18 int mp[N][N],sx,sy,tx,ty; 19 int ed[4][N*N],len[4][N*N];//左、上、右、下 20 int tt,first[N*N],vv[N*N<<5],nx[N*N<<5],ww[N*N<<5]; 21 int v[N*N]; 22 int stpx[4]={-1,1,0,0},stpy[4]={0,0,-1,1}; 23 void Dij(int ); 24 inline void Add(int ,int ,int ); 25 int main() 26 { 27 read(n),read(m); 28 for (int i=1; i<=n; ++i) 29 for (int j=1; j<=m; ++j) 30 { 31 char ch=getchar(); 32 while (ch^'.' and ch^'#' and ch^'C' and ch^'F') ch=getchar(); 33 if (ch=='C') sx=i,sy=j; 34 else if (ch=='F') tx=i,ty=j; 35 else if (ch=='#') mp[i][j]=1; 36 } 37 for (int i=1,d; i<=n; ++i) 38 for (int j=1; j<=m; ++j) 39 { 40 int id=(i-1)*m+j; 41 if (mp[i][j]) continue; 42 if (mp[i][j-1]) ed[0][id]=id,len[0][id]=0; 43 else ed[0][id]=ed[0][id-1],len[0][id]=len[0][id-1]+1; 44 if (mp[i-1][j]) ed[1][id]=id,len[1][id]=0; 45 else ed[1][id]=ed[1][(i-2)*m+j],len[1][id]=len[1][(i-2)*m+j]+1; 46 } 47 for (int i=n,d; i; --i) 48 for (int j=m; j; --j) 49 { 50 int id=(i-1)*m+j; 51 if (mp[i][j]) continue; 52 if (mp[i][j+1]) ed[2][id]=id,len[2][id]=0; 53 else ed[2][id]=ed[2][id+1],len[2][id]=len[2][id+1]+1; 54 if (mp[i+1][j]) ed[3][id]=id,len[3][id]=0; 55 else ed[3][id]=ed[3][i*m+j],len[3][id]=len[3][i*m+j]+1; 56 } 57 for (int i=1; i<=n; ++i) 58 for (int j=1; j<=m; ++j) 59 { 60 if (mp[i][j]) continue; 61 int id=(i-1)*m+j,minn=0x3f3f3f3f; 62 for (int k=0; k<4; ++k) 63 { 64 if (!mp[i+stpx[k]][j+stpy[k]]) 65 Add(id,(i+stpx[k]-1)*m+j+stpy[k],1); 66 minn=min(len[k][id],minn); 67 } 68 for (int k=0; k<4; ++k) 69 if (minn==len[k][id] and len[k][id]^0) 70 Add(id,ed[k][id],minn); 71 else if (minn^len[k][id]) 72 Add(id,ed[k][id],minn+1); 73 } 74 memset(v,0,sizeof(v)); 75 Dij((sx-1)*m+sy); 76 if (poi[(tx-1)*m+ty].dis==0x3f3f3f3f) puts("no"); 77 else printf("%d ",poi[(tx-1)*m+ty].dis); 78 return 0; 79 } 80 void Dij(int k) 81 { 82 priority_queue<DIJ> q; 83 for (int i=1; i<=n; ++i) 84 for (int j=1; j<=m; ++j) 85 poi[(i-1)*m+j].dis=0x3f3f3f3f, 86 poi[(i-1)*m+j].num=(i-1)*m+j; 87 poi[k].dis=0; 88 poi[k].num=k; 89 q.push(poi[k]); 90 while (!q.empty()) 91 { 92 DIJ x=q.top(); 93 q.pop(); 94 int pnt=x.num,dtc=x.dis; 95 v[pnt]=1; 96 for (int i=first[pnt]; i; i=nx[i]) 97 { 98 int ver=vv[i]; 99 if (v[ver]) continue; 100 if (poi[ver].dis>dtc+ww[i]) 101 { 102 poi[ver].dis=dtc+ww[i]; 103 q.push(poi[ver]); 104 } 105 } 106 } 107 } 108 inline void Add(int u,int v,int w) 109 { 110 vv[++tt]=v,ww[tt]=w,nx[tt]=first[u],first[u]=tt; 111 } 112 inline void read(int &a) 113 { 114 char ch=getchar(); 115 for (a=0; ch<'0' or ch>'9';ch=getchar()); 116 for (;ch>='0' and ch<='9'; a=(a<<3)+(a<<1)+(ch^48),ch=getchar()); 117 }
T3 柱状图
神仙题，数状数组的妙用。
会了一点点，不过还是挂上巨神博客吧。
还见识了一种玄学算法，模拟退火。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<ctime> 5 #include<algorithm> 6 #define int long long 7 #define HZOI std 8 using namespace HZOI; 9 const int N=1e5+5,INF=1<<30; 10 double T=0.001,delta=0.97,eps=1e-10; 11 int n,ans,a[N],b[N],nowpos,nowans,newpos,newans; 12 inline int Ask(int ); 13 signed main() 14 { 15 srand(time(0)); 16 ans=1e16; 17 scanf("%lld",&n); 18 for (int i=1; i<=n; ++i) 19 scanf("%lld",&a[i]); 20 nowpos=(n+1)>>1; 21 nowans=Ask(nowpos); 22 while (T>eps) 23 { 24 // printf("T=%.12lf ",T); 25 newpos=max(1ll,newpos); 26 newpos=min(n,newpos); 27 newans=Ask(newpos); 28 if( newans<nowans or exp((newans-nowans)/T)*RAND_MAX<rand() ) 29 nowpos=newpos,nowans=newans; 30 if (newans<ans) ans=newans; 31 T*=delta; 32 } 33 printf("%lld",ans); 34 } 35 inline int Ask(int k) 36 { 37 int t=1,sm=0,mid=(n+1)>>1,maxx; 38 b[k]=a[k]; 39 for (int i=k-1; i; --i) 40 b[i]=a[i]+t,++t; 41 t=1; 42 for (int i=k+1; i<=n; ++i) 43 b[i]=a[i]+t,++t; 44 nth_element(b+1,b+mid,b+n+1); 45 maxx=max(b[mid],max(k,n-k+1)); 46 for (int i=1; i<=n; ++i) sm+=abs(maxx-b[i]); 47 return sm; 48 }