cf 611 A||codeforces goodbye 2015 C. New Year and Domino

Posted by 111qqz on Friday, January 1, 2016

TOC

http://codeforces.com/contest/611/problem/C 题意:给出一个n*m的地图,.表示可以空,#表示墙。一个东西需要占两个相邻的格子,问给定一个矩形,放一个东西的方案数。 思路:q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下,每次标记到后一个点。然后二维的前缀和。然后每次询问的时候,去掉最上边和最左边两条边界上对应的多加的点。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>

using namespace std;

const int N=5E2+7;
char maze[N][N];
int n,m;
int q;
int a[N][N],b[N][N];
int sum[N][N];
int sum2[N][N];
    
int main()
{
    cin>>n>>m;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for ( int i = 0  ; i< n ;i++ ) scanf("%s",maze[i]);
    for ( int i = 1 ;  i < n ; i++)
    {
        for (int  j =  0 ; j< m ;j++)
        {
        if (maze[i][j]=='.'&&maze[i-1][j]=='.')
            a[i+1][j+1]++;
        }
    }
	
    for ( int i = 0 ; i < n ; i++)
    {
        for ( int j = 1 ;  j < m ; j++)
        {
        if (maze[i][j]=='.'&&maze[i][j-1]=='.')
            b[i+1][j+1]++;
        }
    }
    sum[0][0] = 0;
    sum2[0][0] =  0;
    for ( int i = 1 ; i <= n ; i++)
    {
        for ( int j = 1 ;  j<= m ; j++)
        {
        sum[i][j] =sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        sum2[i][j] = sum2[i-1][j]+sum2[i][j-1]-sum2[i-1][j-1] + b[i][j];
        }
    }
    cin>>q;

    while (q--)
    {
        int n1,n2,m1,m2;
        scanf("%d %d %d %d",&n1,&m1,&n2,&m2);
        int ans = 0 ;
        ans+=sum[n2][m2]-sum[n1-1][m2]-sum[n2][m1-1]+sum[n1-1][m1-1];
        ans+=sum2[n2][m2]-sum2[n1-1][m2]-sum2[n2][m1-1]+sum2[n1-1][m1-1];
        for ( int j = m1 ; j <= m2 ;j++)
        {
        if (a[n1][j]==1) ans--;
        }
        for ( int i = n1 ; i <= n2 ; i++)
        {
        if (b[i][m1]==1) ans--;
        }
	        
        printf("%d\n",ans);
    }

    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付