題意

題解

又是一道神仙題……
顯然的做法是大力splay，時間復雜度\(O((N+Q)N\log N)\), 可以卡掉。
正解: 使用十字鏈表維護矩陣，在周圍增加第\(0\)行/列和第\((n+1)\)行/列，設\(li[x][d]\)表示\(x\)這個點在\(d\)這個方向上的下一個元素的編號是什么（一開始給每個元素都編上號）。那么對于一次旋轉，子矩形邊界上的格子暴力修改，內部相當于把\(4\)個方向做了個輪換，因此可以打標記實現。
然而本題的實現方法比較神奇: 每次修改從\((0,0)\)走到\((x,y)\) (只花費\(O(N)\)的時間)，首先\((0,0)\)的標記一定是正確的（因為沒有修改過），然后一路上通過當前點和下一個點互相儲存位置的偏移量以及當前點的正確標記確定下一個點的正確標記。（詳見代碼，我的代碼里標記的含義是實際方向等于存儲方向加標記）
時間復雜度\(O((N+Q)N)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;const int N = 1002; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; char ch[N+3]; char a[N*N+3]; int li[N*N+3][4]; int tag[N*N+3]; int aux1[4][N+3],aux2[4][N+3]; int n,q;int getid(int x,int y) {return x*(n+2)+y+1;} int getnxt(int u,int dir) {int ret = li[u][(dir-tag[u]+4)&3];for(int i=0; i<4; i++) {if(li[ret][i]==u) {tag[ret] = (dir-i+6)&3;}}return ret; }int main() {scanf("%d%d",&n,&q);for(int i=1; i<=n; i++) {scanf("%s",ch+1); for(int j=1; j<=n; j++) a[getid(i,j)] = ch[j];}for(int i=0; i<=n+1; i++){for(int j=0; j<=n+1; j++){int u = getid(i,j);for(int k=0; k<4; k++){if(i+dx[k]>=0&&i+dx[k]<=n+1&&j+dy[k]>=0&&j+dy[k]<=n+1) {li[u][k] = getid(i+dx[k],j+dy[k]);}}}}while(q--){int x,y,l; scanf("%d%d%d",&x,&y,&l);int u = 1;for(int i=0; i<x; i++) u = getnxt(u,0);for(int i=0; i<y; i++) u = getnxt(u,1);for(int k=0; k<4; k++){for(int i=0; i<l; i++){aux1[k][i] = u; aux2[k][i] = getnxt(u,(k+3)&3);if(i<l-1) u = getnxt(u,k);}}for(int k=0; k<4; k++){for(int i=0; i<l; i++){li[aux1[k][i]][(k-tag[aux1[k][i]]+3)&3] = aux2[(k+1)&3][i];li[aux2[k][i]][(k-tag[aux2[k][i]]+5)&3] = aux1[(k+3)&3][i];}}}int u = 1;for(int i=1; i<=n; i++){u = getnxt(u,0);int uu = u;for(int j=1; j<=n; j++) {uu = getnxt(uu,1); ch[j] = a[uu];/* printf("%d ",uu);*/}puts(ch+1); // puts("");}return 0; }

總結

以上是生活随笔為你收集整理的[JOI2012春季合宿]Rotate (链表)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。