D - AB Graph (构造、图)

题目

思路:
分为两种情况:
1.当m为奇数时,直接12121212…构造出的一定是回文。
2.当m为偶数时,可以知道n>=3时一定可以构造出。证明如下:
当1,2,3三个点中出现来回字母一样,只需两个点不断循环即可。

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

当(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;
			}
		}
	}
}

全部评论

相关推荐

缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务