OI题解 - 机器人高尔夫球赛(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 机器人高尔夫球赛(LOJ)

发表于 分类于 Valine：

一道精妙的暴力题 : (

# 题面

> LOJ 3193

# 解析

要有打表的意识 awa（其实我打了表还是不知道怎么做）

首先可以得到一个非常暴力的$O(nm)$ 的DP：f[i][j][0/1] 表示此时球在 $(i,j)$，且现在是先手/后手击球，得分会是多少，转移太简单就不写了。

什么意思呢？我们发现偌大的 $10^9\times 10^9$ 的矩形上，竟然只有 $10^5$ 个洞。于是想到，我们看一下一个洞会对 DP 数组造成什么影响。

假设一开始木有洞，那么就是全 0 的DP数组，然后在某个位置出现了一个 hole，假设其值为 1（>0）：

1
2
3
4
5
6
7
//(a,b) 表示 (f[i][j][0]=a,f[i][j][1]=b)
(1,0) (0,1) (0,0) (0,0) (0,0) (0,0)
(0,1) (1,0) (0,1) (0,0) (0,0) (0,0)
(0,0) (0,1) (1,0) (0,1) (0,0) (0,0)
(0,0) (0,0) (0,1) (1,0) (0,1) (0,0)
(0,0) (0,0) (0,0) (0,1) (1,0) (0,1)
(0,0) (0,0) (0,0) (0,0) (0,1) (1,1)

非常开心的发现其实它只会影响到一个对角线形的较小的一块区域，而且看起来非常的有规律。

有什么规律？观察我们DP的次序，其实可以看成下面这样的顺序：

1
2
3
4
5
6
//数字表示转移的先后（较小的先计算）
8 7 6 5 4
7 6 5 4 3
6 5 4 3 2
5 4 3 2 1
4 3 2 1 0

于是我们大胆猜测，从左下到右上的对角线之间是有规律的，再次打表，的确有规律：

png1

（相同颜色是相同的DP值）假如橙色虚线往上就没有 hole 了，那么DP数组的这几条对角线将会一直保持这样。

然后考虑这样有规律的 DP 数组可能会被一个 hole 给打乱。但是我们发现一个 hole 只会影响以它为右下角的 $3\times3$ 的矩阵。于是对于这 9 个位置直接暴力 DP 一下值即可。

综上所述，在DP数组中，其实有值的位置很少，并且左下-右上对角线存在规律。

所以我们用 map 维护一下当前的左下-右上对角线上有值的位置的 DP 值。只暴力计算每个 hole 对应的 $3\times3$ 的位置的 DP 值即可。

至于计算答案，因为一条左上-右下对角线上的 DP 值——除非被暴力计算修改掉——是一直不变的。所以可以在暴力修改时计算当前左上-右下对角线原来的 DP 值出现了多少次，从而算出答案。

# 源代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*Lucky_Glass*/
#include<map>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define fir first
#define sec second
const int N=1e5+10,MOD=998244353;
typedef pair<int,int> pii;

inline int Add(const int &A,const int &B){return A+B>=MOD? A+B-MOD:A+B;}
inline int Mul(const int &A,const int &B){return 1ll*A*B%MOD;}

map<int,int> las;
map<pii,int> key;

int rol,col,n;
vector<pii> sp;
pii f[N<<4]; //min(first),max(second)

inline int Ri(){
    register int a=0,b=1,c=getchar();
    while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
    while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
    return a*b;
}
inline bool cmp(pii A,pii B){return A.fir+A.sec==B.fir+B.sec? A.fir<B.fir:A.fir+A.sec>B.fir+B.sec;}
inline pii Calc(int x,int y){
    if(key.count(make_pair(x,y))) return make_pair(key[make_pair(x,y)],key[make_pair(x,y)]);
    pii key1(0,0),key2(0,0);
    if(las.count(x-y+1)) key1=f[las[x-y+1]];
    if(las.count(x-y-1)) key2=f[las[x-y-1]];
    return make_pair(min(key1.sec,key2.sec),max(key1.fir,key2.fir));
}
inline int Model(const int &x){return (x%MOD+MOD)%MOD;}
int main(){
    rol=Ri(),col=Ri(),n=Ri();
    for(int i=1;i<=n;i++){
        int x=Ri(),y=Ri(),val=Ri();
        key[make_pair(x,y)]=val;
        //枚举3*3的矩阵，标记这些位置要暴力计算
        for(int p=0;p<=2 && x-p>0;p++)
            for(int q=0;q<=2 && y-q>0;q++)
                sp.push_back(make_pair(x-p,y-q));
    }
    //把要暴力计算的位置排序、去重
    sort(sp.begin(),sp.end(),cmp);
    sp.erase(unique(sp.begin(),sp.end()),sp.end());
    long long ans=0;
    for(int o=0,lo=sp.size();o<lo;o++){
        int tag=sp[o].fir+sp[o].sec,beg=o;
        while(o+1<lo && sp[o+1].fir+sp[o+1].sec==tag) o++;
        //找到在同一条左下-右上对角线上的暴力计算的点
        for(int i=beg;i<=o;i++){
            int x=sp[i].fir,y=sp[i].sec;
            //统计当前左上-右下对角线原来的DP值出现的次数并计算贡献
            if(las.count(x-y)) ans=Add(ans,Mul(Model(f[las[x-y]].fir),sp[las[x-y]].fir-x));
            f[i]=Calc(x,y);
            las[x-y]=i; //记录当前左上-右下对角线的 DP 值
        }
    }
    //还有一些 DP 值的贡献
    for(map<int,int>::iterator it=las.begin();it!=las.end();it++)
        ans=Add(ans,Mul(Model(f[it->sec].fir),min(sp[it->sec].fir,sp[it->sec].sec)));
    printf("%d\n",ans);
    return 0;
}

THE END

Thanks for reading!