#include<bits/stdc++.h> using namespace std; /* O(1):无法进入循环、x>=y且x,y为常数、x=y=n 其他:n:为常数,y为n */ int maxk = 0;//最大级数 int tag = 0; //复杂度级数 int change(string s) { if (s == "O(1)") return 0; int num = 0; for (int i = 0; i < s.size(); i++) { if (s[i] >= '0' && s[i] <= '9') num = num * 10 + (s[i] - '0'); } return num; } //循环状态数据 struct status { int k; string i; bool pass;//1:通过 status(int a, string b, bool c) { k = a; i = b; pass = c; } }; set<string> m; stack<status> q; stack<status> w; void dealF(string i, string j, string k) { if (m.count(i))//元素查重 tag = 1; m.insert(i); auto num = q.top(); if (num.pass) { q.push({ num.k,i,1 }); return; } int l1=0, l2=0; if (j == "n") l1 = 2024; else l1 = change(j); if (k == "n") l2 = 2024; else l2 = change(k); if (l2 - l1 > 100) { num.k += 1; maxk = max(maxk, num.k); q.push({ num.k,i,0 }); } else if (l1 > l2) { q.push({ num.k,i,1 }); } else { q.push({ num.k,i,0 }); } } void dealE() { if (q.size()<=1) { tag=1; return; } auto k1 = q.top(); q.pop(); m.erase(k1.i); } void judge() { q = w; m.clear(); maxk = 0, tag = 0; int L; string str; cin >> L >> str; int temp = L; int s = change(str); q.push({ 0,"*",0 });//初始化栈 while (L--) { string a; cin >> a; if (a == "F") { string i, j, k; cin >> i >> j >> k; dealF(i, j, k); } else dealE(); } if (tag || q.size()!=1) { cout << "ERR" << endl; return; } else if (maxk == s) cout << "Yes" << endl; else cout << "No" << endl; } int main() { int t; cin >> t; while (t--) { judge(); } return 0; }
- 用栈模拟循环过程
- 关联式存储器,set:有序无重复元素的集合
- 读入数据的处理
- 循环中的特征数据:变量,时间复杂度,是否进入下一次循环标志