神仙題，打了個whs式暴力卡常卡A了（我沒臉），正解還是要打的，然而作者的題解看不懂……

Drink:

看慣了羅馬音的小朋友們都會知道r發(fā)l的音，題目名：D Link.

每次修改都會改變O( N ^?2 )個位置的值，二維平面上沒有一個確定的正方向，因此也無法使用傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)。

什么東西的變化量是O( N )級別的呢？

如果把每個點都看作一個人，他的頭面向某個方向。分別記錄這個人的方向上的前后左右分別是誰，那么每次旋轉(zhuǎn)改變的只是正方形邊緣上的值，以及所有點的方向。

這樣來看至少我們發(fā)現(xiàn)了變化量為O( N )級別的東西啦（雖然方向的改變量還是O( N ^ 2 )）。

注意到，我們并不需要真的知道每個點的方向，我們只需要正確地維護前后左右四個值即可。因為每個點的方向是可以由已知方向的相鄰點算出來的！

每個點確實是有方向的，但是我們不用紀錄也不用直接更改它，每次只要正確修改邊界上的值，整個矩形的方向就會自動改變。

解決啦！

復雜度O( Q * N ), 常數(shù)稍大。

搞不懂，先坑著。把暴力代碼放出來：

?

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define LL long long 5 #define ma(x) memset(x,0,sizeof(x)) 6 using namespace std; 7 int n,m,q; 8 int x[2010],y[2010],c[2010]; 9 char map[2010][2010],tmap[2010][2010]; 10 inline int read(); 11 signed main() 12 { 13 // freopen("drink.in","r",stdin); 14 // freopen("3.out","w",stdout); 15 16 n=read(),m=read(),q=read(); 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<=m;j++) 19 { 20 map[i][j]=getchar(); 21 while(map[i][j]<'0'||map[i][j]>'9')map[i][j]=getchar(); 22 tmap[i][j]=map[i][j]; 23 } 24 int tx,ty,tc; 25 for(int i=1;i<=q;i++) 26 { 27 tx=read(),ty=read(),tc=read(); 28 for(;tc>1;tc-=2,tx++,ty++) 29 { 30 for(int j=0;j<tc-1;j++) 31 { 32 int t1=map[tx+j][ty+tc-1], 33 t2=map[tx][ty+j], 34 t3=map[tx+tc-1][ty+tc-1-j], 35 t4=map[tx+tc-1-j][ty]; 36 map[tx+j][ty+tc-1]=t2; 37 map[tx][ty+j]=t4; 38 map[tx+tc-1][ty+tc-1-j]=t1; 39 map[tx+tc-1-j][ty]=t3; 40 } 41 } 42 } 43 for(int i=1;i<=n;i++) 44 { 45 for(int j=1;j<=m;j++) 46 printf("%d ",map[i][j]-'0'); 47 puts(""); 48 } 49 } 50 inline int read() 51 { 52 int s=0,f=1;char a=getchar(); 53 while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();} 54 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} 55 return s*f; 56 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Al-Ca/p/11331097.html

總結(jié)

以上是生活随笔為你收集整理的HZOJ Drink的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。