比賽預期情況

總共比賽人數：175 (至少通過一道題的人數，沒有通過題的不計入總人數)

P.S. “EDIT” 部分懶得數了，先湊合看一下

題解

chiking 的偶像

大致題意

回圈輸出 \soup_god/，且總共輸出的字串長度為 n n n

思路

簡單的簽到題，只需要還記得有 mod 這個運算就能寫出來

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    const char *data = "\\soup_god/";
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cout << data[i % 10];
    }
    cout << endl;
}

chiking 和珂朵莉

大致題意

n n n 個物品，每個物品都有價值和所屬類別，讓你選擇 n ? k n - k n?k 種類別的物品，使得所選出來的這些類別的物品的總價值最大

思路

也是簽到題之一

在讀入資料的時候統計每個類別的物品價值只和，之后排序一下，取出后 n ? k n - k n?k 個類別的價值即可

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int w[11] = {0};
    int m, n, k;
    cin >> m >> n >> k;
    for (int i = 0; i < m; ++i) {
        int d, s;
        cin >> d >> s;
        w[s] += d;
    }
    sort(w + 1, w + n + 1);
    int ans = 0;
    for (int i = k + 1; i <= n; ++i) ans += w[i];
    cout << ans << endl;
}

吐槽

這道題原來有一個小坑點，即物品的價值可以為負數，所以需要額外增加一個判斷，但是想了想還是當簽到題，不要故意惡心了，于是就刪掉了，所以順便好奇的問一下，有多少人看到題面之后去想過價值是不是可能為負數呢

chiking 的序列 II

大致題意

有一個非遞減的陣列，允許你進行任意次數操作，每次操作可以使得其中一個值增加 1 1 1，問至少需要多少次操作才能使得陣列內沒有相同的值

思路

因為只能進行加法運算，所以數字只會增加，由于已經排序好了陣列，所以最簡單的方案就是讓每一個值都比前一個值要大即可

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; ++i) cin >> data[i];
    long long sum = 0;
    for (int i = 1; i < n; ++i) {
        int tmp = max(data[i - 1] + 1, data[i]);
        sum += tmp - data[i];
        data[i] = tmp;
    }
    cout << sum << endl;
}

chiking 的序列 I

大致題意

有一個陣列，允許你進行任意次操作，每次執行操作可以將任意一個數字插入到陣列到任意位置，問至少需要多少次操作才能使得陣列內到每一個值滿足 a i ≤ i a_i \leq i ai?≤i，其中 i i i 表示下標

思路

首先要讓每一位的的數字小于等于其下標，那么插入的數字也不能例外，由于插入的數字可以是任意值，所以理所應當的，選擇 1 1 1 進行插入是最好的選擇，因為無論插入何處均可以使得新插入的數字不再需要考慮

接下來是考慮插入位置的問題，在等式中 a i a_i ai? 是不可更新的值，所以只能想辦法使得 i i i 增大，那么最容易得到的解決方案就是將數字插入陣列開頭，這會使得所有原來在陣列內的值的下標都增大，最大程度的滿足條件

接下來考慮插入數量的問題，由于都是插入陣列最前面，所以可以將等式改寫為 a i < = i + x a_i <= i + x ai?<=i+x，其中的 x x x 即為需要求解的值，那么對于每一個 i i i 都要滿足這個等式，所以遍歷一次陣列，找出最大的需要的 x x x 即可

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            ans = max(ans, tmp - i - 1);
        }
        cout << ans << endl;
    }
}

chiking 的棋盤

大致題意

用 k k k 個 L 形狀的方塊能否平鋪一個矩形方格

思路

我們可以用 L 形狀的方塊拼出如下兩種最簡平鋪方案

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-JhYBmf9b-1639041859538)(/image/acm/2021-ZJGSU-ACM-freshman-competition/2*4.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Q0HQwnc4-1639041859539)(/image/acm/2021-ZJGSU-ACM-freshman-competition/3*8.png)]

這兩個方案都是 8 8 8 個方格的倍數，所以起碼，方格總數應該是 8 8 8 的倍數，即 n × m = 8 k n \times m = 8k n×m=8k

1. 假設兩邊都是偶數，那么必然其中一邊為 2 2 2 的倍數，另外一邊為 4 4 4 的倍數，所以必然可以被僅靠第一種平鋪方案平鋪
2. 假設一邊為奇數一邊是偶數，那么必然其中一邊為 8 8 8 的倍數，而第一種方案也可以改寫為 2 ? 8 2 * 8 2?8 的方格，即只需要另外一邊可以分解為 2 x + 3 y 2x + 3y 2x+3y 的形式即可，易得只要 $ \geq 2$ 的值均可

所以結論：只要滿足方格數為 8 8 8 的倍數，且兩邊都 $ \geq 2$，則必定可以平鋪

接下來只需要計算數量對不對就行

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
#define int long long
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, m, k;
        cin >> n >> m >> k;
        if (n > 1 && m > 1 && (n * m) % 8 == 0) {
            int cnt = (n * m / 4);
            if (cnt == k) cout << "Perfect!\n";
            else cout << "Single forever!\n";
        } else cout << "Single forever!\n";
    }
}

樂于助人的 chiking

大致題意

允許將字串中 oo 和 u 互轉，也允許將字串的 kh 和 h 互轉的前提下，計算給出的字串陣列中有幾個不同的字串

思路

由于存在轉換，所以最好的辦法就是統一轉為一種型別，再進行比較

oo 和 u 這對規則，若我們將所有的 oo 轉為 u，那么當遇到 ou 和 uo 時，會發現在此條規則下應該是相等的字串沒有相等，所以應該將所有的 u 字符轉為 oo

kh 和 h 這對規則，若我們將所有的 h 轉為 kh，那么就會出現 kh 還可以繼續轉為 kkh、kkkh、kkkkh 等，所以只能選擇將 kh 轉為 h，但是請注意 kkkh 這類連續的 k 的情況，可以連續多次轉換

處理完成后，統計不同的字串的數量即可

處理字串復雜度 O ( n m ) = 1 e 5 O(nm) = 1e5 O(nm)=1e5
統計不同字串數量 O ( n 2 m ) = 1 e 7 O(n^2m) = 1e7 O(n2m)=1e7

滿足要求

AC Code

#include "bits/stdc++.h"

using namespace std;

char a[1010], b[2010];

void solve() {
    int n;
    cin >> n;
    vector<string> data;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        int len = (int) strlen(a);
        int pos = 0;
        for (int j = 0; j < len; ++j) {
            if (a[j] == 'u') {
                b[pos++] = 'o';
                b[pos++] = 'o';
            } else if (a[j] == 'h') {
                while (pos > 0 && b[pos - 1] == 'k') pos--;
                b[pos++] = 'h';
            } else {
                b[pos++] = a[j];
            }
            b[pos] = 0;
        }
        data.emplace_back(b);
    }
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool flag = true;
        for (int j = i + 1; j < n; ++j) {
            if (data[i] == data[j]) {
                flag = false;
                break;
            }
        }
        if (flag) cnt++;
    }
    cout << cnt + 1 << endl;
}

更好的優化

實際上，這里需要比較的是字串是否相同，所以可以使用字串 hash 來解決，這樣，復雜度將會降低至 O ( n m ) O(nm) O(nm)，當然，字串 hash 存在一定的可能錯誤的隱患，但是可以通過增加多組 hash 來解決

Better Code

#include "bits/stdc++.h"

using namespace std;

char a[1010], b[2010];

void solve() {
    int n;
    cin >> n;
    set<long long> hashCode;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        int len = (int) strlen(a);
        int pos = 0;
        for (int j = 0; j < len; ++j) {
            if (a[j] == 'u') {
                b[pos++] = 'o';
                b[pos++] = 'o';
            } else if (a[j] == 'h') {
                while (pos > 0 && b[pos - 1] == 'k') pos--;
                b[pos++] = 'h';
            } else {
                b[pos++] = a[j];
            }
        }
        long long code = 0;
        const long long p = 131, m = 1e9+7;
        for (int j = 0; j < pos; ++j) {
            code *= p;
            code %= m;
            code += b[j];
            code %= m;
        }
        hashCode.insert(code);
    }
    cout << hashCode.size() << endl;
}

chiking 的俄羅斯方塊

大致題意

寬度為 4 的俄羅斯方塊游戲，僅有兩種方塊： 2 × 2 2 \times 2 2×2 的方塊和 1 × 4 1 \times 4 1×4 的長條，在已知所有的下落順序的情況下，求出最優的分數

思路

需要思考的東西比較多，我們先來證明一些東西，方面后面使用

實際上僅會出現 10 分和 3 分兩種消方塊

這個結論應該是比較簡單就可以得出的，因為垂直方向上只有長度為 2 和 4 的方塊，所以當我們能遇到創造出 10 分的情況，盡快消除絕對不會虧

長條方塊必定可以合并視為 2 × 4 2 \times 4 2×4

這個結論指的是如下的情況是不可能發生的(帶箭頭的藍色方塊是最后落下的)

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-bn9035cT-1639041859540)(/image/acm/2021-ZJGSU-ACM-freshman-competition/Tetris-cannot-be-inserted.png)]

因為這個情況下，才會出現 1 × 4 1 \times 4 1×4 無法插入到原來的 1 × 4 1 \times 4 1×4 中使得變成 2 × 4 2 \times 4 2×4

而這個情況恰好滿足一個 10 分的消除情況，即下圖

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-WXj8mYEQ-1639041859540)(/image/acm/2021-ZJGSU-ACM-freshman-competition/10-1.png)]

既然能創造 10 分，那么就沒必要糾結是不是能夠合并了，先變成 10 分重要，所以不存在單獨一根的長條方塊的情況

將 2*2 放中間一定不是好的選擇

這個結論應該顯而易見吧，因為放左/右邊既可以與 1 × 4 1 \times 4 1×4 消分，還可以與 2 × 2 2 \times 2 2×2 消分，比放中間肯定更優

原來的結構不影響當前期望的分數

這句話擴展起來就是

不管之前的方塊帶來什么影響，若接下來 n 個方塊能夠創造 10 分的價值，則一定可以創造 10 分的價值，若接下來 n 個方塊能創建 3 分的價值，則一定可以創造 3 分的價值

這一條暫且先不證明

所有組合如下

所有能夠拿分的組合只有下面這些，其中只有前兩個是 10 分，其他的均為 3 分

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PHbSOyvp-1639041859540)(/image/acm/2021-ZJGSU-ACM-freshman-competition/10-1.png)]

![10-2](/image/acm/2021-ZJGSU-ACM-freshman-competition/10-2.png

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-yNdZwLFI-1639041859541)(/image/acm/2021-ZJGSU-ACM-freshman-competition/3-1.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PAtpKcOk-1639041859541)(/image/acm/2021-ZJGSU-ACM-freshman-competition/3-2.png)]

接下來我們可以證明上面那條的結論

之前方塊帶來的影響主要是由于其必須要先落下導致占用了一定的位置，使得原來可以消掉的方塊沒有辦法繼續消除

最常見的一個影響就是 2 × 2 2 \times 2 2×2 影響，簡單來說就是原來已經有一塊 2 × 2 2 \times 2 2×2 方格，此時就不一定能夠做到滿足上述的消分情況，如下圖

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-AeD0hA2S-1639041859541)(/image/acm/2021-ZJGSU-ACM-freshman-competition/2-2-block.png)]

例如此時，其實無法完美的滿足第二種 10 分的消分情況，因為你不可能將四個 1 × 4 1 \times 4 1×4 放在同一行中，即同時下落四個 1 × 4 1 \times 4 1×4 的方塊時，你不能僅通過這四個方塊得到 10 分

但是又如何呢？

實際上我們仍然可以拿到 10 分，而且最后剩下的結果仍然是 2 × 2 2 \times 2 2×2方塊，如下圖所示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-YsV3O7nJ-1639041859541)(/image/acm/2021-ZJGSU-ACM-freshman-competition/2-2-block-solve.png)]

這里就不再詳細介紹每種情況了，供各位思考在 2 × 2 2 \times 2 2×2 的影響下，四種得分方案是否都可以得到原來的分數且不帶來新的影響

還有一種影響是 2 × 4 2 \times 4 2×4 的，比較類似，不再詳細說明了

特別的，無論在 2 × 2 2 \times 2 2×2 還是 2 × 4 2 \times 4 2×4 的影響下，第三種得分方案都有可能會從 3 分變成 10 分，而這雖然增加了分數，但是同時也增加了難于預料的問題，必須予以解決，有趣的是，這種新的得分方案，其實正是第一種方案，所以如果我們能夠優先將所有可能的第一種方案計算完，那么此情況其實不再可能出現，那么也就可以忽略了

除了 2 × 2 2 \times 2 2×2 還是 2 × 4 2 \times 4 2×4，還有更多的可能，例如更高的 2 × 8 2 \times 8 2×8 等等，但實際上是類似的，也就不再需要證明

當然還有更加離譜的影響，例如 1 × 4 1 \times 4 1×4影響，明顯，這個影響確實真的影響到得分了，因為第四種得分方案壓根不可能得分了，如下圖

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-tPxSwovZ-1639041859542)(/image/acm/2021-ZJGSU-ACM-freshman-competition/1-4-block-solve.png)]

但是，注意題目中說的 1 × 4 1 \times 4 1×4 一定是偶數個，所以之后必定有一個 1 × 4 1 \times 4 1×4，那么就回到了開頭的那個結論的情況，這里又可以拿到 10 分了

穿插組合并無影響

簡單來說就是兩個結構需要的方塊穿插起來，并不會影響最終的得分，這里就不再詳細介紹

當你證明完成后接下來就是模擬討論所有情況即可

注意第一種 10 分，其要求最后一個落下的必須是 1 × 4 1 \times 4 1×4 的長條即可，剩下的，統計數量就行

AC Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n;
    cin >> n;
    int tot0 = 0, cnt0 = 0, cnt1 = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin >> tmp;
        if (tmp == 1) {
            cnt1++;
            if (cnt1 >= 2 && cnt0 >= 2) {
                cnt1 -= 2;
                cnt0 -= 2;
                ans += 10;
            }
        } else {
            tot0++;
            cnt0++;
        }
    }
    ans += (cnt1 / 4) * 10;
    cnt1 &= 2;
    if (tot0 >= 2) {
        ans += (cnt0 + cnt1) / 2 * 3;
    } else if (cnt0 && cnt1) {
        ans += 3;
    }
    cout << ans << endl;
}

chiking 和大家一起來做簽到題

大致題意

給定一個 n，允許使用加減乘除和任意括號，找出有多少種不同的四個數字，使得這四個數字能夠運算出 n，且運算程序中一定出現了小數，羅列所有的可能的四個數字的組合

思路

其實就是一道暴力題

算一下復雜度， 1 3 4 / 2 ? 4 ! ? 2 ? 3 6 = 499 , 703 , 256 13^4 / 2 * 4! * 2 * 3^6 = 499,703,256 134/2?4!?2?36=499,703,256

解釋一下，羅列每個位置的每個可能，為 → 1 3 4 / 2 \rightarrow 13^4 / 2 →134/2 （避免重復，遍歷程序保證前一個值不大于當前值）

排列陣列 → 4 ! \rightarrow 4! →4!

總共有兩種括號方式 ( ( A @ B ) @ C ) @ D ((A @ B) @ C) @ D ((A@B)@C)@D 和 ( A @ B ) @ ( C @ D ) (A @ B) @ (C @ D) (A@B)@(C@D)（ A B C D ABCD ABCD 為數字， @ @ @ 為運算子號），所以 → 2 \rightarrow 2 →2

列舉所有的運算子號 → 3 6 \rightarrow 3^6 →36（6 種運算分別為 A + B , A ? B , B ? A , A × B , A ÷ B , B ÷ A A + B, A - B, B - A, A \times B, A \div B, B \div A A+B,A?B,B?A,A×B,A÷B,B÷A）

做一下剪枝，很容易提前放棄掉部分方案，復雜度還可以降低

所以直接暴力就行

但是，如何優雅的暴力呢？

AC code

#include "bits/stdc++.h"

using namespace std;

const double eps = 1e-6;


void solve() {

    int m;
    set<int> ans;
    int curValue[4];
    cin >> m;

    auto isM = [&](double cur) { return abs(cur - m) < eps; };
    auto isDouble = [&](double cur) { return abs(cur - int(cur + eps)) > eps; };

    auto add = [](double a, double b) { return a + b; };
    auto sub1 = [](double a, double b) { return a - b; };
    auto sub2 = [](double a, double b) { return b - a; };
    auto times = [](double a, double b) { return a * b; };
    auto div1 = [](double a, double b) { return a / b; };
    auto div2 = [](double a, double b) { return b / a; };

    function<double(double, double)> arr[6] = {add, sub1, sub2, times, div1, div2};

    auto cal = [&]() {
        bool reach = false, hasNoDouble = false;
        do {

            function<bool(double, int, bool)> dfs1 = [&](double cur, int deep, bool hasDouble) {
                if (deep == 4) {
                    if (isM(cur)) {
                        reach = true;
                        if (!hasDouble) {
                            hasNoDouble = true;
                            return false;
                        }
                    }
                    return true;
                }

                return all_of(arr, arr + 6, [&](function<double(double, double)> &func) {
                    double nxt = func(cur, curValue[deep]);
                    return dfs1(nxt, deep + 1, hasDouble || isDouble(nxt));
                });
            };
            function<bool()> dfs2 = [&]() {
                for (auto &i: arr) {
                    for (auto &j: arr) {
                        double l = i(curValue[0], curValue[1]);
                        double r = j(curValue[2], curValue[3]);
                        for (auto &k: arr) {
                            double t = k(l, r);
                            if (isM(t)) {
                                reach = true;
                                if (!isDouble(l) && !isDouble(r)) {
                                    hasNoDouble = true;
                                    return false;
                                }
                            }
                        }
                    }
                }
                return true;
            };

            dfs1(curValue[0], 1, false);
            dfs2();

        } while (next_permutation(curValue, curValue + 4));

        if (reach && !hasNoDouble) {
            // 四個小于 16 的 int 數字，可以按位壓縮到一個 int 中
            int t = 0;
            for (auto &item: curValue) {
                t <<= 4;
                t += item;
            }
            ans.insert(t);
        }
    };

    // 暴力列舉沒有必要一定要用 dfs，實際上 for 也可以，甚至更快，因為減少了出入堆疊的耗時
    for (int i = 0; i < 13; ++i) {
        curValue[0] = i + 1;
        for (int j = i; j < 13; ++j) {
            curValue[1] = j + 1;
            for (int k = j; k < 13; ++k) {
                curValue[2] = k + 1;
                for (int l = k; l < 13; ++l) {
                    curValue[3] = l + 1;
                    cal();
                }
            }
        }
    }

    cout << ans.size() << endl;
    for (auto &item: ans) {
        int cur = item;
        for (int i = 3; i >= 0; --i) {
            curValue[i] = cur % 16;
            cur >>= 4;
        }
        for (int i = 0; i < 4; ++i)
            cout << curValue[i] << " \n"[i == 3];
    }
}

chiking 是一個機器人

大致題意

有一個地圖，有障礙物，三種不同的機器，一個只能下，一個只能右，最后那個可以下右移動，詢問 q 次某種機器能否從起始點到終點

思路

考慮前兩種機器，其實很好解決，以第一種機器舉例，我將整個地圖的第一行加到第二行，此時的第二行加到第三行，如此操作后，每個點上保存的是此點的正上方有多少個墻，稱其為“前綴墻”，若起點和終點的點的“前綴墻”數量相同，則就可以到達，否則中間必定存在墻

第二種機器就不再過多介紹了

第三種機器則比較難做，考慮一種 dp 的可能：若這個點不是墻，則可以到達這個點的所有點，是能夠到達這個點上方點的所有點和能夠到達這個點左邊的所有點的并集，用公式描述一下就是

KaTeX parse error: No such environment: equation at position 8: \begin{?e?q?u?a?t?i?o?n?}? dp[i][j] =…

如此計算我們可以得到第一份代碼

#include "bits/stdc++.h"

using namespace std;

struct Node {
    int x1, y1, x2, y2, i;

    bool operator<(const Node &rhs) const {
        return x2 < rhs.x2;
    }
};

void solve() {
    const int N = 510;
    const int M = 510;

    // 讀取地圖
    int n, m;
    cin >> n >> m;
    vector<bitset<M>> graph(n);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            graph[i][j] = c == '0';
        }
    }

    // 前綴和解決 1 和 2 型號的
    vector<vector<int>> modelList[2];
    for (auto &model: modelList) {
        model.resize(n);
        for (auto &item: model)
            item.resize(m, 0);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            modelList[0][i][j] = (i != 0 ? modelList[0][i - 1][j] : 0) + !graph[i][j];
            modelList[1][i][j] = (j != 0 ? modelList[1][i][j - 1] : 0) + !graph[i][j];
        }
    }

    int q;
    cin >> q;
    vector<bool> ans(q);    // 離線計算答案
    vector<Node> query;
    query.reserve(q);

    for (int i = 0; i < q; ++i) {
        int t, x1, y1, x2, y2;
        cin >> t >> x1 >> y1 >> x2 >> y2;
        // 下標從 0 開始
        x1 -= 1;
        y1 -= 1;
        x2 -= 1;
        y2 -= 1;

        if (t == 1) ans[i] = (y1 == y2) and (x1 <= x2) and (modelList[0][x1][y1] == modelList[0][x2][y2]);
        else if (t == 2) ans[i] = (x1 == x2) and (y1 <= y2) and modelList[1][x1][y1] == modelList[1][x2][y2];
        else {
            if (x1 > x2 || y1 > y2) ans[i] = false;
            else query.push_back((Node) {x1, y1, x2, y2, i});
        }
    }

    sort(query.begin(), query.end());

    auto hashNode = [&](const int &x, const int &y) {
        return x * n + y;
    };

    vector<bitset<N * M>> dp(m);
    for (int i = 0; i < m; ++i) {
        dp[i].reset();
        dp[i][hashNode(0, i)] = graph[0][i];
    }

    int curQuery = 0;

    for (int i = 0; i < n; ++i) {
        // 離線計算每個位置哪些可以到達
        if (!graph[i][0]) dp[0].reset();
        else dp[0][hashNode(i, 0)] = true;
        for (int j = 1; j < m; ++j) {
            if (!graph[i][j]) dp[j].reset();
            else {
                dp[j][hashNode(i, j)] = true;
                dp[j] |= dp[j - 1];
            }
        }
        while (curQuery < query.size()) {
            if (query[curQuery].x2 == i) {
                ans[query[curQuery].i] = dp[query[curQuery].y2][hashNode(query[curQuery].x1, query[curQuery].y1)];
                curQuery++;
            } else break;
        }
    }

    for (int i = 0; i < q; ++i)
        cout << (ans[i] ? "yes" : "no") << endl;
}

讓我們計算一下復雜度: O ( n 4 ) = 50 0 4 = 62 , 500 , 000 , 000 O(n^4) = 500^4 = 62,500,000,000 O(n4)=5004=62,500,000,000，這肯定不行，就算壓位也不能通過

所以需要優化

問題出在需要計算所有的點可達問題，這就導致了計算一個節點就需要 O ( n 2 ) O(n^2) O(n2) 的時間，非常不合理

如果試圖減少一個 n n n，那么我們只能計算能否到達某一行或者某一列的值，而不能計算全部

但是考慮雙向，如果我們知道出發點能夠到達某個節點，而目標點可以來自同一個點，那么也同樣可以說明可以到達

所以這個特殊的一行或者一列將地圖分為兩半，同時若詢問是跨立在這一行或者這一列，則可以回答，但是對于沒有跨立的如何解決？

分治

以橫向為例，不斷取橫向中間軸作為特定行，不斷計算跨此軸的詢問的解，復雜度為 O ( n 3 l o g n ) = 50 0 3 ? l o g ( 500 ) = 337 , 371 , 250 O(n^3logn) = 500^3 * log(500) = 337,371,250 O(n3logn)=5003?log(500)=337,371,250，似乎可行

可以得到第二份代碼

#include "bits/stdc++.h"

using namespace std;

const int QUERY_LEN = 1e5 + 10;
const int NUM = 505;
const int DIV = 505;

char mp[NUM][NUM];
int n, m, ans[QUERY_LEN];
int L[NUM][NUM], U[NUM][NUM];
struct node {
    int id, x1, y1, x2, y2;
};
vector<node> queryList;
unsigned vis1[NUM][NUM][DIV], vis2[NUM][NUM][DIV];

void reset(unsigned *v) {
    memset(v, 0, sizeof(unsigned) * DIV);
}

void cpFlag(unsigned *dist, const unsigned *from) {
    memcpy(dist, from, sizeof(unsigned) * DIV);
}

void orFlag(unsigned *dist, const unsigned *from) {
    for (int i = 0; i < DIV; ++i) dist[i] |= from[i];
}

void setFlagTrue(unsigned *v, int id) {
    v[id] = 1;
}

bool andFlagAny(const unsigned *a, const unsigned *b) {
    for (int i = 0; i < DIV; ++i) if (a[i] & b[i]) return true;
    return false;
}

void dfs(int l, int r, vector<node> &q) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    for (int i = mid; i >= l; i--) {
        for (int j = m; j >= 1; j--) {
            reset(vis1[i][j]);
            if (mp[i][j] == '1') continue;
            if (i == mid) setFlagTrue(vis1[i][j], j);
            else cpFlag(vis1[i][j], vis1[i + 1][j]);
            orFlag(vis1[i][j], vis1[i][j + 1]);
        }
    }
    for (int i = mid; i <= r; i++) {
        for (int j = 1; j <= m; j++) {
            reset(vis2[i][j]);
            if (mp[i][j] == '1') continue;
            if (i == mid) setFlagTrue(vis2[i][j], j);
            else cpFlag(vis2[i][j], vis2[i - 1][j]);
            orFlag(vis2[i][j], vis2[i][j - 1]);
        }
    }
    vector<node> vl, vr;
    for (auto it: q) {
        if (it.x2 < mid) vl.push_back(it);
        else if (it.x1 > mid) vr.push_back(it);
        else ans[it.id] = andFlagAny(vis1[it.x1][it.y1], vis2[it.x2][it.y2]);
    }
    dfs(l, mid - 1, vl);
    dfs(mid + 1, r, vr);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == '0') L[i][j] = L[i][j - 1] + 1;
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (mp[i][j] == '0') U[i][j] = U[i - 1][j] + 1;
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int op, x1, x2, y1, y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2 || y1 > y2) {
            ans[i] = 0;
            continue;
        }
        if (op == 1) {
            if (y1 != y2 || U[x2][y2] < x2 - x1) ans[i] = 0;
            else ans[i] = 1;
        } else if (op == 2) {
            if (x1 != x2 || L[x2][y2] < y2 - y1) ans[i] = 0;
            else ans[i] = 1;
        } else {
            queryList.push_back({i, x1, y1, x2, y2});
        }
    }
    dfs(1, n, queryList);

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "yes\n" : "no\n");
}

但是，還是不對，實際上是空間超限了

仔細思考，實際上我們使用了 int 來模擬一個布林值組，非常浪費空間，可以進行壓位，得到最終的代碼，此時的復雜度為 O ( n 3 l o g n / 64 ) = 50 0 3 ? l o g ( 500 ) / 64 = 5 , 271 , 425 O(n^3logn / 64) = 500^3 * log(500) / 64 = 5,271,425 O(n3logn/64)=5003?log(500)/64=5,271,425，

#include "bits/stdc++.h"

using namespace std;

const int QUERY_LEN = 1e5 + 10;
const int NUM = 505;
const int DIV = 8;
const int LEN = 64;
typedef unsigned long long bits;

char mp[NUM][NUM];
int n, m, ans[QUERY_LEN];
int L[NUM][NUM], U[NUM][NUM];
struct node {
    int id, x1, y1, x2, y2;
};
vector<node> queryList;
bits vis1[NUM][NUM][DIV], vis2[NUM][NUM][DIV];

void reset(bits *v) {
    memset(v, 0, sizeof(bits) * DIV);
}

void cpFlag(bits *dist, const bits *from) {
    memcpy(dist, from, sizeof(bits) * DIV);
}

void orFlag(bits *dist, const bits *from) {
    for (int i = 0; i < DIV; ++i) dist[i] |= from[i];
}

void setFlagTrue(bits *v, int id) {
    v[id / LEN] |= ((bits) 1u) << (id % LEN);
}

bool andFlagAny(const bits *a, const bits *b) {
    for (int i = 0; i < DIV; ++i) if (a[i] & b[i]) return true;
    return false;
}

void dfs(int l, int r, vector<node> &q) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    for (int i = mid; i >= l; i--) {
        for (int j = m; j >= 1; j--) {
            reset(vis1[i][j]);
            if (mp[i][j] == '1') continue;
            if (i == mid) setFlagTrue(vis1[i][j], j);
            else cpFlag(vis1[i][j], vis1[i + 1][j]);
            orFlag(vis1[i][j], vis1[i][j + 1]);
        }
    }
    for (int i = mid; i <= r; i++) {
        for (int j = 1; j <= m; j++) {
            reset(vis2[i][j]);
            if (mp[i][j] == '1') continue;
            if (i == mid) setFlagTrue(vis2[i][j], j);
            else cpFlag(vis2[i][j], vis2[i - 1][j]);
            orFlag(vis2[i][j], vis2[i][j - 1]);
        }
    }
    vector<node> vl, vr;
    for (auto it: q) {
        if (it.x2 < mid) vl.push_back(it);
        else if (it.x1 > mid) vr.push_back(it);
        else ans[it.id] = andFlagAny(vis1[it.x1][it.y1], vis2[it.x2][it.y2]);
    }
    dfs(l, mid - 1, vl);
    dfs(mid + 1, r, vr);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == '0') L[i][j] = L[i][j - 1] + 1;
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            if (mp[i][j] == '0') U[i][j] = U[i - 1][j] + 1;
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int op, x1, x2, y1, y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2 || y1 > y2) {
            ans[i] = 0;
            continue;
        }
        if (op == 1) {
            if (y1 != y2 || U[x2][y2] < x2 - x1) ans[i] = 0;
            else ans[i] = 1;
        } else if (op == 2) {
            if (x1 != x2 || L[x2][y2] < y2 - y1) ans[i] = 0;
            else ans[i] = 1;
        } else {
            queryList.push_back({i, x1, y1, x2, y2});
        }
    }
    dfs(1, n, queryList);

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "yes\n" : "no\n");
}

當然，如果你了解 bitset 的話，那么就更好辦了