[NOIP2017]时间复杂度
皎月半洒花
2018-05-02 12:52:30
这个题是我 $A$ 的第三百个……那么首先：
## $\color{pink}AC300$祭！๑乛◡乛๑
嗯，那么下面开始干正事：
## 一、对于这个题的概述
先说明一下，这个题虽然我花了大约两个上午——大约 $5h$ 的时间把它连码带调搞出来了，好像看上去很毒瘤，但是其实这个题根本不毒瘤，只是有些细节值得注意罢了。
不得不说，这是道很不错的题，因为既没有多么难，规则浅显易懂，也会有很多的细节不注意导致 GG（本蒟蒻就几乎把所有这个题能得的分数遍历了一遍 ORZ,多亏可以下载数据……不过考试的时候好像肯定会 GG)。
那么对于这道题我在做的时候就发现，出题人真的是太良心了，因为以下几点完全就是怕 NOIP 出的太难，来均衡难度的：
### 1 循环变量的上下界只有一个字母会出现：$n$。
但是从渐进意义上来讲，任何一个字母都是可以的，而这个地方只出现了 $n$，所以这是送分的。
#### 毒瘤版本：
循环的上下界可以有别的字母，那么以下这种情况也需要考虑进总的时间复杂度，按照 $O(n)$ 算：
```cpp
F i x y
F j 1 i
E
E
```
那么这个时候就要牵扯到除了 $n$ 以外的其他字母实现有没有被定义（如果未定义输出 `ERR`）等诸多问题,比如可能这样：
```cpp
F i 3 66
F j 1 i-1
F k i j
E
E
E
```
那么实际上，在上面这组样例中，$k$这层循环是进不去的。
### 2 所有常数都小于一百
这一点也很良心，由于都小于一百，所以我们在输入或者其他操作里，只用考虑两位就可以。不要小瞧这一点……这直接决定了模拟的难度。
#### 毒瘤版本：
在每个循环中，循环变量的绝对值保证在 `int` 范围里。
### 3、时间复杂度方面，不会出现$log$以二为底
嗯，以上就是本蒟蒻 yy 出来的毒瘤版本，那么看起来这道题不算是个毒瘤题……但为什么会做错呢？因为细节不注意啊 ORZ。
## 二、这个题的做法
我还是倒着说吧：
### 满分做法：
**读入**：
我们先用 `while` 按字符读入每个程序的第一行，抠出需要检验的复杂度， $O(1)$ 用 $0$ 来存 $[n^0=1 (n\neq 0)]$。
注意，有可能有两位数，需要多扣一位……
```cpp
while(o!=')'){
if(o=='1'&&!chk)
need_check=0;
if(o=='n'){
cin>>o>>o;
need_check=o-48;
chk=1;
}
o=getchar();
if(isdigit(o)&&chk)need_check*=10,need_check+=(o-48);
}
getchar();
```
至于最后为什么要再 `getchar()` 一次……自己试试就知道了。
那么接下来就要按行读入循环了，比较简单。
**初始化**
为了使码风简洁，所以写到函数里了。这个地方我用到了三个栈，一个用来记录每个循环的答案（因为有可能有多个相互独立的循环），一个用来记录每次 `F` 时读入的循环上下界。以上两个都是 `int` 栈,还有一个 `char` 栈，存储每次定义的循环变量，而这个字符栈搭配一个 `bool` 性的数组，用于记录是否可用。
```cpp
#define MAX 1000000
int i,x,y,t,tt,num,cntf,cnte,res,ans[MAX],T,l,now,need_checks,stk[MAX];
bool check[150],flag,spj,chk;
char s[3010],o,stkk[MAX];
inline void init(){
memset(check,0,sizeof(check));
memset(stkk,0,sizeof(stkk));
memset(stk,0,sizeof(stk));
now=t=tt=cntf=cnte=res=flag=spj=chk=0;
}
```
ps: 虽然不知道用一个二进制位的$0$来初始化字符数组会怎样……不过好像海星。
`cnte` 和 `cntf` 用来记录 `F` 和 `E` 的数量， `num` 、 `t` 、 `tt` 都是栈的指针，`spj` 用来判断一个独立循环是否结束（如果结束就把当前的得到压入栈），`now` 用来搭配 `spj` 记录当前独立循环体的时间复杂度， `chk` 用于读入每个程序的第一行（即含有需要判断的时间复杂度的那一行），`flag` 用于判断输出。
**主要操作**
对于读入的东西，分类讨论，然后 `continue`……没什么可说的。
```cpp
while(l--){
gets(s);
for(i=0;i<strlen(s);){
while(s[i]==' ')i++;
if(s[i]=='F'){
if(cntf>cnte&&cnte){
ans[++num]=now;
now=0;
}
cntf++,i++;
continue;
}
if(s[i]=='E'){
y=stk[t],t--;
x=stk[t],t--;
cnte++;
if(cnte==cntf)spj=1;
if(x!=MAX){
if(y==MAX)now++;
if(y<x)now=0;
}
else{
if(y!=MAX)now=0;
}
check[stkk[tt]-'a']=0;
tt--,i++;
if(spj){
ans[++num]=now;
now=0;
spj=0;
}
continue;
}
if(!isdigit(s[i])&&s[i]!='n'){
if(check[s[i]-'a']&&!flag){
cout<<"ERR"<<endl;
flag=1;
}
stkk[++tt]=s[i];
check[s[i]-'a']=1;
}
else {
if(s[i]=='n'){
my_push(s[i],s[i+1]);
i+=2;
}
my_push(s[i],s[i+1]);
}
i++;
}
}
```
唯一需要注意的是入栈操作，因为要把字符压入整型，所以我又写了个函数来入栈。入栈的时候当然需要注意是不是两位数……
哦，还有，如果这次轮到 $n$ 入栈了，那么就随便入栈一个大于一百的数即可。
```cpp
inline void my_push(char a,char b){
if(isdigit(a)){
if(isdigit(b)){
stk[++t]=(a-48)*10+b-48;
i++;
}
else stk[++t]=a-48;
}
if(a=='n')stk[++t]=MAX;
}
```
最后判断一下输入输出即可。
```cpp
if(!flag&&cntf!=cnte){
cout<<"ERR"<<endl;
flag=1;
}
while(num){
res=max(res,ans[num]);
num--;
}
if(!flag) if(res==need_check) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
```
嗯~o(*￣▽￣*)o这就是满分做法了。
### $72$ 分做法
这个很坑爹……输出完直接 `break` 会导致你虽然在主观上已经不管这个询问接下来如何，但是客观上，你的程序是一边输入一边操作的，所以你接下来的输入就会 GG，这也就是引入 `mark` 的原因。
### $63$ 分做法
在 72 分的基础上，再输入 `need_check` 忘记判断 $O(n^{11})$ 和 $O(1)$ 了……这就很爆炸。
### $45$ 分做法
没有考虑嵌套在循环中的循环体的独立性，那么我们可以发现，当你在读入一个 `F` 时，如果现在 `F` 的数量大于 `E` 的数量并且 `cnte!=0`，就说明是这种情况那么就提前将结果入栈即可。
```cpp
if(s[i]=='F'){
if(cntf>cnte&&cnte){
ans[++num]=now;//提前入栈
now=0;
}
cntf++,i++;
continue;
}
```
### $27$ 分做法
忘记了自然数可以是两位数……所以赶紧打了个入栈。
### $0$ 分做法
全部的爆零都是因为我忘记了把调试用的 `freopen` 注释掉 ORZ。
总结：我认为这个题我在考场上挂的情有可原……因为我既蒟又不细心 OTZ。
还有，如果那位大佬 `hack` 掉了我的程序，别忘了通知我哇！
```cpp
#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
int i,x,y,t,tt,num,cntf,cnte,res,ans[MAX],T,l,now,need_check,stk[MAX];
bool check[150],flag,spj,chk;
char s[3010],o,stkk[MAX];
inline void init(){
memset(check,0,sizeof(check));
memset(stkk,0,sizeof(stkk));
memset(stk,0,sizeof(stk));
now=t=tt=cntf=cnte=res=flag=spj=chk=0;
}
inline void my_push(char a,char b){
if(isdigit(a)){
if(isdigit(b)){
stk[++t]=(a-48)*10+b-48;
i++;
}
else stk[++t]=a-48;
}
if(a=='n')stk[++t]=MAX;
}
int main(){
cin>>T;
while(T--){
init();
cin>>l>>o;
while(o!=')'){
if(o=='1'&&!chk)
need_check=0;
if(o=='n'){
cin>>o>>o;
need_check=o-48;//the same as above
chk=1;
}
o=getchar();
if(isdigit(o)&&chk)need_check*=10,need_check+=(o-48);
}
getchar();
while(l--){
gets(s);
for(i=0;i<strlen(s);){
while(s[i]==' ')i++;
if(s[i]=='F'){
if(cntf>cnte&&cnte){
ans[++num]=now;
now=0;
}
cntf++,i++;
continue;
}
if(s[i]=='E'){
y=stk[t],t--;
x=stk[t],t--;
cnte++;
if(cnte==cntf)spj=1;
if(x!=MAX){
if(y==MAX)now++;
if(y<x)now=0;
}
else{
if(y!=MAX)now=0;
}
check[stkk[tt]-'a']=0;
tt--,i++;
if(spj){
ans[++num]=now;
now=0;
spj=0;
}
continue;
}
if(!isdigit(s[i])&&s[i]!='n'){
if(check[s[i]-'a']&&!flag){
cout<<"ERR"<<endl;
flag=1;
}
stkk[++tt]=s[i];
check[s[i]-'a']=1;
}
else {
if(s[i]=='n'){
my_push(s[i],s[i+1]);
i+=2;
}
my_push(s[i],s[i+1]);
}
i++;
}
}
if(!flag&&cntf!=cnte){
cout<<"ERR"<<endl;
flag=1;
}
while(num){
res=max(res,ans[num]);
num--;
}
if(!flag) if(res==need_check) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
```