—— Summon, Light!
0%

UVALive 7139 Rotation

发表于 更新于 Valine：

Rotation

题意：$N×M$ 的网格图，给定一条网格线连成的闭合路径，计算所有格子转动值的平方和。假设一辆车沿着路径移动，一个人站在某个格子正中间始终对着车，这个人在车开始到停下顺时针转动了 $x$ 度，则他的转动值为 $\frac{x}{360}$ （可以为负数）。
题解：首先，因为起点和终点相同，每个格子的转动值一定为整数。
其次，若路径为简单环，环内的格子转动值均为 $\pm 1$，环外的格子转动值均为 $0$ 。

环外某格的转动值一定为0
接着可以发现，每次路径向下时，为左边的格子贡献正的转动值，为右边的格子贡献负的转动值。
用一个看来的巧妙的做法：每次只考虑路径对右侧的格子的影响。上行一次，右侧所有格子加一，下行一次，右侧所有格子减一。这时，这个做法已经不仅限于简单环了。
现在问题转化为给一个矩阵增量，由于只需要最后结果，我们可以利用差分的思想。
在一维时，差分可以将区间增量变成两个点的增量。差分即为前缀和的逆运算，回忆一下二维前缀和的递推：$$sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]$$

设计如下的增量：

二维的差分

进行二维前缀和递推以后即可得到真实的数。

考虑到本题每次更新的矩阵都是直到右边界，所以可以忽略右边的两个增量。

最后，本题需要生成一个长宽不定的矩阵，C++使用 vector 比较方便，C语言查了一下指针和malloc大概要十多行吧。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
int T,n,m,k;
vector< vector<int> > mp;

void update(int r1,int r2,int c,int val)
{
    mp[r1][c]+=val;
    mp[r2][c]-=val;
}

int main()
{
    scanf("%d",&T);
    for (int t=1;t<=T;t++) {
        scanf("%d%d%d",&n,&m,&k);
        mp=vector< vector<int> >(n+2,vector<int>(m+2,0));
        int r=1,c=1;
        while (k--) {
            char d[2];
            int s;
            scanf("%s%d",d,&s);
            if (d[0]=='U') {
                update(r-s,r,c,1);
                r-=s;
                continue;
            }
            if (d[0]=='D') {
                update(r,r+s,c,-1);
                r+=s;
                continue;
            }
            if (d[0]=='L') {
                c-=s;
            } else {
                c+=s;
            }
        }
        ll ans=0;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                mp[i][j]=mp[i][j]+mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];
                ans+=(ll)mp[i][j]*mp[i][j];
            }
        }
        printf("Case #%d: %lld\n",t,ans);
    }
    return 0;
}

其实我们可以发现，不管考虑哪一侧都可以解决这个问题，当然因为最开始在左上角，维护左侧和上侧可能比较困难。下面放一个维护下侧的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
int T,n,m,k;
vector< vector<int> > mp;

void update(int r,int c1,int c2,int val)
{
    mp[r][c1]+=val;
    mp[r][c2]-=val;
}

int main()
{
    scanf("%d",&T);
    for (int t=1;t<=T;t++) {
        scanf("%d%d%d",&n,&m,&k);
        mp=vector< vector<int> >(n+2,vector<int>(m+2,0));
        int r=1,c=1;
        while (k--) {
            char d[2];
            int s;
            scanf("%s%d",d,&s);
            if (d[0]=='L') {
                update(r,c-s,c,-1);
                c-=s;
                continue;
            }
            if (d[0]=='R') {
                update(r,c,c+s,1);
                c+=s;
                continue;
            }
            if (d[0]=='U') {
                r-=s;
            } else {
                r+=s;
            }
        }
        ll ans=0;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                mp[i][j]=mp[i][j]+mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];
                ans+=(ll)mp[i][j]*mp[i][j];
            }
        }
        printf("Case #%d: %lld\n",t,ans);
    }
    return 0;
}
咖啡，亦我所需也