Gym - 101350G (容斥原理)

83 阅读 0 评论 55 点赞

我是靠谱客的博主帅气春天，最近开发中收集的这篇文章主要介绍Gym - 101350G (容斥原理)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

G. Snake Rana
time limit per test4.0 s
memory limit per test256 MB
inputstandard input
outputstandard output
Old Macdonald wants to build a new hen house for his hens. He buys a new rectangular area of size N by M. The night before he builds the hen house, snake Rana devises an evil plan to plant bombs in K distinct cells in the area to kill the hens and eat them for dinner later.

The morning of, Old Macdonald notices that each of the K cells, where snake Rana planted a bomb, have a marking on them. That won’t stop him though, all he must do is build the hen house in an area with no bombs.

Assume that rows are numbered from top to bottom, and columns are numbered from left to right. Old Macdonald now wants to know the number of ways he can choose sub-rectangles of top left coordinates (x1, y1) and bottom right coordinates (x2, y2) (x1 ≤ x2) (y1 ≤ y2) such that there are no bombs in the sub rectangle.

Input
The first line of input is T – the number of test cases.

The first line of each test case is three integers N, M, and K (1 ≤ N, M ≤ 104) (1 ≤ K ≤ 20).

The next K lines each contains distinct pair of integers x, y (1 ≤ x ≤ N) (1 ≤ y ≤ M) - where (x, y) is the coordinate of the bomb.

Output
For each test case, output a line containing a single integer - the number of sub-rectangles that don’t contain any bombs.

Example
input
3
2 2 1
2 2
6 6 2
5 2
2 5
10000 10000 1
1 1
output
5
257
2500499925000000

容斥原理裸题总情况-必定包含一个点的情况+必定包含两个点的情况-3个点+……

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define inf 1e9
const int maxn = 1e5+100;
struct p
{
    long long x,y;

}a[maxn];
int main()
{

    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long m,n,k;
        scanf("%I64d%I64d%I64d",&n,&m,&k);
        for (int i=0;i<k;i++)
            scanf("%I64d%I64d",&a[i].x,&a[i].y);
        long long ans=(n+1)*n/2*(m+1)*m/2;
        for (int s=1;s<(1<<k);s++)
        {
            long long minx=inf,miny=inf,maxx=-1,maxy=-1;
            int cnt=0;
            for (int i=0;i<k;i++)
            {
                 if (s>>i&1)
                 {
                     minx=min(minx,a[i].x);
                     miny=min(miny,a[i].y);
                     maxx=max(maxx,a[i].x);
                     maxy=max(maxy,a[i].y);
                     cnt++;
                 }
            }
            long long res=minx*miny*(n-maxx+1)*(m-maxy+1);
            if (cnt&1) ans-=res;
            else ans+=res;
        }
        printf("%I64dn",ans);

    }



}