nowcoder多校6-Androgynos(构造+同构)

题目链接:nowcoder多校6-Androgynos

题意:

给n个点,要求构造出一个图G,使图G与其补图G'同构。

题解:

显然,同构的两个图的边数需要相等,所有只有当n阶完全图的边数为偶数时有解。

然后,我们可以分情况讨论:

  1. n=4k
  2. n=4k+1

对于两种情况,我们都可以先把点分为四部分A,B,C,D。首先把A和B构造成完全图,然后C中每个点与A中每个点相连,D中每个点与B中每个点相连。当n=4k+1时,多余的那个点与两个团相连。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e3 + 3;
const ll inf = 0x7f7f7f7f7f7f7f7f;
int T, n;
int mp[MAXN][MAXN];
int f[MAXN];
int main()
{
    scanf("%d", &T);
    int icase = 0;
    while (T--)
    {
        scanf("%d", &n);
        memset(f, 0, sizeof(f));
        memset(mp, 0, sizeof(mp));
        int tmp = n * (n - 1) / 2;
        if (tmp % 2)
        {
            printf("Case #%d: No\n", ++icase);
            continue;
        }
        printf("Case #%d: Yes\n", ++icase);
        for (int i = 1; i <= n / 2; i++)
            for (int j = i + 1; j <= n / 2; j++)
                mp[i][j] = mp[j][i] = 1;

        for (int i = 1; i <= n / 4; i++)
            for (int j = n / 2 + 1; j <= n / 4 * 3; j++)
                mp[i][j] = mp[j][i] = 1;
        for (int i = n / 4 + 1; i <= n / 2; i++)
            for (int j = n / 4 * 3 + 1; j <= n / 4 * 4; j++)
                mp[i][j] = mp[j][i] = 1;
        for (int i = 1; i <= n / 2; i++)
            f[i] = i + n / 2;
        int temp = n / 4 * 4;
        for (int i = n / 2 + 1; i <= n; i++)
            f[i] = temp - i + 1;
        if (n % 4 == 1)
        {
            for (int i = 1; i <= n / 2; i++)
                mp[i][n] = mp[n][i] = 1;
            f[n] = n;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                printf("%d", mp[i][j]);
            puts("");
        }
        for (int i = 1; i <= n; i++)
            if (i != n)
                printf("%d ", f[i]);
            else
                printf("%d\n", f[i]);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。