[NOIP2017]时间复杂度

NOIP day2T2 居然才是模拟题?厉害了……

题目(洛谷)

用栈来大模拟……

代码写得比较杂也不一一解释了……

总之注意几种情况:

ERR的情况:1.栈都空了还在E    2.栈中出现相同字母

然后就是合法情况了:

  1. 常数 -> 常数  O(1),并且判断后面那个常数是否大于等于前面那个
  2. 常数 -> n  ++O
  3. n->常数  O(1)且不进入循环
  4. n->n  O(1)且进入循环

完了?

完了。

哦对了,上面这份代码并不是我考试时提交的代码。

考试时94行的代码是这样的:

这句话就是在表明:我完全漏了n->n的情况……

但还是过了,因缺思厅。

后来思考了一下为什么会过,发现主要是ccf的数据很水……

我这么写会错的话就是在ERR上面会判断错误,如果栈中出现了两个相同字母的话。

而数据里面没有n->n还出现相同字母的情况。

于是就过了233

发表评论