[题解]洛谷P3952：时间复杂度

  1.  首页
  2. 正文  
    3. 分享到：

因为是时间复杂度所以配图当然要给狂三啦~❤

原题链接：P3952 时间复杂度

这是我做过的最简单的蓝题！（虽然我就没做过几道
也是码风清奇还能AC的迄今为止唯一一道Orz……

题目很直白，就是一个算复杂度的，需要注意的是语法正确与否的判断以及变量的生命周期（请认真看题！！！我还是没明白我为什么幻视成了变量不销毁……）。

题目给人一种不好上手的感觉，主要是因为读入内容混乱（真），这时候确定一个方便的读入和储存方式就很重要。在输入中其实还是有很大一部分是无关数据，例如大O记号、括号、你亲爱的小写n等等。

于是采用getchar()，根本不虚上手就是大模拟（这方面还是猪国杀比较强，不过我也不会就是了）。用getchar()基本就可以为所欲为了，本来还想怠惰一下用scanf()水一水整数读入，后来看来也不是很舒服，就手写了快读。
但是快写是不必要 (可能) 写的，这题输出根本就是puts()啊……

炮姐是你们所有节点的祖宗，所以我们定义一个总的变量misaka，作为一个虚节点，保存整个循环结构。

碎碎念：这种水题肯定是得在线做的，洛谷题解里面那种读入一行的简直too simple……

本题有两种思路，第一种是比较常规的在栈里线性操作，对每一层的同级循环取复杂度max，按照嵌套入栈；另一种就是我这次的搞法，维护树形结构。

为什么说是树形结构呢？我们可以把循环结构看作节点。很显然，每一个循环结构下可能嵌套多个平级的循环结构，就相当于这个节点的所有子节点；而这些嵌套的循环结构下又可能类似地嵌套更多层……明显的树形结构！

画图辅助理解：

维护的数据结构

（御坂美琴一词来自我一时兴起敲的虚节点名misaka）

设计这个结构体！

struct stmt{
    int o;//本节点的时间复杂度
    char var_name;//本节点声明的变量名
    int subc;//子节点的个数
    stmt* subv[107];//子节点表
    stmt* parent;//父节点
    void reset(){//重置
        for(int i=0;i<subc;i++){//调用各个子节点的重置方法并delete掉子节点
            subv[i]->reset();
            delete subv[i];
        }
        o=0;//变量全部初始化
        subc=0;
        parent=0;
        var_name=0;
    }
    stmt* O(int x){//设置节点复杂度
        o=x;
        return this;//只是一时兴起
    }
    stmt* append(char vn){//增加子节点
        subv[subc]=new stmt();
        subv[subc]->reset();
        subv[subc]->parent=this;
        subv[subc]->var_name=vn;
        return subv[subc++];//返回子节点指针
    }
    int O(){//计算总时间复杂度
        if(o==-1)return 0;//本层不算，无视下层按照常数复杂度返回
        int rs=0;
        for(int i=0;i<subc;i++){//计算下层的复杂度，按照平级循环中最复杂的
            rs=max(rs,subv[i]->O());
        }
        if(o){//怎么废话这么多，可以压成一行写的……
            return rs+o;
        }else{
            return rs;
        }
    }
}misaka;

架构上应该还是有可以优化之处，只是懒~就这样了。
成员变量o一共有三种取值，即-1 0 1，分别表示“根本不执行的结构”、“这一层O(1)的结构”和“这一层O(n)的结构”。

明确一点：我们维护的是大O记号中n的系数！这样时间复杂度的相乘关系才能通过幂运算法则直接转化为加法维护。

这里有两个坑：第一，对stmt*类型的初始化是坑，必须new出来，否则就是非法地址访问；第二，以后敲代码我保证不写o这样的变量名，尤其是还有一（两）个O()方法的情况下……

关于语法解析……
这长题解敲得心累……估计看着更累……

简单谈好了……读到F标记++，读到E标记--。
不过注意标记--后要立刻确认正负，否则碰到这样的结构你就玩完：

E
F j 1 n
E
F i 1 n

这个显然是ERR，但是标记不判我就不知道会怎么样了。

注意！复杂度可能有三种而不是两种，因为输入数据不排除根本就一次不会执行的情况，这时需要整体ignore全部看做常数！
仍然是Example：

F i 1 n
F j 1 n
E
F k 5 1
F l 1 n
F m 1 n
E
E
E
E

答案是O(n^2)而不是O(n^4)哦~

那么分析就到此为止，大模拟就靠造化了。[heimu]A了猪国杀，走遍天下都不怕（我没有A[/heimu]

附AC代码（由于Dev-C++的垃圾特性我全写的英文注释，一堆病句不好看，甚至还有正则表达式）：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
bool __flag[26];
inline bool search(char c){
    if(!__flag[c-'a'])return __flag[c-'a']=true,false;
    else return true;
}
inline void del(char c){
    __flag[c-'a']=false;
}
inline void reset(){
    memset(__flag,0,sizeof(__flag));
}
inline int read(){//return INF as 'n'
    char ch;
    bool flag=false;
    while(!isdigit(ch=getchar()))
        if(ch=='n')return INF;
    int rs=0;
    for(rs=ch-'0';isdigit(ch=getchar());rs=rs*10+(ch-'0'));
    flag&&(rs=-rs);
    return rs;
}
struct stmt{
    int o;
    char var_name;
    int subc;
    stmt* subv[107];
    stmt* parent;
    void reset(){
        for(int i=0;i<subc;i++){
            subv[i]->reset();
            delete subv[i];
        }
        o=0;
        subc=0;
        parent=0;
        var_name=0;
    }
    stmt* O(int x){
        o=x;
        return this;
    }
    stmt* append(char vn){
        subv[subc]=new stmt();
        subv[subc]->reset();
        subv[subc]->parent=this;
        subv[subc]->var_name=vn;
        return subv[subc++];
    }
    int O(){
        if(o==-1)return 0;
        int rs=0;
        for(int i=0;i<subc;i++){
            rs=max(rs,subv[i]->O());
        }
        if(o){
            return rs+o;
        }else{
            return rs;
        }
    }
}misaka;
int main(){
    //freopen("test.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        misaka.reset();
        reset();
        int L;
        scanf("%d",&L);
        getchar();//' '
        getchar();//'O'
        getchar();//'('
        int ch=getchar();//'1' or 'n'
        getchar();//')' or '^'
        int block=0;
        if(ch=='n'){//O(n^w) 'n'
            block=read();//block=w and ignore ')'
        }
        ch=getchar();
        while(ch=='\r'||ch=='\n')ch=getchar();//ignore /\r?\n/
        int begin=0;
        bool CE=false;
        stmt* now=&misaka;
        while(L--){
            if(ch=='E'){//'E'
                begin--;
                if(begin<0)CE=true;
                else{
                    del(now->var_name);
                    now=now->parent;
                }
            }else{//'F'
                getchar();//' '
                char var=getchar();
                if(search(var))CE=true;
                now=now->append(var);
                int x,y;
                x=read();
                y=read();
                if(x!=INF&&y==INF){
                    now->O(1);//O(n)
                }else if(x>y){//not at all
                    now->O(-1);//O(0)
                }else{
                    now->O(0);//O(1)
                }
                begin++;
            }
            if(L){
                ch=getchar();
                while(ch=='\r'||ch=='\n')ch=getchar();//ignore /\r?\n/
            }
        }
        if(CE||begin)puts("ERR");
        else{
            int result=misaka.O();
            puts(result==block?"Yes":"No");
        }
    }
    return 0;
}

评级过高了，本题最多也只能算绿题水平 -> R17380139

说句闲话，喜欢三三的最好证明是
[heimu]A了这道题，祝你们成功（大雾[/heimu]

版权声明：本文是原创文章，版权归 无限UCW 所有。

本文链接：https://ucw.moe/archives/solution-luogu-p3952.html

本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。

最后修改：2019 年 08 月 01 日 10 : 09 AM
© 允许规范转载
欢迎投食喵 ~

发表评论

2 条评论

  1. bertwaver

    说实话，我也喜欢用一些奇奇怪怪的变量名，比如循环体变量我通常写的是cptime。hhh
    回复
  2. 阿珏

    虽然不知道在说什么，但看起来很牛逼的样子。
    御坂美琴节点可还行
    回复