一个错误的代码
- 没有用栈 ： 之前的循环如果没有执行，
down = 0，会对后面产生影响，down实际上不需要
写了将近两个小时。。。郁闷
#include<cstdio>
#include<algorithm>
#include<locale>
#include<cstring>
#include<queue>
#define N 1000001
using namespace std;
int stk[110],u[30],top;
int L,t;
int output[110];
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(int k = 1;k <= t;++k)
{
char cmd[11];
int cnt = 0,ans,down = 1,complex = 0,maxc = -1;
memset(u,0,sizeof(u));
scanf("%d",&L);
scanf("%s",cmd);
if(cmd[2] == '1')
{
ans = 0;
}
else
{
int i = 4;
ans = 0;
while(isdigit(cmd[i]))
{
ans = ans*10 + cmd[i++] - 48;
}
}
getchar();
for(int i = 1; i <= L; ++i)
{
gets(cmd);
int x = 0,y = 0;
if(cmd[0] == 'F' && down == 1)
{
++cnt;
int tx = 4,ty = 6;
if(isdigit(cmd[4]))
{
while(cmd[tx] != ' ')
{
x = x*10 + cmd[tx++] - 48;
}
}
else{
tx = 5;
x = N;
}
if(isdigit(cmd[tx + 1]))
{
ty = tx + 1;
while(cmd[ty] != ' ')
{
y = y*10 + cmd[ty++] - 48;
}
}
else
{
y = N;
}
if(x == N){
down = 0;
}
else
{
if(y == N)
{
if(u[cmd[2] - 'a' + 1] == 0){
u[cmd[2] - 'a' + 1] = 1;
stk[++top] = cmd[2] - 'a' + 1;
complex++;
}
else
{
printf("Conflict
");
down = 0;
output[k] = -1;
}
}
else
{
if(x >= y) down = 0;
else if(x < y)
{
if(u[cmd[2] - 'a' + 1] == 0)
{
u[cmd[2] - 'a' + 1] = 1;
stk[++top] = cmd[2] - 'a' + 1;
complex++;
}
else
{
printf("Conflict
");
down = 0;
output[k] = -1;
}
}
}
}
}
else if(cmd[0] == 'E')
{
--cnt;
if(down == 1)
{
u[stk[top--]] = 0;
maxc = max(maxc,complex);
complex = 0;
}
//printf("cnt--,%d
",cnt);
}
else if(down == 0)
{
++cnt;
maxc = max(maxc,complex);
if(maxc == ans)
{
output[k] = 1;
}
else
{
output[k] = 0;
}
}
}
maxc = max(maxc,complex);
if(maxc == ans)
{
output[k] = 1;
}
else
{
output[k] = 0;
}
if(cnt != 0) output[k] = -1,printf("cnt != 0 %d
",cnt);
}
for(int i = 1;i <= t;++i)
{
if(output[i] == 1) printf("Yes
");
else if(output[i] == -1) printf("ERR
");
else printf("No
");
}
return 0;
}
脑子呢？
决定放弃，参考Luogu上的题解(离线做法)，要用栈！！！
#include<cstdio>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxl=105;
int t,l,w;
string o;
string code[maxl];
//一个函数来获取代码中的正整数
//用于获得c串下标为x的中的正整数，我们将 F x 1 n 中的n也看作整数，有利于后续对循环的处理。
//n也就是特判一下，其余的模拟快读就好了
int sread(int &x,string c)
{
int res=0;
int len=c.size();
while(c[x]<'0' || c[x]>'9'&&x<c.size())
{
if(c[x]=='n')
{
++x;
return 1000000;
}
++x;
}
while(c[x]>='0' && c[x]<='9')
{
res*=10;
res+=c[x]-'0';
++x;
}
return res;
}
//写一个函数以获取复杂度:
int geto()
{
int res=0,x=3;
int len=o.size();
if(o[2]=='n') res=sread(x,o);
else res=0;
return res;
}
然后开始模拟循环，同时判断语法是否有误，并计算复杂度。我们写一个int check()函数，结果用res保存，若返回值为-1，则代表有语法错误，否则代表代码复杂度。（当前复杂度用now保存）。
首先考虑没有语法错误的情况：
我们在模拟的时候，肯定需要一个栈s。
遍历一遍代码:
- 如果遇到了F，那么获取变量名，用k保存，获取 F x i j 中的 i j，分别用 a b 保存。将 k 进栈。
- 如果 b<a ,那么没有进入循环。用一个 flag 来保存最早的没有没有进入的 k。如果都进入了，则flag为-1。
- 如果 a<=b ,代表进入循环，此时若 b-a>1000 并且 flag 为 -1 ,则本层循环对复杂度有贡献，执行 now++ 操作。同时我们用 ef[26] 保存 now++ 时 k 的信息(ef[k]=true)。（在k出栈时now - -,ef[k]=false）并更新res。（res=max（res，now））
如果遇到了E，那么同样获取变量名 k ，将k弹出（因为没有语法错误，栈一定不空）。同时判断 flag是否为 k ，若为 k ，则 flag=-1 代表已经出了没有贡献的循环。在判断k是否对复杂度有贡献，若有，则now-,ef[k]=false；
最后return res；
再来在此基础上考虑有语法错误的情况：
- F 和 E 不匹配 （类似于括号匹配）：
① F比E多，只需在k出栈时判断栈是否为空，若为空则有语法错误，直接return -1。
② F比E少，只需在遍历完代码后判断栈是否不为空，若不空则有语法错误，直接return -1。- 新建的变量与已经存在但未被销毁的变量重复：
用一个bool数组 ins[26] 表示当前，哪些变量被用过。那么只需在原来的基础上：
① 在k入栈时，判断k是否已经被用过（即k是否在栈中），若用过则有语法错误，直接return -1。
② 在k出栈时，判断栈是否为空，若为空则有语法错误，直接return -1。
分析到此结束。
int check()
{
int res=0,now=0;
int a,b,x;
stack<int> s;
int flag=-1;
bool ins[26]= {0};
bool ef[26]= {0};
for(int i=1; i<=l; i++)
{
if(code[i][0]=='F')
{
int k=code[i][2]-'a';
if(ins[k]) return -1;
s.push(k);
ins[k]=true;
x=4;
a=sread(x,code[i]);
b=sread(x,code[i]);
//printf("a:%d b:%d
",a,b);
if(b-a>1000)
{
if(flag==-1)
{
now++;
res=max(res,now);
ef[k]=true;
}
}
if(a>b)
{
if(flag==-1) flag=k;
}
}
if(code[i][0]=='E')
{
if(s.empty()) return -1;
int k=s.top();
s.pop();
ins[k]=false;
if(flag==k) flag=-1;
if(ef[k])
{
ef[k]=false;
now--;
}
}
}
if(s.size()) return -1;
return res;
}
int main()
{
scanf("%d",&t);
while(t--)
{
int ww;
scanf("%d ",&l); //选用getline(cin,s)读入一整行代码;
getline(cin,o); //注意%d后的空格（输入中l后有一个空格）
w=geto();
for(int i=1; i<=l; i++) getline(cin,code[i]);
ww=check();
if(ww==-1) puts("ERR");
else
{
if(ww==w) puts("Yes");
else puts("No");
}
}
}