3 条题解

  • 1
    @ 2025-10-10 15:35:28

    LLL

    一道非常优雅的题目，我场上想的东西都不对

    首先考虑第一个数，第一个数肯定是尽可能地选 L ，因为要让字典序最小

    然后我们考虑，找到了 a1a_1 是我们第一个要放出来的，那我们还得找到一个 axa_x 使得 ax=a1a_x=a_1 ，并且可以看出 axa_x 一定是最后一个放出来的

    那我们再想，因为 axa_x 是最后一个放出来的，所以说在 axa_x 前面的数就只能通过 L 的方式放出来，在 axa_x 后面的数就只能通过 R 的方式放出来

    那这像什么，很像一个栈对不对

    然后我们发现就是说，我们接下来再放出来一个数 apa_p 一定是在栈顶放出来，那么我们就发现与 apa_p 对应的那个数 aqa_q 一定是当前还在栈内元素中最后一个放出来的，既然一个是第一个放出来，一个是最后一个放出来，那么那个最后一个放出来的肯定实在栈底，如果找不到，一定没有解

    先放 R 同理，只不过最后一步得让最后一个从 L 出来

    我们只要判断这两个栈中有没有任意一个栈顶与栈底相等，并且优先选左边的栈，因为要字典序最小

    然后这个栈可以使用双端队列来维护

    请欣赏冗长代码，不要用string会超时

    #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=1e6+10;
int _=1,n,posx=0,posy=0,a[N];
char ans[N];
deque<int> q1,q2;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("palin2.in","r",stdin);
	freopen("std.oust","w",stdout);
}
inline void clr(){
//	Don't forget!
	while(!q1.empty()) q1.pop_back();
	while(!q2.empty()) q2.pop_back();
	memset(ans,0,sizeof(ans));
}
bool solve(int L1,int R1,int L2,int R2,bool dududu){
	clr();
	for(int i=L1;i<=R1;i++) q1.push_back(a[i]);
	for(int i=L2;i<=R2;i++) q2.push_front(a[i]);
	for(int i=1;i<n;i++){
		int px1=q1.empty()?0:q1.front(),px2=q1.empty()?0:q1.back();
		int py1=q2.empty()?0:q2.front(),py2=q2.empty()?0:q2.back();
		if(px1==px2&&q1.size()>1){
			q1.pop_front(),q1.pop_back();
//			ans1+='L',ans2='L'+ans2;
			ans[i]='L',ans[2*n-i-1]='L';
		}
		else if(px1==py2){
			q1.pop_front(),q2.pop_back();
//			ans1+='L',ans2='R'+ans2;
			ans[i]='L',ans[2*n-i-1]='R';
		}
		else if(py1==px2){
			q2.pop_front(),q1.pop_back();
//			ans1+='R',ans2='L'+ans2;
			ans[i]='R',ans[2*n-i-1]='L';
		}
		else if(py1==py2&&q2.size()>1){
			q2.pop_front(),q2.pop_back();
//			ans1+='R',ans2='R'+ans2;
			ans[i]='R',ans[2*n-i-1]='R';
		}
		else return 0;
	}
	if(!dududu) printf("L%sL\n",ans+1);
	else printf("R%sL\n",ans+1);
	return 1;
}
bool test_case(){
	for(int i=1;i<=n+n;i++){
		if(a[i]==a[1]&&i!=1) posx=i;
		if(a[i]==a[n+n]&&i!=n+n) posy=i;
	}
	if(solve(2,posx-1,posx+1,n+n,0)) return 1;
	if(solve(1,posy-1,posy+1,n+n-1,1)) return 1;
	return 0;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n+n;i++) a[i]=reads();
		if(!test_case()) puts("-1");
	}
	return 0;
}
    • @ 2025-10-10 15:39:27

      要用STL？

      这里有更优雅的代码

      #include<iostream>
#include<cstdio>
#include<algorithm>

#define N 1000006

using namespace std;

inline int read(){
	int x=0,f=1; char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar(); 
	}
	return x*f; 
}

int T,n,a[N];
char ans[N];

inline bool check(int l1,int r1,int l2,int r2){
	for (int i=1;i<(n>>1);i++){
		if (l1<=r1 && l1<r1 && a[l1]==a[r1]){
			l1++;
			r1--;
			ans[i]='L';
			ans[n-i-1]='L';
		}else if (l1<=r1 && l2<=r2 && a[l1]==a[l2]){
			l1++;
			l2++;
			ans[i]='L';
			ans[n-i-1]='R';
		}else if (l2<=r2 && l2<r2 && a[r2]==a[l2]){
			l2++;
			r2--;
			ans[i]='R';
			ans[n-i-1]='R';
		}else if (l2<=r2 && l1<=r1 && a[r2]==a[r1]){
			r1--;
			r2--;
			ans[i]='R';
			ans[n-i-1]='L';
		}else return 0;
	}
	return 1;
}

int main(){
	T=read();
	while (T--){
		n=read(); n<<=1;
		int posA1=0,posAn=0;
		for (int i=1;i<=n;i++){
			a[i]=read();
			ans[i]=0;
		}ans[n+1]=0;
		for (int i=1;i<=n;i++){
			if (1!=i && a[1]==a[i]) posA1=i;
			if (n!=i && a[n]==a[i]) posAn=i;
		}
		if (check(2,posA1-1, posA1+1,n)) printf("L%sL\n",ans+1);
		else if (check(1,posAn-1, posAn+1,n-1)) printf("R%sL\n",ans+1);
		else printf("-1\n");
	}
	return 0;
}
  • 0
    @ 2025-10-10 15:37:27

    一道非常優雅的題目，我場上想的東西都不對

    首先考慮第一個數，第一個數肯定是盡可能地選L，因為要讓字典序最小

    然後我們考慮，找到了a1a_1是我們第一個要放出來的，那我們還得找到一個axa_x使得ax=a1a_x=a_1，並且可以看出axa_x一定是最後一個放出來的

    那我們再想，因為axa_x是最後一個放出來的，所以說在axa_x前面的數就只能通過L的管道放出來，在axa_x後面的數就只能通過R的管道放出來 那這像什麼，很像一個棧對不對

    然後我們發現就是說，我們接下來再放出來一個數apa_p一定是在棧頂放出來，那麼我們就發現與apa_p對應的那個數aqa_q一定是當前還在棧內元素中最後一個放出來的，既然一個是第一個放出來，一個是最後一個放出來，那麼那個最後一個放出來的肯定實在棧底，如果找不到，一定沒有解

    先放R同理，只不過最後一步得讓最後一個從L出來 我們只要判斷這兩個棧中有沒有任意一個棧頂與棧底相等，並且優先選左邊的棧，因為要字典序最小

    然後這個棧可以使用雙端隊列來維護

    請欣賞冗長程式碼，不要用string會超時

    #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=1e6+10;
int _=1,n,posx=0,posy=0,a[N];
char ans[N];
deque<int> q1,q2;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("palin2.in","r",stdin);
	freopen("std.oust","w",stdout);
}
inline void clr(){
//	Don't forget!
	while(!q1.empty()) q1.pop_back();
	while(!q2.empty()) q2.pop_back();
	memset(ans,0,sizeof(ans));
}
bool solve(int L1,int R1,int L2,int R2,bool dududu){
	clr();
	for(int i=L1;i<=R1;i++) q1.push_back(a[i]);
	for(int i=L2;i<=R2;i++) q2.push_front(a[i]);
	for(int i=1;i<n;i++){
		int px1=q1.empty()?0:q1.front(),px2=q1.empty()?0:q1.back();
		int py1=q2.empty()?0:q2.front(),py2=q2.empty()?0:q2.back();
		if(px1==px2&&q1.size()>1){
			q1.pop_front(),q1.pop_back();
//			ans1+='L',ans2='L'+ans2;
			ans[i]='L',ans[2*n-i-1]='L';
		}
		else if(px1==py2){
			q1.pop_front(),q2.pop_back();
//			ans1+='L',ans2='R'+ans2;
			ans[i]='L',ans[2*n-i-1]='R';
		}
		else if(py1==px2){
			q2.pop_front(),q1.pop_back();
//			ans1+='R',ans2='L'+ans2;
			ans[i]='R',ans[2*n-i-1]='L';
		}
		else if(py1==py2&&q2.size()>1){
			q2.pop_front(),q2.pop_back();
//			ans1+='R',ans2='R'+ans2;
			ans[i]='R',ans[2*n-i-1]='R';
		}
		else return 0;
	}
	if(!dududu) printf("L%sL\n",ans+1);
	else printf("R%sL\n",ans+1);
	return 1;
}
bool test_case(){
	for(int i=1;i<=n+n;i++){
		if(a[i]==a[1]&&i!=1) posx=i;
		if(a[i]==a[n+n]&&i!=n+n) posy=i;
	}
	if(solve(2,posx-1,posx+1,n+n,0)) return 1;
	if(solve(1,posy-1,posy+1,n+n-1,1)) return 1;
	return 0;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n+n;i++) a[i]=reads();
		if(!test_case()) puts("-1");
	}
	return 0;
}
    • -1
      @ 2025-10-10 15:39:15

      A very elegant question, everything I thought on the field was wrong

      Firstly, consider the first number, which should be chosen as L as much as possible to minimize the lexicographic order

      Then we consider that if we find that a1a_1 is the first one we want to release, we also need to find axa_x such that ax=a1a_x=a_1 , and it can be seen that axa_x must be the last one to be released

      Let's think again, because axa_x is the last one to be released, so the numbers before axa_x can only be released through the L method, and the numbers after axa_x can only be released through the R method

      What does this look like? It's quite like a stack, isn't it

      Then we realized that if we put another number apa_p at the top of the stack, then we would find that the number aqa_q corresponding to apa_p must be the last element currently in the stack to be put out. Since one is the first one to be put out and the other is the last one, then the last one must be at the bottom of the stack. If we cannot find it, there must be no solution

      Let's put R first, similarly, but the last step is to let the last one come out of L

      We just need to check if either of these two stacks has the top and bottom of the stack equal, and prioritize the stack on the left because we want to minimize the lexicographic order

      Then this stack can be maintained using a dual ended queue

      Please appreciate the lengthy code.Do not use string as it will time out

      #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
bool Test_MLE_start;
constexpr int N=1e6+10;
int _=1,n,posx=0,posy=0,a[N];
char ans[N];
deque<int> q1,q2;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("palin2.in","r",stdin);
	freopen("std.oust","w",stdout);
}
inline void clr(){
//	Don't forget!
	while(!q1.empty()) q1.pop_back();
	while(!q2.empty()) q2.pop_back();
	memset(ans,0,sizeof(ans));
}
bool solve(int L1,int R1,int L2,int R2,bool dududu){
	clr();
	for(int i=L1;i<=R1;i++) q1.push_back(a[i]);
	for(int i=L2;i<=R2;i++) q2.push_front(a[i]);
	for(int i=1;i<n;i++){
		int px1=q1.empty()?0:q1.front(),px2=q1.empty()?0:q1.back();
		int py1=q2.empty()?0:q2.front(),py2=q2.empty()?0:q2.back();
		if(px1==px2&&q1.size()>1){
			q1.pop_front(),q1.pop_back();
//			ans1+='L',ans2='L'+ans2;
			ans[i]='L',ans[2*n-i-1]='L';
		}
		else if(px1==py2){
			q1.pop_front(),q2.pop_back();
//			ans1+='L',ans2='R'+ans2;
			ans[i]='L',ans[2*n-i-1]='R';
		}
		else if(py1==px2){
			q2.pop_front(),q1.pop_back();
//			ans1+='R',ans2='L'+ans2;
			ans[i]='R',ans[2*n-i-1]='L';
		}
		else if(py1==py2&&q2.size()>1){
			q2.pop_front(),q2.pop_back();
//			ans1+='R',ans2='R'+ans2;
			ans[i]='R',ans[2*n-i-1]='R';
		}
		else return 0;
	}
	if(!dududu) printf("L%sL\n",ans+1);
	else printf("R%sL\n",ans+1);
	return 1;
}
bool test_case(){
	for(int i=1;i<=n+n;i++){
		if(a[i]==a[1]&&i!=1) posx=i;
		if(a[i]==a[n+n]&&i!=n+n) posy=i;
	}
	if(solve(2,posx-1,posx+1,n+n,0)) return 1;
	if(solve(1,posy-1,posy+1,n+n-1,1)) return 1;
	return 0;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n+n;i++) a[i]=reads();
		if(!test_case()) puts("-1");
	}
	return 0;
}
      • 1

      [CSP-S 2021] 回文

      信息

      ID
      472
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      (无)
      递交数
      19
      已通过
      5
      上传者
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      3. Worker 0, 50ms
      4. Powered by Hydro v4.18.3 Community