博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 4915 Parenthese sequence
阅读量:5173 次
发布时间:2019-06-13

本文共 2369 字,大约阅读时间需要 7 分钟。

扫过去。记录最大和最小可能开括号值

假设该尺寸比左小圆括号右括号尺寸。它不是不可避免

从扫再次。相同的记录最大和最小可能的左括号值

假定右括号尺寸小于开口括号的大小,它不是不可避免

最小值中的最大值,和最大值中的最小值

假设前者大于后者,则不行,假设后者大于前者则有多重解。假设相等则为唯一解(感谢LUKE队长提供的思路)

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;typedef long double ld;typedef pair
pll;typedef complex
point;typedef pair
pii;typedef pair
piii;template
inline bool read(T &n){ T x = 0, tmp = 1; char c = getchar(); while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar(); if(c == EOF) return false; if(c == '-') c = getchar(), tmp = -1; while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar(); n = x*tmp; return true;}template
inline void write(T n){ if(n < 0) { putchar('-'); n = -n; } int len = 0,data[20]; while(n) { data[len++] = n%10; n /= 10; } if(!len) data[len++] = 0; while(len--) putchar(data[len]+48);}//-----------------------------------const int L=1000050;int a[L][2],b[L][2];int main(){ int i,j,l,sig,ta,tb; char s[L]; while(scanf("%s",s+1)!=EOF) { l=strlen(s+1); sig=0; if(l%2==1) { printf("None\n"); continue; } a[0][0]=a[0][1]=b[l][0]=b[l][1]=0; for(i=1; i<=l; i++) { if(s[i]=='(')a[i][0]=a[i-1][0]+1,a[i][1]=a[i-1][1]+1; else if(s[i]==')') { if(a[i-1][0]==0)a[i][0]=1; else a[i][0]=a[i-1][0]-1; a[i][1]=a[i-1][1]-1; } else if(s[i]=='?

') { if(a[i-1][0]==0)a[i][0]=1; else a[i][0]=a[i-1][0]-1; a[i][1]=a[i-1][1]+1; } if(a[i][0]>a[i][1])sig=1; } if(sig) { printf("None\n"); continue; } for(i=l; i>=1; i--) { if(s[i]==')')b[i-1][0]=b[i][0]+1,b[i-1][1]=b[i][1]+1; else if(s[i]=='(') { if(b[i][0]==0)b[i-1][0]=1; else b[i-1][0]=b[i][0]-1; b[i-1][1]=b[i][1]-1; } else if(s[i]=='?') { if(b[i][0]==0)b[i-1][0]=1; else b[i-1][0]=b[i][0]-1; b[i-1][1]=b[i][1]+1; } if(b[i][0]>b[i][1])sig=1; } if(sig) { printf("None\n"); continue; } for(i=1; i<=l; i++) { ta=max(a[i][0],b[i][0]); tb=min(a[i][1],b[i][1]); if(ta>tb) { sig|=1; break; } if(ta<tb) { sig|=2; } } if(sig&1) { printf("None\n"); continue; } else if(sig&2) { printf("Many\n"); continue; } else printf("Unique\n"); } return 0; }

版权声明:本文博客原创文章。博客,未经同意,不得转载。

转载于:https://www.cnblogs.com/bhlsheji/p/4684953.html

你可能感兴趣的文章
初识数据库
查看>>
宏定义的使用
查看>>
认识对于java生活和工作的应该是怎么样的
查看>>
Codeforces 781C Underground Lab
查看>>
【BZOJ】 4813: [Cqoi2017]小Q的棋盘
查看>>
Backbone Collection 学习笔记
查看>>
回话处理程序(17)
查看>>
【poj2947】高斯消元求解同模方程组【没有AC,存代码】
查看>>
ANDROID笔记:滑动关闭Fragment的简单实现
查看>>
职业发展-外包公司考虑项
查看>>
java学习笔记(菜鸟原创)
查看>>
[Done]FindBugs: boxing/unboxing to parse a primitive
查看>>
数据库表中字段的字符串替换
查看>>
把二元查找树转变成排序的双向链表
查看>>
input与select 设置相同宽高,在浏览器上却显示不一致,不整齐
查看>>
NUGET常用命令
查看>>
CentOs下Apache+Python+Django+mod_wsgi环境搭建
查看>>
java基础知识总结(3)
查看>>
spark配置
查看>>
数据仓库 - 3.数据仓库基本概念
查看>>