题解 P5441 【【XR-2】伤痕】

· · 题解

题目大意

前置知识

题解

一组不强连通的四个点只有 3 种可能：

  1. 从一个点向另外三个点各连一条有向边，记这样的四个点有 X 组。
  2. 在不满足第 1 种可能的前提下，从三个点向另外一个点各连一条有向边。
  3. A 与 B、C 与 D 之前都是无向边，但从 A 向 CD 各连一条有向边，从 B 向 CD 各连一条有向边。

记点 i 向其它点连的有向边有 S_i 条。

因为 n 为奇数，有：

\sum_{i = 1}^{n} S_i = \frac{n \times (n - 1)}{2} - n = n \times \frac{n - 3}{2}

又 C_{x}^{3} = \frac{x \times (x - 1) \times (x - 2)}{6} 在 x \ge 3 时为凸函数，有：

X = \sum_{i = 1}^{n} C_{S_i}^{3} \ge n \times C_{\frac{n - 3}{2}}^{3}

因此，最少有 n \times C_{\frac{n - 3}{2}}^{3} 组第一种可能的不强连通的四个点。

接下来，我们只需要构造出只有 n \times C_{\frac{n - 3}{2}}^{3} 组第一种可能，没有第二、三种可能的建边方案即可。

构造方案显然不唯一，接下来给出一种构造方案：

将 n 个点放在一个圆内接正 n 边形的顶点上，所有最长的对角线为无向边，每个点都向顺时针接下来的 \frac{n - 3}{2} 个点连一条有向边。

显然，这种构造方案满足条件。

综上所述，最终的答案为：

C_{n}^{4} - n \times C_{\frac{n - 3}{2}}^{3} = \frac{n(n-3)(n^2+6n-31)}{48}

注意 n = 1 时需要特判。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << endl << 0 << endl;
        return 0;
    }
    cout << n * (n - 3) * (n * n + 6 * n - 31) / 48 << endl;
    int m = (n + 1) >> 1;
    for (int i = 1; i <= n; i++) {
        int a[n+1];
        memset(a, 0, sizeof(a));
        for (int j = 1; j <= m; j++)
            a[(i+j-1)%n+1] = 1;
        for (int j = 1; j < n; j++) cout << a[j] << " ";
        cout << a[n] << endl;
    }
    return 0;
}

Special Judge

#include "testlib.h"

#define AC return quitf(_ok, "The answer is correct."), 0
#define WA return quitf(_wa, "The answer is wrong."), 0
#define WArules return quitp(0.5, "The answer is correct, but your plan breaks the rules."), 0
#define WAplan return quitp(0.5, "The answer is correct, but your plan is wrong."), 0

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    int n = inf.readInt(), ans = ouf.readInt(), a[n+1][n+1];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = ouf.readInt();

    if ((n == 1 && ans) || (n != 1 && ans != n * (n - 3) * (n * n + 6 * n - 31) / 48)) WA;

    int cnt = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (a[i][j] && a[i][j] != 1) WArules; 
            if (i == j) {
                if (a[i][j]) WArules;
            } else {
                if (!a[i][j] && !a[j][i]) WArules;
                if (i < j && a[i][j] && a[j][i]) ++cnt;
            }
        }

    if (cnt > n) WArules;

    int k = 0, p[5];

    for (p[1] = 1; p[1] <= n; p[1]++)
        for (p[2] = p[1] + 1; p[2] <= n; p[2]++)
            for (p[3] = p[2] + 1; p[3] <= n; p[3]++)
                for (p[4] = p[3] + 1; p[4] <= n; p[4]++) {
                    bool flag = 0;
                    int o[5];
                    for (int i = 1; i <= 4; i++) o[i] = p[i];
                    do if (a[o[1]][o[2]] && a[o[2]][o[3]] && a[o[3]][o[4]] && a[o[4]][o[1]]) flag = 1;
                    while (!flag && std::next_permutation(o + 1, o + 5));
                    k += flag;
                }

    if (k != ans) WAplan;
    AC;
}