二分图经典题型——Domino for Young

· · 题解

传送门

这是一道作业题。

先考虑普通二分图，但是数据庞大，会被T。

所以对格子进行二分图染色，答案是两种格子数量的较小值。

比如上面这张图，我们先设左下角的格子为黑，通过染色得出下图。

然后，我们就可以发现一个结论：

1：当一列格子数为偶数时，黑色格子与白色格子数量相同。

2：当一列格子数为奇数时，由于左下角的格子我们设成了黑色，所以不难发现当是第i列（i是奇数）时的最上面的格子是黑色的，第i列（i是偶数）时的最上面的格子是白色的。

部分代码：

for(int i=1;i<=n;i++)
{
    black+=a[i]/2;
    white+=a[i]/2;//黑色白色格子数目均分
    if(a[i]%2)
    {
        if(i%2) black++;
        else white++;//上面我已经说过了
    } 
}

谢谢观看