1 条题解
-
0
思路
大家貌似都是递归做的?
显然这题还可以用栈搞啊。
从左往右扫两遍,第一遍判可行,第二遍输出方案。
栈中类型设为
bool
,表示处理到了每个pair
的哪一项。简单说,就是每次遇到
pair
就进栈并标记为false
,每次遇到int
就反复出栈直至遇到false
并把其改为true
。这与二叉树的中序遍历类似,
int
即叶结点,pair
即枝结点。注意一些细节特判,如根结点即叶子(测试点
#10
)、多棵二叉树等等。Code
#include <stack> #include <stdio.h> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;} template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;} std::stack<bol>S;chr C[10];bol Ok[300005]; int main() { uint n=0; bol f=false; scanf("%*u"); while(scanf("%s",C)==1)Ok[n++]=C[0]=='i'; if(n==1)return puts(Ok[0]?"int":"Error occurred"),0; for(uint i=0;i<n;i++) { if(Ok[i]) { if(S.empty()){puts("Error occurred");return 0;} while(!S.empty())if(S.top())S.pop();else{S.top()=true;break;} } else { if(S.empty()){if(f){puts("Error occurred");return 0;}else f=true;} S.push(false); } } if(!S.empty()){puts("Error occurred");return 0;} for(uint i=0;i<n;i++) { if(Ok[i]){printf("int");while(!S.empty()){if(S.top())putchar('>'),S.pop();else{putchar(','),S.top()=true;break;}}} else S.push(false),printf("pair<"); } putchar('\n'); return 0; }
- 1
信息
- ID
- 7071
- 时间
- 4000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者