bzoj2462: [BeiJing2011]矩阵模板

我就是我 2021-10-26 13:31 245阅读 0赞

[咕咕咕][Link 1]

这题数据有点水...我直接求矩阵和，比较矩阵大小...还a了

矩阵hash棵题

![1542296-20190809093429027-595034030.png][]

唉...懒得写正解了...既然假的都过了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//bzoj 2462
    //二维hash
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    inline int read()
    {
        int sum = 0,p = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9')
        {
            if(ch == '-')
                p = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            (sum *= 10) += ch - '0';
            ch = getchar();
        }
        return sum * p;
    }
    const int N = 1009;
    int n,m,na,mb,cnt,p[N][N],a[N][N],b[N][N];
    bool flag;
    int main()
    {
        n = read(),m = read(),na = read(),mb = read();
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%1d",&a[i][j]);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                p[i][j] = p[i][j - 1] +p[i - 1][j] - p[i - 1][j - 1] + a[i][j];
        int q = read();
        for(int i = 1;i <= q;i++)
        {
            flag = false;
            cnt = 0;
            for(int i = 1;i <= na;i++)
                for(int j = 1;j <= mb;j++)
                {
                    scanf("%1d",&b[i][j]);
                    cnt += b[i][j];
                }
            for(int i = na;i <= n;i++)
                for(int j = mb;j <= m;j++)
                    if(cnt == p[i][j] - p[i][j - mb] - p[i - na][j] + p[i - na][j - mb])
                    {
                        printf("1\n");
                        flag = true;
                        i = n + 1;
                        j = m + 1;
                    }
            if(!flag)
                printf("0\n");
        }
        return 0;
    }

假的正解

转载于:https://www.cnblogs.com/darlingroot/p/11325194.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=2462
[1542296-20190809093429027-595034030.png]: /images/20211026/5912b8ac83894577a3c503d74d314770.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/4c524d12a0cb4e3a9be00558f59a8ab7.png