题解

给一个

\tt n

n 个点的完全有向图，

(

)

\tt(u,v)

(u,v) 或者

(

)

\tt(v,u)

(v,u) 都有一条边，前提是

≠

\tt u\not=v

u=v 。

每条边的边权是字符 a 或字符 b ，会给你一个

\tt n\times n

n×n 的二维字符表

\tt G

G 来表示它们，若

≠

\tt i\not=j

i=j ，则

\tt G_{i,j}=a

Gi,j=a 或

\tt G_{i,j}=b

Gi,j=b ，否则

∗

\tt G_{i,j}=*

Gi,j=∗ ，表示该边不存在。

现在问你，从任意一个起点开始，走

\tt m

m 步(可以经过重复的点或边)形成的字符串，是否可以为回文串？如果有，输出行走方案。

≤

500

\tt T\leq 500

T≤500 组数据，

∑

≤

1000

∑

≤

\tt \sum n\leq1000,\sum m\leq10^5

∑n≤1000,∑m≤105 。

题解

一眼看过去，貌似是道

\tt DP

DP ？以前做过路径为回文串的题。

但是这题没必要，因为评分只有2000，明显可以直接分类讨论。

对于

\tt m

m 是奇数的情况，我们可以任意找两个点，反复跳，容易发现结果定是回文串。也就是说，这种情况下一定有解。

如果

\tt m

m 是偶数，这样讨论：

若存在一对点

u

,

v

\tt u,v

u,v ，满足

G

u

,

v

=

G

v

,

u

\tt G_{u,v}=G_{v,u}

Gu,v=Gv,u ，那么直接在这两个点之间跳。这明显是无懈可击的方案。
否则，整个图满足对于任意两个不相等的点
u

,

v

\tt u,v

u,v ，

G

u

,

v

,

G

v

,

u

\tt G_{u,v},G_{v,u}

Gu,v,Gv,u 其中一个是 a ，另一个是 b 。然后，我们找这么三个点

x

,

y

,

z

\tt x,y,z

x,y,z （

x

≠

y

,

y

≠

z

\tt x\not=y,y\not=z

x=y,y=z），满足

G

x

,

y

=

G

y

,

z

\tt G_{x,y}=G_{y,z}

Gx,y=Gy,z，令这两条边为最中心的两条边，那么整个回文串为

.

.

.

G

x

,

y

G

y

,

x

G

x

,

y

(

m

i

d

d

l

e

)

G

y

,

z

G

z

,

y

G

y

,

z

.

.

.

\tt ...G_{x,y}G_{y,x}~G_{x,y}(middle)G_{y,z}~G_{z,y}G_{y,z}...

...Gx,yGy,x Gx,y(middle)Gy,z Gz,yGy,z... ，左右两边都是交替出现的 ab ，且保证回文。
如果这三个点也找不到，那么说明不论这一步是什么字符，下一步一定是不一样的字符。这样是形不成偶数长度的回文串的，此时无解。

复杂度

(

)

\tt\Theta(m)

Θ(m) 。

CODE

#include<set>

#include<queue>

#include<bitset>

#include<cmath>

#include<ctime>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 1005

#define ENDL putchar('\n')

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

#define INF 0x3f3f3f3f

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int n,m,i,j,s,o,k;

char g[MAXN][MAXN];

int as[MAXN];

int main() {

	int T = read();

	while(T --) {

		n = read();m = read();

		for(int i = 1;i <= n;i ++) {

			scanf("%s",g[i] + 1);

		}

		if(m & 1) {

			printf("YES\n");

			for(int i = 1;i <= m+1;i ++) printf("%d ",2-(i&1));ENDL;

		}

		else {

			s = o = 0;

			for(int i = 1;i <= n;i ++) {

				for(int j = 1;j <= n;j ++) {

					if(g[i][j] == g[j][i] && i != j) {s = i;o = j;break;}

				}

			}

			if(s && o) {

				printf("YES\n");

				for(int i = 1;i <= m+1;i ++) printf("%d ",(i&1) ? s:o);ENDL;

			}

			else {

				int cen = 0;

				s = o = 0;

				for(int i = 1;i <= n;i ++) {

					int pa = 0,pb = 0;

					for(int j = 1;j <= n;j ++) {

						if(g[j][i] == 'a') pa = j;

						if(g[j][i] == 'b') pb = j;

					}

					for(int j = 1;j <= n;j ++) {

						if(g[i][j] == 'a' && pa) {s = pa;o = j;}

						if(g[i][j] == 'b' && pb) {s = pb;o = j;}

					}

					if(s && o) {cen = i;break;}

				}

				if(cen) {

					printf("YES\n");

					m ++;

					int md = (m+1)/2;

					as[md] = cen;

					as[md-1] = s;

					as[md+1] = o;

					for(int i = md-2;i > 0;i --) {

						if(as[i+1] == s) as[i] = cen;

						else as[i] = s;

					}

					for(int i = md+2;i <= m;i ++) {

						if(as[i-1] == o) as[i] = cen;

						else as[i] = o;

					}

					for(int i = 1;i <= m;i ++) printf("%d ",as[i]);ENDL;

				}

				else printf("NO\n");

			}

		}

	}

	return 0;

}

巴特西

[CF1481D] AB Graph（构造）

题解

题解

CODE

最新文章

热门文章