NoipDay1T2时间复杂度

题目链接

NoipDay1T2时间复杂度

题解

考完改题感觉跟吃翔一样

我\(NOIp\)成也这道题,败也这道题…

我是奔着场切这道题去的.

然而并不存在….

具体思路就是模拟一个栈.该加的加,该减的减,数据给个很弱.很好拿分.

我的程序思路正确小细节可以把我卡成0分,最后拿了70,

感谢\(CCF\)…

不存在的


实现略有复杂.但是思路很清晰的..

大概讲一下.

\(lenew\)表示这个需要计算时间复杂度的程序有多长

\(tott\)表示给定的时间复杂度.

\(ttot\)是实际算出的时间复杂度.

\(cnt\)表示当前栈中有的循环结构.

其实就是还有多少循环结构没有判断过.

如果cnt为0说明嵌套的循环已经全部解决了我的程序加上这句特判就能A啊.难受嘤嘤嘤.白丢30分

\(trr\)表示循环中定义的字母.其实就是一个桶的思想.

\(woc\)是我\(WA\)的核心,\(woc\)为-1的时候表示计算过程正常,为0表示不合法的情况出现了,为1表示循环结构是数字到数字,即复杂度应该计算为常数,而并非一个\(n\)

\(maxx\)表示当前程序计算出的最大的时间复杂度.

\(ti\)表示读入的时间复杂度.需要\(workt\)函数计算出对应的时间(即\(tott\))

\(s\)表示按要求读入程序.模拟解决即可.

\(ff,spj\)这两个都是用来特判的.


\(workt\)函数是模拟把它给定的字符串转换成对应的数字的.

\(init\)就是预处理

\(rread\)是用来读入给定的程序内容的

\(solc\)和\(myx\)函数使用来处理程序的内容

\(iinit\)是预处理


\[workt\]

处理好给定的程序复杂度,以及是否存在给定的程序是\(O(1)\)的特殊情况.


\[solc\]

对于\(F\ x\ a\ b\)的形式判断

  • \(a<b\),\(a,b\)均为数字,即该行复杂度应该被判断为\(O(1)\)的情况
  • \(a\)是字母.因为题目要求循环不为逆序.所以\(a\)一旦是\(n\),直接忽略后面的程序.不进入后面的循环.额外处理.
  • \(b\)是字母,\(a>0\)正常循环.
  • \(a>b\)一样循环不为逆序,不进入后面的程序.用\(spj\)特判

\[myx\]

一次处理程序的每一行.

有\(F\)的操作就加到栈中.同时用桶记录一下字母的使用情况.

额外需要注意字符串中的空格的处理.

有\(E\)的操作就从栈中弹出一个.统计一个最大的时间复杂度.

以及从栈中弹出的时候还需要将之前桶中记录的字母使用情况和这一段程序算出的时间复杂度清空.

如果栈中为空.就重新处理\(woc\)数组.

因为会有循环并列的情况…我30分就丢在这里了….

难受


\[main\]

多组数据.对字符串的处理.

判断时候,如果有程序仅一行的直接不用管这个程序,程序仅一行只能为\(F\)或是\(E\)都是不合题意的.直接\(ERR\)

结束过多.栈中元素可能为负的时候.或者是元素重复定义的时候.都是\(ERR\)

所有行都处理完了.但是栈中还有元素的时候.一样是\(ERR\)

算出的时间复杂度和给定的时间复杂度不同.\(No\)

剩下的就是\(Yes\)了…


By:Wahacer

2017.12.22

11:03

发表评论

电子邮件地址不会被公开。 必填项已用*标注