操場上的莓果 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： YummyBerry

觀看題解前請先好好想過題目，觀看完題解後也想想為什麼這樣寫能AC，如果你因此寫出比我效率更好的程式就更棒了٩(◦`꒳´◦)۶。

這題明顯不能直接用迴圈算矩形內的空格子(TLE)。

因此我們要做預處理，可以發現空格子數量不會被改變。

所以此題只要利用 二維前綴和 即可。 https://walkonnet.com/archives/462481 <-關於前綴和的文章

然後有一點要注意的是題目是先給y再給x。

以下是程式碼。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define sakura ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

signed main()
{
    sakura int n, q;
    cin >> n >> q;

    vector<vector<int>> pre(n + 1, vector<int>(n + 1, 0)); // 多+1可以減少一點麻煩
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        for (int j = 1; j <= n; j++)
        {
            if (str[j - 1] == '*')
            {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + 1;
            }
            else
            {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
            }
        }
    }

    while (q--)
    {
        int y1, x1, y2, x2, ans;
        cin >> y1 >> x1 >> y2 >> x2;
        ans = pre[y2][x2] - pre[y2][x1 - 1] - pre[y1 - 1][x2] + pre[y1 - 1][x1 - 1];
        cout << ans << "\n";
    }

    return 0;
}

评论


  • 0
    YummyBerry  于2023年6月4日 14:26评论

    不對吧 怎麼前言也跑進來了ﾚ(ﾟ∀ﾟ;)ﾍ