CodeForces Gym 100989B LCS (B)

最新推荐文章于 2022-09-13 16:29:10 发布

sky-edge

最新推荐文章于 2022-09-13 16:29:10 发布

阅读量620

点赞数

分类专栏：水题 CodeForces

本文链接：https://blog.csdn.net/code12hour/article/details/51911753

版权

CodeForces 同时被 2 个专栏收录

48 篇文章

订阅专栏

水题

46 篇文章

订阅专栏

给一个算LCS时得到的DP矩阵，然后根据这个矩阵让你算出两个符合条件的字符串

因为字符串长度<=25，然后可以先假设A字符串就是abcdef....，然后根据A算B就行，看B中哪个跟A一样，但是A中可能有两个或以上的字符跟B的某个是一样的，然后这时就要把这两个变成同一个，但是这个涉及到很多，因为可能还跟B中别的字符一样，所以就用并查集维护他们，把他们并到一个集合里，最后输出时按集合的根输出就行。

或者不用并查集，每次遇到这个问题时，就把AB字符串都扫一遍，遇到要改的改掉就行，反正长度 25，随便搞

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
int R, C;
char A[30], B[30];
int DP[30][30];
int set[30];
int stk[30];
int findset(int x)
{
	if (x == set[x])
		return x;
	else
		return set[x] = findset(set[x]);
}
void unionset(int x, int y)
{
	int fx = findset(x);
	int fy = findset(y);
	if (fx == fy)
		return;
	else
		set[fy] = fx;
	findset(y);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d%d", &R, &C);
	for (int i = 0; i <= R; ++i)
	{
		for (int j = 0; j <= C; ++j)
		{
			scanf("%d", &DP[i][j]);
		}
	}
	for (int i = 1; i <= R; ++i)
	{
		A[i] = 'a' + i - 1;
		set[i] = i;
	}
	int cnt = 0;
	for (int j = 1; j <= C; ++j)
	{
		cnt = 0;
		for (int i = 1; i <= R; ++i)
		{
			if (DP[i][j] > DP[i - 1][j] && DP[i][j] > DP[i][j - 1])
			{
				stk[cnt++] = i;
			}
		}
		for (int i = 1; i < cnt; ++i)
			unionset(stk[0], stk[i]);
	}
	for (int i = 1; i <= R; ++i)
	{
		findset(i);
	}
	for (int i = 1; i <= R; ++i)
		A[i] = A[findset(i)];
	for (int i = 1; i <= C; ++i)
	{
		if (B[i] == 0)
			B[i] = 'z';
	}
	for (int j = 1; j <= C; ++j)
	{
		cnt = 0;
		for (int i = 1; i <= R; ++i)
		{
			if (DP[i][j] > DP[i - 1][j] && DP[i][j] > DP[i][j - 1])
			{
				B[j] = A[set[i]];
			}
		}
	}
	printf("%s\n", A + 1);
	printf("%s\n", B + 1);
	//system("pause");
	//while (1);
	return 0;
}