HZOJ Drink

悠悠 2021-10-26 16:01 238阅读 0赞

神仙题，打了个whs式暴力卡常卡A了（我没脸），正解还是要打的，然而作者的题解看不懂……

> Drink:
> 
> 看惯了罗马音的小朋友们都会知道r发l的音，题目名：D Link.
> 
> 每次修改都会改变O( N ^ 2 )个位置的值，二维平面上没有一个确定的正方向，因此也无法使用传统数据结构。
> 
> 什么东西的变化量是O( N )级别的呢？
> 
> 如果把每个点都看作一个人，他的头面向某个方向。分别记录这个人的方向上的前后左右分别是谁，那么每次旋转改变的只是正方形边缘上的值，以及所有点的方向。
> 
> 这样来看至少我们发现了变化量为O( N )级别的东西啦（虽然方向的改变量还是O( N ^ 2 )）。
> 
> 注意到，我们并不需要真的知道每个点的方向，我们只需要正确地维护前后左右四个值即可。因为每个点的方向是可以由已知方向的相邻点算出来的！
> 
> **每个点****确实****是有****方向的****，****但是我们不用纪录也不用直接更改****它，****每次只要正确修改****边界****上的值，****整个****矩形的方向就会自动改变。**
> 
> 解决啦！
> 
> 复杂度O( Q \* N ), 常数稍大。

搞不懂，先坑着。把暴力代码放出来：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/Al-Ca/p/11331097.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/4ecc88fa5e2049b883f6ec52fda2e083.png