D - AB Graph (构造、图)

不念不忘少年蓝@ 2021-07-16 13:14 432阅读 0赞

[题目][Link 1]

思路：  
分为两种情况：  
1.当m为奇数时，直接12121212…构造出的一定是回文。  
2.当m为偶数时，可以知道n>=3时一定可以构造出。证明如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]当1，2，3三个点中出现来回字母一样，只需两个点不断循环即可。

当无上述情况，来回必然是a,b交叉，因此我们一定可以找到如下的图。其实就是有连续两个a，1->2->3->1,或2->3->1->2，或3->1->2->3，这几种情况aab,aaa,aba…因为是循环的一定可以找出两个连续的a构成下图。（不懂可以自行模拟下过程）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]当(m/2)%2 == 1  
我们可以按序号123212321232…走构造出aabbaabb…aabb，  
当(m/2)%2==0  
我们可以按序号232123212321走构造出  
abbaabba…abba

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e3 + 5;
    char lst[Max][Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n, m;cin >> n >> m;
    		for (int i = 1;i <= n;i++)
    			for (int j = 1;j <= n;j++)cin>>lst[i][j];
    		if (m % 2 == 1)
    		{ 
    			cout << "YES" << endl;
    			for (int i = 1;i <= m + 1;i++)
    				if (i % 2 == 0)cout << "1 ";
    				else cout << "2 ";
    			cout << endl;
    		}
    		else
    		{ 
    			if (n == 2)
    			{ 
    				if (lst[1][2] != lst[2][1])cout << "NO" << endl;
    				else
    				{ 
    					cout << "YES" << endl;
    					for (int i = 1;i <= m + 1;i++)
    						if (i % 2 == 0)cout << "1 ";
    						else cout << "2 ";
    					cout << endl;
    				}
    			}
    			else
    			{ 
    				cout<<"YES"<<endl;
    				int a = 0, b, c;
    				if (lst[1][2] == lst[2][1])a = 1, b = 2;
    				else if (lst[2][3] == lst[3][2])a = 2, b = 3;
    				else if (lst[1][3] == lst[3][1])a = 3, b = 1;
    				if (a)
    				{ 
    					for (int i = 1;i <= m + 1;i++)
    						if (i % 2 == 1)cout << a << " ";
    						else cout << b << " ";
    				}
    				else
    				{ 
    					if (lst[1][2] == lst[2][3])a = 1, b = 2, c = 3;
    					else if (lst[2][3] == lst[3][1])a = 2, b = 3, c = 1;
    					else if (lst[3][1] == lst[1][2])a = 3, b = 1, c = 2;
    					if (m / 2 % 2 == 1)
    					{ 
    						for (int i = 1;i <= m + 1;i++)
    							if (i % 4 == 1)cout << a << " ";
    							else if (i % 4 == 2)cout << b << " ";
    							else if (i % 4 == 3)cout << c << " ";
    							else cout << b << " ";
    					}
    					else
    					{ 
    						for (int i = 1;i <= m + 1;i++)
    							if (i % 4 == 1)cout << b << " ";
    							else if (i % 4 == 2)cout << c << " ";
    							else if (i % 4 == 3)cout << b << " ";
    							else cout << a << " ";
    					}
    				}
    				cout << endl;
    			}
    		}
    	}
    }

[Link 1]: https://codeforc.es/contest/1481/problem/D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/1111538de5d7430585b71b7d963c3c39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70 1]: /images/20210716/453ab3964d094b6693138d3bd97e9970.png