问题是:
时限:0.2s
在这些情况下,定义了正确的方括号表达式:
我的主要想法类似于CodeForces上的 380C 问题,http://codeforces.com/blog/entry/10363
然后,我检查给定范围内的最长子序列是否等于范围的长度,因此我将得到答案。但是我遇到时间限制错误。
我整天都在互联网上搜索此内容,但没有得到答案。如果您能帮助我,我将不胜感激。 :)
这是我的代码:https://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp
最佳答案
有效括号序列的条件是:
因此,从原始的左括号和右括号开始,我们可以将其转换为数字序列,每个数字代表从序列开头的右括号和右括号之间的差异。每个方括号中,我们将加一个,而负号则作为关闭。
例如,对于
((()))))
->,我们具有序列{1,2,3,2,1,0,-1,-2}因此,要测试子字符串(例如,子字符串(2,5),即
()))
)是否有效,我们需要查看open和close之间的差异是否为负。从上面的序列中,我们得到{3,2,1,0},我们需要为每个元素减去2,因为我们需要从字符串的开头删除那些不在子字符串中的括号。 ->我们有{1,0,-1,-2}->所以子字符串无效。了解了以上想法后,我们就可以对问题进行解决。
(
更改为)
,那么我们需要将-2
减去从索引3开始的所有元素。 根据所有这些要求,我们可以使用Segment tree,它为您提供O(log n)更新和O(log n)检索。
伪代码
SegmentTree tree;
Initialize the tree with original sequence
for each query in the tree
if( query type is update)
if(change from ) to ()
increase all value by 2 from range index to n
else if(change from ( to ) )
decrease all value by 2 from range index to n
else
int min = tree.getMinimumValueInRange(u, v)
int notInSubstring = tree.getMinimumValueInRange(u - 1, u - 1)
if(min - notInSubstring < 0)
print Invalid
else if( length of substring is not even)
print Invalid
else if( tree.getMinimumValueInRange(v, v) != notInSubstring)//Number of open and close brackets are not equaled.
print Invalid
关于c++ - 更新并检查包含方括号的子字符串是否正确,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/34303769/