P8865 [NOIP2022] 种花 Solution

更好的阅读体验戳此进入

题面

大概就是在有障碍的网格图里分别问能填充多少 C 和 F 形状的图形。严谨地叙述太复杂了，这里就不多叙述，直接去看 洛谷题面 吧。

然后顺便吐槽一下，这不愧是经典的 NOIP T1，感觉和上次的报数差不多，难度有点低了，比 CSP 的 T1 T2 都要简单，可惜考试取消了没考上。

Solution

做完之后翻了一下讨论区，似乎还有一些高妙的悬线法之类的解法，可以很简短地切掉这题。不过我不会我感觉不是很好像，所以这里提供一个思维难度极低，代码略长的做法，比较无脑，但是是妥妥的 $O(n^2)$$O(n^2)$。

大概就是手画一下找性质，然后发现，对于 C 型来说，当我们固定其上下两行之后，若最左侧列从上至下都是 $0$$0$，那么这样的方案书就是上端横行向右最大延申的 $0$$0$ 乘上下端延伸的。换句话说，我们就是要枚举确定每个 C 的左侧的竖直的部分，然后把上下两侧可以延伸的乘起来加到方案里。

然后这东西是 $O(n^3)$$O(n^3)$ 的，也就是枚举每个点然后再枚举竖直能延申多少。

然后我们发现这东西实际上是可以优化的，也就是说当我们确定一个竖直部分上端点所在行为 $i$$i$ 的时候，如果这个点竖直向下最长可以延申 $\xi$$\xi$，那么我们要的就是行数为 $[i+2,i+\xi ]$$[i + 2, i + \xi]$ 之间的所有可能水平延伸的长度之和。

这样的话我们就随便做一个竖直方向上的前缀和即可优化 $O(n^3)⟶O(n^2)$$O(n^3) \longrightarrow O(n^2)$，则对于 C 型的就过了。

对于维护最长能延申的距离，随便写一个 deque 即可，也就是双端队列，里面存下标，对于每个值如果为 $0$$0$ 那么直接插进去，如果为 $1$$1$ 那么更新队列里所有的下标的值即可，具体可看代码，很好理解。

然后考虑 F 型，这个需要想一下，发现对于一个确定的 C 型，变成 F 型就是乘上其下端点能够延伸的距离。这个正常做还是 $O(n^3)$$O(n^3)$ 的，优化方式也类似，类比之前的方式，维护水平延申长度的时候直接乘上竖直延申长度，然后再做个前缀和即可，具体实现可以参考代码。

Tips：有一些循环能压在一起，会让代码可读性变差这里就不压了。然后因为是 VP 也没打对拍，交上去最后两个点 WA 了，随便写了个满的数据才发现是最后加法没有取模。。。不过这种错误随便拍一下就能调出来，然后这题本身也很好调，思路非常直观，一步一步检查即可。

Code

105
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(998244353)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, M, C, F;
28
bool mp[1100][1100];
29
int cline[1100][1100];
30
int srow[1100][1100];
31
int crow[1100][1100];
32
int line_x_row[1100][1100];
33
ll srowF[1100][1100];
34
ll cntC(0), cntF(0);
35

36
int main(){
37
    int T = read(); (void)read();
38
    while(T--){
39
        memset(mp, 0, sizeof mp);
40
        memset(cline, 0, sizeof cline);
41
        memset(srow, 0, sizeof srow);
42
        memset(crow, 0, sizeof crow);
43
        memset(line_x_row, 0, sizeof line_x_row);
44
        memset(srowF, 0, sizeof srowF);
45
        cntC = cntF = 0;
46
        N = read(), M = read(), C = read(), F = read();
47
        for(int i = 1; i <= N; ++i)
48
            for(int j = 1; j <= M; ++j){
49
                char c = getchar();
50
                while(c != '1' && c != '0')c = getchar();
51
                mp[i][j] = c - '0';
52
            }
53
        for(int i = 1; i <= N; ++i){//i = line, j - row
54
            deque < int > cur;
55
            for(int j = 1; j <= M; ++j)
56
                if(!mp[i][j])cur.emplace_back(j);
57
                else while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
58
            while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
59
        }
60
        // for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", cline[i][j], j == M ? '\n' : ' ');
61
        for(int i = 1; i <= M; ++i){//i - row, j - line
62
            deque < int > cur;
63
            for(int j = 1; j <= N; ++j)
64
                if(!mp[j][i])cur.emplace_back(j);
65
                else while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
66
            while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
67
        }
68
        // for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", crow[j][i], j == M ? '\n' : ' ');
69
        for(int i = 1; i <= M; ++i)//i - row, j - line
70
            for(int j = 1; j <= N; ++j)
71
                srow[i][j] = srow[i][j - 1] + cline[j][i];
72
        for(int i = 1; i <= M; ++i)
73
            for(int j = 1; j <= N; ++j)
74
                line_x_row[i][j] = crow[i][j] * cline[j][i] % MOD;
75
        for(int i = 1; i <= M; ++i)
76
            for(int j = 1; j <= N; ++j)
77
                srowF[i][j] = (srowF[i][j - 1] + line_x_row[i][j]) % MOD;
78
        for(int i = 1; i <= M; ++i)
79
            for(int j = 1; j <= N - 2; ++j){
80
                if(crow[i][j] < 2)continue;
81
                (cntC += (ll)cline[j][i] * (srow[i][j + crow[i][j]] - srow[i][j + 1]) % MOD) %= MOD;
82
                if(!crow[i][j + 2])continue;
83
                (cntF += (ll)cline[j][i] * (srowF[i][j + crow[i][j]] - srowF[i][j + 1]) % MOD) %= MOD;
84
            }
85
        printf("%lld %lld\n", cntC * C, cntF * F);
86
    }
87
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
88
    return 0;
89
}
90

91
template < typename T >
92
inline T read(void){
93
    T ret(0);
94
    int flag(1);
95
    char c = getchar();
96
    while(c != '-' && !isdigit(c))c = getchar();
97
    if(c == '-')flag = -1, c = getchar();
98
    while(isdigit(c)){
99
        ret *= 10;
100
        ret += int(c - '0');
101
        c = getchar();
102
    }
103
    ret *= flag;
104
    return ret;
105
}

UPD

update-2022_11_28 初稿