P8865 [NOIP2022] 种花 Solution

• P8865 [NOIP2022] 种花 Solution
  • 更好的阅读体验戳此进入
    • 题面
    • Solution
    • Code
  • UPD

更好的阅读体验戳此进入

题面

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

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

Solution

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

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

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

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

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

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (ll)(998244353)

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

int N, M, C, F;
bool mp[1100][1100];
int cline[1100][1100];
int srow[1100][1100];
int crow[1100][1100];
int line_x_row[1100][1100];
ll srowF[1100][1100];
ll cntC(0), cntF(0);

int main(){
    int T = read(); (void)read();
    while(T--){
        memset(mp, 0, sizeof mp);
        memset(cline, 0, sizeof cline);
        memset(srow, 0, sizeof srow);
        memset(crow, 0, sizeof crow);
        memset(line_x_row, 0, sizeof line_x_row);
        memset(srowF, 0, sizeof srowF);
        cntC = cntF = 0;
        N = read(), M = read(), C = read(), F = read();
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= M; ++j){
                char c = getchar();
                while(c != '1' && c != '0')c = getchar();
                mp[i][j] = c - '0';
            }
        for(int i = 1; i <= N; ++i){//i = line, j - row
            deque < int > cur;
            for(int j = 1; j <= M; ++j)
                if(!mp[i][j])cur.emplace_back(j);
                else while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
            while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
        }
        // for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", cline[i][j], j == M ? '\n' : ' ');
        for(int i = 1; i <= M; ++i){//i - row, j - line
            deque < int > cur;
            for(int j = 1; j <= N; ++j)
                if(!mp[j][i])cur.emplace_back(j);
                else while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
            while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
        }
        // for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", crow[j][i], j == M ? '\n' : ' ');
        for(int i = 1; i <= M; ++i)//i - row, j - line
            for(int j = 1; j <= N; ++j)
                srow[i][j] = srow[i][j - 1] + cline[j][i];
        for(int i = 1; i <= M; ++i)
            for(int j = 1; j <= N; ++j)
                line_x_row[i][j] = crow[i][j] * cline[j][i] % MOD;
        for(int i = 1; i <= M; ++i)
            for(int j = 1; j <= N; ++j)
                srowF[i][j] = (srowF[i][j - 1] + line_x_row[i][j]) % MOD;
        for(int i = 1; i <= M; ++i)
            for(int j = 1; j <= N - 2; ++j){
                if(crow[i][j] < 2)continue;
                (cntC += (ll)cline[j][i] * (srow[i][j + crow[i][j]] - srow[i][j + 1]) % MOD) %= MOD;
                if(!crow[i][j + 2])continue;
                (cntF += (ll)cline[j][i] * (srowF[i][j + crow[i][j]] - srowF[i][j + 1]) % MOD) %= MOD;
            }
        printf("%lld %lld\n", cntC * C, cntF * F);
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_28 初稿