2298 - L2105 的题解

回去原题
#想到暴力方法,开n*m的哈希,模拟每个棋子的放置,其中行、列和2条对角线各要模拟一遍,时间O(k*(m+n)),统计答案要O(m*n),总计O(k*(m+n)+m*n),空间O(n*m),可以得30%的分。
对于k=1,则计算行、列和对角线上一共有多少格子被覆盖,时间O(1),空间O(1),可以再得10%的分。
再看16M的空间,显然不能开n*m的哈希,尝试只开m的哈希。
用ans记录答案,对于每一行,我们共享一个哈希h,h[i]表示该行第i格的状况;初始剩余棋子t=m,穷举每个棋子,可以计算这个棋子与这一行的相交情况,在处理相交时分类:
1.该棋子覆盖整个一行,则t=0,退出循环
2.该棋子相交的格子在这行没有被覆盖过,则t-1,该格标记为覆盖
3.该棋子相交的格子在这行被覆盖过,t不变
每行完后ans+t。
小技巧:为了防止重复清空h,可以打上时间戳,第i行中,h[j]=i表示j被覆盖,否则表示在以前被覆盖(这一行没被覆盖)。
时间O(n*k),空间O(m),可以得100%的分数。
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int x[501],y[501],h[20001];
int main()
{
    int n,m,k,i,j,ans,t;
    scanf("%d%d%d",&n,&m,&k);
    memset(h,0,sizeof(h));
    for (i=1;i<=k;i++) scanf("%d%d",&x[i],&y[i]);
    ans=0;
    for (i=1;i<=n;i++)
    {
        t=m;
        for (j=1;j<=k;j++)
            if (x[j]==i)
            {
                t=0;
                break;
            } else
            {
                if (h[y[j]]!=i)
                {
                    h[y[j]]=i;
                    t--;
                }
                if ((i+y[j]-x[j])>0 && (i+y[j]-x[j])<=m && h[i+y[j]-x[j]]!=i)
                {
                    h[i+y[j]-x[j]]=i;
                    t--;
                }
                if ((y[j]+x[j]-i)>0 && (y[j]+x[j]-i)<=m && h[y[j]+x[j]-i]!=i)
                {
                    h[y[j]+x[j]-i]=i;
                    t--;
                }
            }
        ans+=t;
    }
    printf("%d\n",ans);
    return 0;
}