趣题

Prob 1

JOISC2015 Limited Memory

现在有一个字符串 \(S\)，由 <,>,[,] 构成。现在只告诉你他的长度，你想要知道他是不是一个合法的括号串。

你需要实现一个函数 memory，每次你可以询问一次某个位置的字符，然后你需要返回一个 \([0,2^{22}-1]\) 的整数或者 \(-1,-2\)。如果返回 \(-1\) 代表这是一个括号串，\(-2\) 代表不是。否则你可以将你上次返回的整数作为参数再传入 memory 函数。

你需要再只使用该参数的情况下回答问题。你最多可以调用 \(15000\) 次 memory 函数。\(1\le |S|\le 100\)。

谔谔只能用 \(22\) 位，所以不能直接用一个栈来匹配。但是我们发现长度貌似很短，所以考虑直接对每个位置判断他能否匹配。\((i,j)\) 显然能够匹配的必要条件是 \([i+1,j-1]\) 这之间的数都得匹配上（当然这俩还得适配）。但是我们发现此时不再关心 \([i+1,j-1]\) 里 <,[ 的区别了。于是我们只需要记以下几个东西：

• 目前需要被匹配的位置（7位）
• 目前需要被匹配的类型（1位）
• 目前栈的大小（7位）
• 目前枚举到的位置（7位）

刚好 22 位，那么这道题就做完了。具体的细节可以参考代码。

#include<bits/stdc++.h>
#include "memory.h"
using namespace std;
char Get(int I);
// 字符串的范围是 [1, N] 
int calc(int type, int pos, int top, int now) {
	int ret = type | (pos << 1) | (top << 8) | (now << 15);
	return ret;
}
bool check(char ch) {
	// 判断是不是左括号 
	return ch == '<' || ch == '[';
}
int Memory(int N, int M) {
	if (N & 1) return -2;
	if (!M) return calc(0, 1, 1, 1);// 开始配对了 
	int type = M & 1, pos = (M >> 1) & 127, top = (M >> 8) & 127, now = (M >> 15) & 127;
	if (pos > N) return -1;// 尝试完了 
	if (pos < 1 || top < 1) return -1;// 错误的输入 
	if (now < 1 || now > N) return -2;// 没有找到匹配的位置 
	char val = Get(now);
	if (pos == now) {
		// 尝试匹配 pos 这个位置 
		if (check(val)) {// 往右枚举 
			return calc(val == '[', pos, 1, now + 1); 
		} else {// 往左枚举 
			return calc(val == ']', pos, 1, now - 1);
		}
	} else if (now > pos) {
		// s[pos] 是个左括号 
		if (!check(val)) top--;
		else top++;
		if (!top) return val == ">]"[type] ? calc(0, pos + 1, 1, pos + 1) : -2;
		else return calc(type, pos, top, now + 1); 
	} else {
		// s[pos] 是个右括号 
		if (check(val)) top--;
		else top++;
		if (!top) return val == "<["[type] ? calc(0, pos + 1, 1, pos + 1) : -2;
		else return calc(type, pos, top, now - 1); 
	}
}

题目来源

[1] : https://loj.ac/p/3005