容斥原理·Gym101350G·Snake Rana

题目大意：n*m的矩阵问不包含炸弹的子矩阵总数；

解题思路：

奇加偶减容斥。

AC代码：

#include <iostream>
#include <cmath>
#include<cstdio>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;
#define maxd 10000 + 10
#define inf 0x3f3f3f3f3f3f3f3f

ll n, m, k;
struct node {
    ll x, y;
};
node ac[maxd];

int main() {
    int t;
    cin >> t;
    while(t --) {
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++) {
            cin >> ac[i].x >> ac[i].y ;
        }
        ll ans = (n + 1) * n/2 * (m + 1) * m/2;
       // cout << "ans :: " << ans << endl;
        for (int i = 1; i < (1<<k); i++) {
            ll cnt = 0;
//            ll LU = 0, LD = 0, RU = 0, RD = 0;
            ll max_x = 0;
            ll min_x = inf;
            ll max_y = 0;
            ll min_y = inf;
            for(int j = 0; j < k; j++) {
                if(i>>j&1) {
                    max_y = max(max_y, ac[j].y);
                    min_y = min(min_y, ac[j].y);
                    max_x = max(max_x, ac[j].x);
                    min_x = min(min_x, ac[j].x);
                    cnt ++;
                }
            }
            //ll nn = max_y - min_y;
           // ll mm = max_x - min_x;
            //ll res = (nn+1) * nn/2 * (mm + 1) * mm/2;
            ll res = min_x * min_y * (n - max_x + 1) * (m - max_y + 1);
            //cout << "res : " << res << endl;
            if(cnt & 1) {
                ans -= res;
            }
            else {
                ans += res;
            }
        }
        cout << ans << endl;
    }
}

最后

以上就是可爱发带为你收集整理的容斥原理·Gym101350G·Snake Rana的全部内容，希望文章能够帮你解决容斥原理·Gym101350G·Snake Rana所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。