【CF1047D】Little C Loves 3 II【构造】【赛瓦维斯特定理】

传送门

题意：给一个$N\times M$的空棋盘，每次选取两个曼哈顿距离为3的空格子放上棋子，问最多能放多少个。

$1\le N,M\le 1e9$

暴力讨论

假装$N\le M$

①$N=1$

容易得到，详见代码

②$N=2$

构造几组小的(0表示空)

$2\times 2$
0 0
0 0

$2\times 3$
1 0 2
2 0 1

$2\times 4$

1 2 3 4
3 4 1 2

$2\times 5$
1 3 2 4 3
5 4 1 5 2

$2\times 6$

1 2 3 1 2 3
4 5 6 4 5 6

$2\times 7$

1 2 3 1 2 3 0
4 5 6 4 5 6 0

由小凯定理 赛瓦维斯特定理，由4和5拼起来最大不能凑出$4\times 5-4-5=11$，即11以上的都能凑出

而$8=4+4,9=4+5,10=5+5，11=5+6$

所以除了$2,3,7$都可以填满

③$N>2$,$NM$为偶数

首先上面凑出了$2\times 4$

两个$2\times 3$凑出$3\times 4$

这样最大不能凑出$2\times 3-2-3=1$,所以所有$4\times M$都可以凑出来

用$M$个$1\times 6$凑出$6\times M$

以两个为单位，所有都可以凑出

所以偶数都可以填满

④$N>2$,$NM$为奇数

首先必须空一格

$3\times 3$

1 2 4
4 0 3
3 1 2

把它从角落上挖掉，剩下的都是偶数……

等等，是5怎么办？

构造啊

$3\times 5$

1 2 3 4 5
6 7 5 6 7
0 1 2 3 4

$5\times 5$

1 2 3 4 5
6 4 1 2 3
7 8 0 7 8
10 11 12 9 5
6 9 10 11 12

完

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if (n>m) swap(n,m);
switch(n)
{
case 1:cout<<m/6*6+2*max(m%6-3,0);break;
case 2:
switch(m)
{
case 2:cout<<0;break;
case 3:cout<<4;break;
case 7:cout<<12;break;
default:cout<<2*m;break;
}
break;
default:cout<<1ll*n*m/2*2;break;
}
return 0;
}

最后

以上就是霸气小伙为你收集整理的【CF1047D】Little C Loves 3 II【构造】【赛瓦维斯特定理】的全部内容，希望文章能够帮你解决【CF1047D】Little C Loves 3 II【构造】【赛瓦维斯特定理】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。