专栏文章

题解：P11530 [THUPC2025 初赛] 峰回路转

JJHPOTATO
P11530题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miqjziec
此快照首次捕获于
2025/12/04 06:03
3 个月前
此快照最后确认于
2025/12/04 06:03
3 个月前
查看原文

一些废话

开赛半个小时后分配到这题，然后被硬控至结束，还没调出来，团队直接蒸发一人。(这下不得不膜拜另一位狂切七题的巨佬了)
这题也是本人写的第一道紫模拟，第二道蓝及以上的模拟。
这也是本人第一篇题解，写得不好还请见谅。

题解

感觉和前几年的大模拟不同，这题的种种要求是在叙述中把限制零散地给出来的，并没有系统性，乍看上去很难入手，所以我们首先需要对题面做阅读理解，并简化题意。
仔细阅读后可以总结出这两条基本性质：
  1. 近邻逆接记号和近邻顺接记号都只用于连接一段连续的数
  2. 遥远跳转记号用于连接不同的段
那么我们可以将原序列按照阅读顺序分成若干连续段，比如可以把 3 4 1 2 8 9 5 6 7 划分为 (3 4) (1 2) (8 9) (5 6 7) 四段，并给每个段标上输出顺序，即 2 1 4 3，接下来的处理就可以以段为单位进行。
首先进行无解判断，因为单个段一定存在合法输出，所以只需判断能不能通过遥远跳转记号把这些段调整至正确的输出顺序。可以发现只有在遥远跳转记号之间存在交叉时不存在合法方案，这也是无法用栈对一个序列进行排序的充要条件，所以可以通过模拟用栈排序进行判定。也就是说当且仅当不能用一个栈对我们划分出的序列进行排序时，不存在合法方案，反之存在。
判断完是否合法后，我们就要确定遥远跳转标记 p-q 中 p 与 q 的值，也就是嵌套层数和该层的跳转顺序，我们发现这两个值都可以在栈排序的过程中求出，具体地说，我们可以给每次连续出栈的一段的 q 赋值，而这一段的 p 值可以通过统计栈中历史存储的最大深度求解，当然，如果一次只弹出了一个元素就不需要跳转标记了，具体细节可以看代码。
这样我们似乎就能输出一组解了，但是发现还有一些题目限制没有满足，所以针对这些细节继续处理。
再次阅读题面后，发现还有如下两条限制没满足：
  1. 由于近邻顺接记号只是用来把一串数连成一段，阅读顺序与自然阅读顺序完全相同，所以如果遥远跳转记号 q 值为 1 且这段需要顺序输出，我们可以按照 ....p-1 的格式输出，而不是用 .p-1#.#.#. 的格式输出。
  2. 题目说明了形如 *.p-q（q 不为 1）的输出会引起阅读歧义，但题目中也给出了解决方案，只需将 .*.*.*.p-q（q 不为 1）改为 p2-q2.*.*.*.p-1 即可。
对于第一点，我们只需要进行特判并打标记即可；对于第二点，我们只需在处理到逆序输出的段时重开一层就可以解决。
处理完这些后就可以输出答案，以段为单位输出，具体实现可以看代码。
回过头再看看，会发现虽然题目给的条件零散且杂乱，但整合起来后限制并没有想象的那么多，而且代码的细节似乎也很少。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
template <typename T>
void in(T &x){
	char c=getchar(), f=1;
	while ((c<'0' || c>'9') && c!='-') c=getchar();
	if (c=='-') f=-1, c=getchar();
	for (x=0; c>='0' && c<='9'; c=getchar())
		x=x*10+c-'0';
	x*=f;
}
//先"合并"连续段
//然后作插入
//栈发生冲突则无解
const int N=1e6+5;
int n,cnt,tmp[N],b[N];//b->映射数组
struct Node{
	bool flag;//1->顺接 0->逆接
	int st,ed;//起始点,终点
	int id;//新标号(按输出顺序标号)
	int p,q,f3;//嵌套的p,q值(首),是否有特殊输出.p-q#.#.#.---->....p-q q==1
	int p2,q2;//嵌套的p,q值(尾)
}s[N];//"缩点"后的数组
int c[N];//c->id与排序后位置的映射
bool cmp(Node e,Node f){
	return e.st<f.st;
}
int stk[N],top,ned;
int d[N];//统计嵌套层数
int stk2[N],top2;//处理连续段的嵌套的p,q值
void out(int num){//输出一段
	if(s[num].f3==1){/*
    判断是否为特殊输出
    即相邻却不需要顺邻标记的段,可能是q为1的顺序段,也可能是不需要跳转标记的顺序段
    两种情况可以放在一起考虑
    */
		for(int i=s[num].st;i<=s[num].ed;i++)printf(".");
		if(s[num].p2&&s[num].q2)printf("%d-%d",s[num].p2,s[num].q2);
		return ;
	}
	//否则一定是.*.*.或.#.#.的格式
	//首部和尾部的跳转标记直接插入即可
	printf(".");
	if(s[num].p&&s[num].q)printf("%d-%d",s[num].p,s[num].q);
	for(int i=s[num].st+1;i<=s[num].ed;i++){
		if(s[num].flag==1)printf("#.");
		else printf("*.");
	}
	if(s[num].p2&&s[num].q2)printf("%d-%d",s[num].p2,s[num].q2);
}
int main(){
	in(n);
	for(int i=1;i<=n;i++){
		in(tmp[i]);
		b[tmp[i]]=i;
	}
	int fir=1;
	while(fir<=n){
		if(fir==n){
			cnt++;
			s[cnt]={1,b[fir],b[fir],cnt};
		}
		else{
			bool flag;
			if(abs(b[fir]-b[fir+1])!=1){
				cnt++;
				s[cnt]={1,b[fir],b[fir],cnt};
			}
			else{
				flag=b[fir]<b[fir+1];
				int last=fir+1;
				while(abs(b[last]-b[last+1])==1&&last<n){
					last++;
				}
				cnt++;
				s[cnt]={flag,min(b[fir],b[last]),max(b[fir],b[last]),cnt};
				fir=last;
			}
		}
		fir++;
		//按时间段先后赋id
	}
	sort(s+1,s+cnt+1,cmp);//按原序列位置先后排序
	ned=1;stk[0]=1e9;
	for(int i=1;i<=cnt;i++){
		c[s[i].id]=i;
		if(s[i].id==ned){
			ned++;
			while(stk[top]==ned){
				ned++,top--;
			}
		}
		else{
			if(stk[top]<s[i].id){
				printf("-1\n");
				return 0;
			}
			stk[++top]=s[i].id;
		}
	}
	//能跑完(能用单栈完成排序)说明有解,然后重做一遍,进行答案更新
	top=0,ned=1;
	for(int i=1;i<=cnt;i++){
		if(s[i].id==ned){
			ned++;
			int ct=1,mxx=0;
			while(stk[top]==ned){
				mxx=max(mxx,d[top]);//记录这一段中的历史最大深度
				ned++,top--;
				ct++;
			}
			d[top]=max(d[top],mxx+1);//更新历史最大深度
			if(ct==1){//不需要嵌套
				if(s[i].flag==1)s[i].f3=1;
			}
			else{
				mxx=1,stk2[++top2]=s[i].id;
				if(s[i].flag==1)s[i].f3=1;
				for(int j=ct-1;j>=1;j--){
					mxx=max(mxx,d[top+j]);
					if(s[c[stk[top+j]]].flag==0){//重开一层,避免*.p-q q!=1的理解歧义
						int x2=top2+1;
						s[c[stk[top+j]]].p2=mxx,s[c[stk[top+j]]].q2=x2;
						x2--;
						while(top2){
							if(s[c[stk2[top2]]].f3==1){//特殊输出判断(....#)
								s[c[stk2[top2]]].p2=mxx;
								s[c[stk2[top2]]].q2=x2;
							}
							else{
								s[c[stk2[top2]]].p=mxx;
								s[c[stk2[top2]]].q=x2;
							}
							x2--;top2--;
						}
						if(j>1){//如果是首,显然不用再跳转
							stk2[++top2]=stk[top+j];
						}
						mxx=0;
					}
					else{
						stk2[++top2]=stk[top+j];
					}
				}
				if(top2){//处理未弹出部分 显然第一个是顺接 因为逆接会重开一层
					int x2=top2;
					s[c[stk2[top2]]].p=mxx,s[c[stk2[top2]]].q=x2;
					top2--,x2--;
					while(top2){
						if(s[c[stk2[top2]]].f3==1){//特殊输出判断(....#)
							s[c[stk2[top2]]].p2=mxx;
							s[c[stk2[top2]]].q2=x2;
						}
						else{
							s[c[stk2[top2]]].p=mxx;
							s[c[stk2[top2]]].q=x2;
						}
						x2--;top2--;
					}
				}
			}
		}
		else{stk[++top]=s[i].id;d[top]=1;}
	}
	for(int i=1;i<=cnt;i++)out(i);//由于已经按原序列位置先后排序,直接顺次输出
	return 0;
}

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...