Codeforces Round #588 (Div. 2)

题目链接：https://codeforces.com/contest/1230

A - Dawid and Bags of Candies

随便弄一下。

B - Ania and Minimizing

随便弄一下。

C - Anadi and Domino

看到这个题目意识到我好像做过这套题。

那么好像我是看过题解的，但是我没有补。

题意：给21种多米诺骨牌，以及不超过7个点的一个简单图，把多米诺骨牌放在边上，使得图的点对应多米诺骨牌的颜色。求最多能放多少个骨牌？

题解：多米诺骨牌的6种颜色是完全等价的，所以n<=6的时候每个点就染一种颜色即可。否则枚举7号点的颜色，然后贪心放就可以。

int edge[8][8];
int used[8][8];

void TestCase() {
    for(int i = 1; i <= 6; ++i) {
        for(int j = 1; j <= 6; ++j)
            edge[i][j] = 0;
    }
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u][v] = 1;
        edge[v][u] = 1;
    }
    if(n <= 6) {
        printf("%d\n", m);
        return;
    }
    for(int i = 1; i <= 6; ++i) {
        for(int j = 1; j <= 6; ++j)
            used[i][j] = 0;
    }
    int cnt = 0;
    for(int i = 1; i <= 6; ++i) {
        for(int j = 1; j <= 6; ++j) {
            if(edge[i][j] && used[i][j] == 0) {
                used[i][j] = 1;
                used[j][i] = 1;
                ++cnt;
            }
        }
    }
    int ans = cnt;
    for(int k = 1; k <= 6; ++k) {
        int tmp = 0;
        for(int i = 1; i <= 6; ++i) {
            if(edge[7][i] && used[k][i] == 0)
                ++tmp;
        }
        ans = max(ans, cnt + tmp);
    }
    printf("%d\n", ans);
    return;
}

上面这个代码WA10，想了想，不能强行要求7号点和前面的点同色，也可能同色的点在前面。所以应该两维枚举同色的点，然后给其他点染色再贪心分配。

Codeforces Round #588 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/12650612.html