企业官网建设流程全解析

P9446 [ICPC 2021 WF] Prehistoric Programs

题目描述

考古学家在 Alutila 洞穴的深层发现了令人兴奋的粘土板。除了两个似乎描述嵌套结构的符号（类似于 LISP 中的开括号和闭括号）外，没有人能够破译粘土板上的文字。难道几千年前人类就已经在编写程序了吗？

综合来看，这些粘土板似乎描述了一项伟大的作品——可能是一个程序，或者是一部史诗，甚至是税务记录！不出所料，经过这么长时间，粘土板已经处于无序状态。你的任务是将它们排列成一个序列，使得结果作品具有正确嵌套的括号结构。仅考虑开括号和闭括号，一个正确嵌套的结构要么是

• ()()()，或者
• (A)(A)(A)，其中AAA是一个正确嵌套的结构，或者
• ABABAB，其中AAA和BBB是正确嵌套的结构。

输入格式

输入的第一行包含一个整数nnn(1≤n≤1061 \leq n \leq 10^61≤n≤106)，表示粘土板的数量。接下来的nnn行中的每一行描述一个粘土板，并包含一个非空的开括号和闭括号字符串；与嵌套结构无关的符号被省略。字符串按照它们在输入中出现的顺序从111到nnn编号。输入中最多包含10710^7107个括号。

输出格式

输出一个从111到nnn的数字排列，使得按此顺序连接字符串后形成一个正确嵌套的结构。如果存在多个排列满足条件，任何一个都可以接受。如果没有这样的排列，输出impossible\texttt{impossible}impossible。

输入输出样例 #1

输入 #1

2 ())())() ((()

输出 #1

2 1

输入输出样例 #2

输入 #2

5 ( )) (( )) (

输出 #2

1 5 3 4 2

输入输出样例 #3

输入 #3

2 (( )

输出 #3

impossible

说明/提示

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#definedebug(i)cout<<"Cute_MKS "<<i<<' '#definepiipair<int,int>#definemkp(a,b)make_pair(a,b)constintN=1e6+10;structnode{intx,y,mn,p;booloperator<(constnode&x)const{returnmn<x.mn;}}a[N];intans[N],n;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){string s;inttop=0;a[i].x=a[i].y=0;a[i].p=i;cin>>s;for(intj=0;j<s.length();j++){if(s[j]==')'){if(!top)a[i].x++;elsetop--;}elsetop++;}a[i].y=top;a[i].mn=min(a[i].x,a[i].y);}intl=1,r=n;sort(a+1,a+n+1);for(inti=1;i<=n;i++){if(a[i].mn==a[i].x)ans[l++]=a[i].p;elseans[r--]=a[i].p;}sort(a+1,a+n+1,[](node x,node y)->bool{returnx.p<y.p;});intsum=0;for(inti=1;i<=n;i++){if(a[ans[i]].x+sum>0){cout<<"impossible";return0;}sum+=a[ans[i]].x-a[ans[i]].y;}if(a[ans[n]].y>0||sum!=0){cout<<"impossible";return0;}for(inti=1;i<=n;i++)cout<<ans[i]<<'\n';}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容