Mobius_CaO @ 2024-09-09 09:27:26
#include<bits/stdc++.h>
using namespace std;
int checko(string O){
if(O=="O(1)")return 0;
if(O[5]==')')return (int)(O[4]-'0');
return (int)((int)(O[4]-'0')*10+(int)(O[5]-'0'));
}
int numb(string T){
if(T=="n")return 10000;
int num=0;
for(int i=0;i<T.length();i++){
num*=10;
num+=T[i]-'0';
}
return num;
}
void solve(){
int n,o;
string O;
cin>>n>>O;
o=checko(O);
string cz;
string jl[101];
map<char,bool> mp;
for(int i=0;i<n;i++){
char c;
cin>>c;
cz=cz+c;
if(c=='F'){
string bl,st,ed;
cin>>bl>>st>>ed;
jl[i]=bl+st+" "+ed;
}
}
int ix=0,ib=0,cs[101],maxi=0;
char stb[101];
int o1=0;
for(int i=0;i<=n;i++)cs[i]=0;
for(int i=0;i<n;i++){
if(cz[i]=='F'){
ix++;
maxi=max(maxi,ix);
string bl,st,ed;
bl=jl[i][0];
int soe=0;
string num="";
for(int j=1;j<jl[i].length();j++){
if(jl[i][j]==' '){
st=num;
num="";
soe=1;
}
else num=num+jl[i][j];
}
ed=num;
char bb=bl[0];
stb[ix]=bb;
if(mp[bb]==1){
printf("ERR\n");
return ;
}
mp[bb]=1;
if(st!="n"&&ed=="n"){
cs[ix]=1;
}
if(st=="n"&&ed!="n"&&cs[ix]!=1&&ix>=maxi||numb(st)>numb(ed))cs[ix]=-1;
}
else {
if(ix<=0){
printf("ERR\n");
return ;
}
mp[stb[ix]]=0;
cs[ix+1]=0;
ix--;
int o2=0;
for(int j=0;j<n;j++){
if(cs[j]==1)o2++;
if(cs[j]==-1)break;
}
o1=max(o1,o2);
}
maxi=max(maxi,ix);
}
if(ix!=0){
printf("ERR\n");
return ;
}
int o2=0;
for(int i=0;i<n;i++){
if(cs[i]==1)o2++;
if(cs[i]==-1)break;
}
o1=max(o1,o2);
if(o1==o)printf("Yes\n");
else{
printf("No\n");
}
}
int main(){
int _;
scanf("%d",&_);
while(_--){
solve();
}
return 0;
}by _Vistion_ @ 2024-09-09 10:36:08
求关
#include <bits/stdc++.h>
using namespace std;
struct Node{
char var; // 循环定义的变量名
int f; // 表示是否是由于这层循环的起始>终止，导致flag1==1；这样可以判断什么时候取消flag1
int g; // 表示这层循环是否给cnt++（判断在回退时是否对cnt-1）
};
void solve(){
int L; string Tim; // 输入行数、预估的时间复杂度
cin >> L >> Tim;
int flag = -1;
if(Tim == "O(1)") flag = 0; // 相当于复杂度是O(n^0)=O(1)
else sscanf(Tim.c_str(), "O(n^%d)", &flag); // 否则表示预估复杂度为O(n^flag)
vector <int> vis(256); // 变量桶，记录是否重复定义循环变量
stack <Node> stack1; // 因为循环调用是顺序调用，在遇到E标签退出时，应该是倒着退出的，栈刚好可以满足这个需求
int err = 0; // 记录是否出现错误
int maxpower = 0; // 记录出现的最大循环层数（只记录有n的，不记录常数）
int cnt = 0; // 记录当前出现的循环层数（同样只记录n）
int flag1 = 1; // 这层循环是否会执行（会遇到 F i 9 4 这样无法执行的循环，注意此时其后面属于它的循环也不能执行）
for(int _ = 1; _ <= L; _ ++){
char op, i; // 标识字符、当前循环变量
string st, ed; // 起始、结束范围
cin >> op;
if(op == 'F'){
cin >> i >> st >> ed;
if(vis[i] == 1){ // 出现重复变量
err = 1;
continue;
}
vis[i] = 1;
// 注意以上要放在判断flag1==0的if上面，因为就算不执行循环也要检查是否有理论错误（如变量层数、E标签闭合等）
if(flag1 == 0){ // 这一层不会执行，不做处理
stack1.push({i, 0, 0}); // 不是有这个导致的
continue; // 下面不执行
}
if(isdigit(st[0]) && isdigit(ed[0])){
int x = stoi(st), y = stoi(ed);
if(x > y){ // 题目说了循环只能从起始向终止执行，如果起始大于终止，则该循环不会执行
flag1 = 0; // 注意这样也不能执行下面的循环
stack1.push({i, 1, 0}); // Node.f赋值为1表示是由于这层循环起始>终止引起的
}
else{ // 否则，是常数阶，不加层数
stack1.push({i, 0, 0});
}
}
else if(st == "n" && isdigit(ed[0])){ // 同上，由于起始>终止，不能执行
flag1 = 0;
stack1.push({i, 1, 0}); // Node.f赋值为1表示是由于这层循环起始>终止引起的
}
else if(isdigit(st[0]) && ed == "n"){ // 算一层n
cnt ++;
stack1.push({i, 0, 1}); // Node.g赋值为1表示算了这一层
}
else if(st == "n" && ed == "n"){ // 这样只执行一次，属于常数阶
stack1.push({i, 0, 0});
}
}
else{ // op == 'E'
if(stack1.empty()){ // 说明循环标签没有闭合，出现错误
err = 1;
continue;
}
maxpower = max(maxpower, cnt); // 统计最大层数
Node u = stack1.top(); stack1.pop();
vis[u.var] = 0; // 撤销已定义的变量
if(u.f == 1) flag1 = 1; // 取消flag1标记
if(u.g) cnt --; // 取消上一次的循环层数
}
}
// 注意栈不空，说明E闭合不对
if(err == 1 || !stack1.empty()) puts("ERR");
else if(flag != maxpower) puts("No");
else puts("Yes");
}
signed main(){
int T; cin >> T;
while(T --) solve();
return 0;
}by Mobius_CaO @ 2024-09-11 09:22:19
@YZ_zhang 已过感谢