【luogu P3952 时间复杂度】 题解

时间:2022-12-19 12:06:34

对于2017 D1 T2 这道题

实实在在是个码力题,非常考验耐心。

其实大体的思路并不是非常难想出来,但是要注意的小细节比较多。

题目链接:https://www.luogu.org/problemnew/show/P3952

思路

对于每一个程序,先读入L和O(),并将其中的时间复杂度抠出来。

其次整行读入字符串,即所给定的程序。

判断第一个字符是F or E

F i x y 需要把x y拿出来,把i压进栈

E 退栈 压进i后为了方便退栈及退栈时判断,用一个flag标记

每做完一个程序,与前面抠出来的时间复杂度对比判断yesnoerr即可。

注意

1.我的readx和ready函数比较暴力,直接截取常数和n可能存在的位置并保存。所以在考虑情况时,常数与n的位置不能搞错,也不能少考虑。

2.在每搞完一个程序时,要把初始值和标记都初始化一遍。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
int L,t,anso,codeo;//anso=0 O(1) anso=x O(n^x) 输入给的时间复杂度 codeo 自己算的时间复杂度 if anso==codeo yes else no if codeo==-1 err
string code[];//按行输入所给代码(F,E)
string ans;//读入给定的复杂度 O()
int readx(string x)
{
int num;
if(x[] >= '' && x[] <= '') num = x[]-'';
if(x[] >= '' && x[] <= '') num = (x[]-'')*+x[]-'';
if(x[] == 'n') num = ;
return num;
} //抠出给定的复杂度 x
int ready(string x)
{
int num;
if(x[] >= '' && x[] <= '' && x[] <= '' || x[] >= '') num = x[]-'';
if(x[] >= '' && x[] <= '' && x[] <= '' || x[] >= '') num = x[]-'';
if(x[] >= '' && x[] <= '' && x[] >= '' && x[] <= '') num = (x[]-'')*+x[]-'';
if(x[] >= '' && x[] <= '' && x[] >= '' && x[] <= '') num = (x[]-'')*+x[]-'';
if(x[] == 'n') num = ;
if(x[] == 'n') num = ;
return num;
}//抠出给定的复杂度 y
int check1()
{
int res;
if(ans[] == '') res = ;
if(ans[] == 'n')
{
if(ans[]<='' && ans[]>='')
res = ans[]-'';
if(ans[]<='' && ans[]>='')
res = (ans[]-'')* + ans[]-'';
}//记录输入给的复杂度
return res;
}
int check2()
{
stack<int> s;
int flag=-;//标记
bool fe[]={};//上面都是便于栈操作,fe来记录变量名
int res=,now=;//now来记录当前循环中的时间复杂度,res是整个程序的时间复杂度
bool cflag[]={};//记录变量是否重复 0 则没用过 1 用过 changeflag
int xnum,ynum; for(int i=;i<=L;i++)
{ if(code[i][]=='F')
{
int k=code[i][]-'a';
if(cflag[k]) return -;
s.push(k);
cflag[k] = ; xnum=readx(code[i]); ynum=ready(code[i]);
if(ynum-xnum>)
{
if(flag==-)
{
now++;
res=max(res,now);
fe[k]=;
}
}
if(xnum>ynum)
{
if(flag==-) flag=k;
}
} if(code[i][]=='E')
{
if(s.empty()) return -;
int k=s.top();
s.pop();cflag[k]=false;
if(flag==k) flag=-;
if(fe[k])
{
fe[k]=false;
now--;
}
}
}
if(s.size()) return -;
return res;
}
int main()
{
scanf("%d",&t);
while(t--)
{ scanf("%d ",&L);getline(cin,ans);
anso=check1(); for(int i=;i<=L;i++)getline(cin,code[i]);
codeo=check2(); if(codeo==-) cout<<"ERR"<<endl;
else
{
if(anso!=codeo) cout<<"No"<<endl;
if(anso==codeo) cout<<"Yes"<<endl;
}
}
return ;
}

【luogu P3952 时间复杂度】 题解的更多相关文章

  1. luogu P3952 时间复杂度 模拟

    题目链接 luogu P3952 时间复杂度 题解 直接模拟即可 注意不要直接return 我真是naive ...... 代码 #include<map> #include<sta ...

  2. &lbrack;LUOGU&rsqb; P3952 时间复杂度

    其实,也没那么难写 这种模拟题,仔细分析一下输入格式,分析可能的情况,把思路写在纸上,逐步求精,注意代码实现 主要思路就是算一个时间复杂度,和给出的复杂度比较,这就先设计一个函数把给出的复杂度由字符串 ...

  3. &lbrack;NOIp2017&rsqb; luogu P3952 时间复杂度

    跪着看评测很优秀. 题目描述 给你若干个程序,这些程序只有 For 循环,求这些程序的时间复杂度. Solution 大模拟.讲下细节. flag[i]flag[i]flag[i] 表示第 iii 位 ...

  4. P3952 时间复杂度

    P3952 时间复杂度 题目描述 小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机 ...

  5. 洛谷 P3952 时间复杂度 解题报告

    P3952 时间复杂度 题目描述 小明正在学习一种新的编程语言A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机会 ...

  6. 洛谷 P3952时间复杂度 (本地AC测评RE的伪题解)

    [题目描述] 小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机会来啦!下面请你编写 ...

  7. 洛谷 - P3952 - 时间复杂度 - 模拟

    https://www.luogu.org/problemnew/show/P3952 这个模拟,注意每次进入循环的时候把新状态全部入栈,退出循环的时候就退栈. 第一次就错在发现ERR退出太及时,把剩 ...

  8. 洛谷P3952 时间复杂度【字符串】【模拟】

    题目描述 小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机会来啦!下面请你编写程序 ...

  9. LOJ P3952 时间复杂度 noip 暴力 模拟

    https://www.luogu.org/problemnew/show/P3952 模拟,日常认识到自己zz. #include<iostream> #include<cstdi ...

随机推荐

  1. webform开发基础

    ASP.NET WebForm C/S(Client/Server):客户端服务器 B/S(Browser/Server):浏览器服务器 C/S和B/S的区别: 首先必须强调的是C/S和B/S并没有本 ...

  2. spring入门(一)

    前面介绍了spring环境的搭建,在搭建spring环境的时候分为java环境和javaWeb环境,在javaWeb环境下通常会结合springMVC使用,在java项目中只需要把spring的包导入 ...

  3. string&period;Format 格式化输出日期

    string.Format("{0:d}",System.DateTime.Now) 结果为:2009-3-20 (月份位置不是03) string.Format("{0 ...

  4. &period;net平台下socket异步通讯

    1,首先添加两个windows窗体项目,一个作为服务端server,一个作为客户端Client 2,然后添加服务端代码,添加命名空间,界面上添加TextBox控件 using System.Net; ...

  5. Java数据结构漫谈-ArrayList

    ArrayList是一个基于数组实现的链表(List),这一点可以从源码中看出: transient Object[] elementData; // non-private to simplify ...

  6. 1、java面试

    1.为什么用单例而不用static 答案:首先你要明白static是在什么时候初始化的,其设计意图是什么,单例就是我们运行的当前虚拟机中有且只有一个需要的对象,不存在重复.static是给类静态成员变 ...

  7. C语言开篇

    Linux下使用最广泛的C/C++编译器是GCC,大多数的Linux发行版本都默认安装,不管是开发人员还是初学者,一般都将GCC作为Linux下首选的编译工具. 1.小程序test_gets.c #i ...

  8. Numpy - 多维数组(上)

    一.实验说明 numpy 包为 Python 提供了高性能的向量,矩阵以及高阶数据结构.由于它们是由 C 和 Fortran 实现的,所以在操作向量与矩阵时性能非常优越. 1. 环境登录 无需密码自动 ...

  9. &lbrack;翻译&rsqb; &period;NET Standard 2&period;1 公布

    [翻译] .NET Standard 2.1 公布 原文: Announcing .NET Standard 2.1 校对: Cloud 自从大约一年前发布 .NET Standard 2.0以来,我 ...

  10. python面向对象高级:枚举

    在数学和计算机科学理论中,一个集的枚举是列出某些有穷序列集的所有成员的程序,或者是一种特定类型对象的计数.这两种类型经常(但不总是)重叠. 枚举是一个被命名的整型常数的集合,枚举在日常生活中很常见,例 ...