Codeforces Global Round 12 1450.C2. Errich-Tac-Toe (Hard Version)(构造,三分图)

link

考虑对这个图染色分类, ( i , j ) (i,j) (i,j)格子归为 ( i + j ) % 3 (i+j)%3 (i+j)%3类

然后在这三类格子中看看哪一类的标记最少,把那一类的 X rm X X都改成 O rm O O

这样做一定合法,因为任何连续的三个格子一定包含我们修改过的 O rm O O

#include 
using namespace std;
const int maxn = 3e5+10;
int t,n,kl[19];
char a[509][509];
int main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n;
		for(int i=1;i<=n;i++)	cin >> ( a[i]+1 );
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if( a[i][j]=='X' )	kl[(i+j)%3]++;
		int mi = 1e9, type = 0;
		for(int i=0;i<=2;i++)
			if( kl[i] 
Hard Version 
现在既有
    
     
      
       
        X
       
      
      
       rm X
      
     
    X又有
    
     
      
       
        O
       
      
      
       rm O
      
     
    O,无脑改变的话行不通了
 
但是可以仍然把格子花费为三类
 
考虑让
    
     
      
       
        x
       
      
      
       x
      
     
    x类格子的
    
     
      
       
        O
       
      
      
       rm O
      
     
    O变成
    
     
      
       
        X
       
      
      
       rm X
      
     
    X,让
    
     
      
       
        y
       
      
      
       y
      
     
    y类格子的
    
     
      
       
        X
       
      
      
       rm X
      
     
    X变成
    
     
      
       
        O
       
      
      
       rm O
      
     
    O(
    
     
      
       
        x
       
       
        !
       
       
        =
       
       
        y
       
      
      
       x!=y
      
     
    x!=y)
 
这样任意相邻三个格子必定存在不同标记的格子,而且通过枚举
    
     
      
       
        x
       
       
        ,
       
       
        y
       
      
      
       x,y
      
     
    x,y必然存在满足条件的解
 
#include 
using namespace std;
const int maxn = 3e5+10;
int t,n,kl[19][2];
char a[509][509];
int main()
{
	cin >> t;
	while( t-- )
	{
		cin >> n;
		for(int i=1;i<=n;i++)	cin >> ( a[i]+1 );
		memset( kl,0,sizeof kl );
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if( a[i][j]=='X' )	kl[(i+j)%3][0]++;
			else if( a[i][j]=='O' )	kl[(i+j)%3][1]++;
		}
		int mi = 1e9, x = 0, y = 0;
		for(int i=0;i<=2;i++)
		for(int j=0;j<=2;j++)
		{
			if( i==j )	continue;
			if( kl[i][0]+kl[j][1]