abc258（G）

本文主要是介绍abc258（G），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

G - Triangle

题意：给定一个邻接矩阵，问有多少个三元组(x, y, z)满足两两顶点之间有一条边直接相连。

该题使用bitset可以快速解决。
首先预处理 bitset b[i], b[i][j] = 1表示有边，否则无边。
然后选中两个点(x, y)，且(x, y)之间有边。
b[x] & b[y] 为一个新的bitset，当bitset[z] 表示 x 和 y 同时与 z 有边。
因此最终的答案为：\((\sum_{i = 1}^{n}\sum_{j = 1}^{n}(b[i]\&b[j]).count() * b[i][j]) / 6\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
typedef long long ll;
const int N = 3000 + 5;
bitset<N> d[N];
char s[N];
int main() {
    int T = 1;
//    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            for (int j = 1; j <= n; j++) {
                d[i][j] = s[j] - '0';
            }
        }
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                res += (d[i] & d[j]).count() * d[i][j];
            }
        }
        printf("%lld\n", res / 6);
    }
    return 0;
}

这篇关于abc258（G）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！