指针做法求调
查看原帖
指针做法求调
573963
wbh20090611楼主2024/10/22 20:11

rt

#include <bits/stdc++.h>
#define L 1
#define R 2
using namespace std;
int n, T, a[1000010], k, l1, l2, r1, r2, b[1000010];
char s[4] = " LR";
int main()
{
	cin >> T;
	while (T--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n * 2; i++)
			scanf("%d", a + i);
		if (n == 1)
		{
			printf("LL\n");
			continue;
		}
		k = a[1];
		for (int i = 2; i <= n * 2; i++)
			if (a[i] == k)
			{
				k = i;
				break;
			}
		l1 = 2;
		l2 = k + 1;
		r1 = k - 1;
		r2 = n * 2;
		if (l1 > r1)
			l1 = r1 = 0;
		if (l2 > r2)
			l2 = r2 = 0;
		b[0] = 0;
  //头为第一个
		for (int i = 1; i < n; i++)
		{
			if (a[l1] == a[r1] && l1 != r1)
			{
				b[n * 2 - i + 1] = b[i] = L;
				l1++;
				r1--;
			}
			else if (a[l1] == a[l2])
			{
				b[n * 2 - i + 1] = R;
				b[i] = L;
				l1++;
				l2++;
			}
			else if (a[r2] == a[r1])
			{
				b[n * 2 - i + 1] = L;
				b[i] = R;
				r2--;
				r1--;
			}
			else if (a[r2] == a[l2] && l2 != r2)
			{
				b[n * 2 - i + 1] = b[i] = R;
				l2++;
				r2--;
			}
			else
			{
				b[0] = -1;
				break;
			}
		}
		if (b[0] == -1)
		{
 //否则尾为第一个
			b[0] = 0;
			k = a[n * 2];
			for (int i = 1; i < n * 2; i++)
				if (a[i] == k)
				{
					k = i;
					break;
				}
			l1 = 1;
			l2 = k + 1;
			r1 = k - 1;
			r2 = n * 2 - 1;
			if (l1 > r1)
				l1 = r1 = 0;
			if (l2 > r2)
				l2 = r2 = 0;
			for (int i = 1; i < n; i++)
			{
				if (a[l1] == a[r1])
				{
					b[n * 2 - i + 1] = b[i] = L;
					l1++;
					r1--;
				}
				else if (a[l1] == a[l2])
				{
					b[n * 2 - i + 1] = R;
					b[i] = L;
					l1++;
					l2++;
				}
				else if (a[r2] == a[r1])
				{
					b[n * 2 - i + 1] = L;
					b[i] = R;
					r2--;
					r1--;
				}
				else if (a[r2] == a[l2])
				{
					b[n * 2 - i + 1] = b[i] = R;
					l2++;
					r2--;
				}
				else
				{
					b[0] = -1;
					break;
				}
			}
			if (b[0] == -1)
				printf("-1\n");
			else
			{
				printf("R");
				for (int i = 1; i <= n * 2; i++)
				{
					if (i == n || i == n + 1)
						continue;
					printf("%c", s[b[i]]);
				}
				printf("L\n");
			}
		}
		else
		{
			printf("L");
			for (int i = 1; i <= n * 2; i++)
			{
				if (i == n || i == n + 1)
					continue;
				printf("%c", s[b[i]]);
			}
			printf("L\n");
		}
	}
}
2024/10/22 20:11
加载中...