社区讨论

64求調

P3952[NOIP 2017 提高组] 时间复杂度参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhj0p8xl
此快照首次捕获于
2025/11/03 18:49
4 个月前
此快照最后确认于
2025/11/03 18:49
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//Emotional Damage
struct order{
	char tape,i;
	string st,ed;
};
int line,o=0,_;
order ord[105];
int check(){
	int res=0,now=0,num=0;
	stack<int> s;
	int vis[26]={};
	for(int i=0;i<line;i++){
		if(ord[i].tape=='F'){
			if(vis[ord[i].i-'a'])return -1;
			vis[ord[i].i-'a']=1;
			s.push(ord[i].i-'a');
			num++;
			if(ord[i].st!="n"&&ord[i].ed=="n"){
				now++;
			}
			else{
				int a,b;
				if(ord[i].st=="n")a=1000;
				else a=stoi(ord[i].st);
				if(ord[i].ed=="n")b=1000;
				else b=stoi(ord[i].ed);
				if(a>=b){
					num=0;
					i++;int m;
					for(m=1;m&&i<line;i++){
						if(ord[i].tape=='F'){
							m++;
						}
						else if(ord[i].tape=='E'){
							m--;
						}
					}
					vis[s.top()]=0;
					s.pop();
					if(m)return -1;
					res=max(res,now),now=0;
				}
			}
		}
		else if(ord[i].tape=='E'){
			if(s.empty())return -1;
			vis[s.top()]=0;
			s.pop();
			num--;
			if(num==0)res=max(res,now),now=0;
		}
	}
	if(s.size())return -1;
	return res;
}
int main() {
	cin>>_;
	while(_--){
		o=0;
		cin>>line;
		string O;
		cin>>O;
		if(O=="O(1)"){
			o=0;
		}
		else{
			string x=O.substr(4,O.size()-5);
			o=stoi(x);
		}
		for(int i=0;i<line;i++){
			cin>>ord[i].tape;
			if(ord[i].tape=='F'){
				cin>>ord[i].i>>ord[i].st>>ord[i].ed;
			}
		}
		int result=check();
		if(result==-1)cout<<"ERR\n";
		else if(result==o)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
WA On 5 6 7 10
調處必関

回复

1 条回复,欢迎继续交流。

正在加载回复...