• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

#交互,栈#LOJ 3005 「JOISC 2015 Day 4」Limited Memory

admin

11 月 28, 2021

题目


分析

一开始想的是栈的匹配,但是位数不够,而且还忘记写memory.h,
考虑它询问次数不超过一万五千次,(O(n^2))的询问是绰绰有余的,
如果每一个符号都能被匹配那整个串也能被匹配,而中间的符号怎么样可以忽略,只需要栈为空时两端相等即可
那么考虑维护当前需要匹配的点、当前位置、需要匹配点是什么类型的符号以及栈的大小,正好用二进制压成22位


代码

#include "memory.h"
int Get_Hash(int is_bracket,int Top,int x,int now){
	return is_bracket|(Top<<1)|(x<<8)|(now<<15);
}
int Memory(int N, int M) {
	int is_bracket=M&1,Top=(M>>1)&127,x=(M>>8)&127,now=(M>>15)&127;
	if (!x) return Get_Hash(0,0,1,1);
	if (x>N) return -1; else if (now<1||now>N) return -2;
	char ch=Get(now);
	if (x==now){
		if (ch=='<'||ch=='[') return Get_Hash(ch=='[',1,x,now+1);
		    else return Get_Hash(ch==']',1,x,now-1);
	}else if (x<now){
		if (ch=='>'||ch==']') --Top; else ++Top;
		if (!Top&&!(is_bracket^(ch=='>'))) return -2;
		    else if (!Top) return Get_Hash(0,0,x+1,x+1);
		return Get_Hash(is_bracket,Top,x,now+1);
	}else{
		if (ch=='<'||ch=='[') --Top; else ++Top;
		if (!Top&&!(is_bracket^(ch=='<'))) return -2;
		    else if (!Top) return Get_Hash(0,0,x+1,x+1);
		return Get_Hash(is_bracket,Top,x,now-1);
	}
}

发表回复