题意分析

这道题目要求我们判断给定的序列是否表示一个合法的广义套娃结构。广义套娃的定义如下：

1. 序列表示：每个玩具$k$在序列中由两个整数$-k$和$k$表示，其中负号在前，正号在后。例如，玩具$2$表示为$-2$和$2$。
2. 嵌套规则：如果一个玩具$m$直接包含玩具$n_1, n_2, \ldots, n_r$，则必须满足$n_1 + n_2 + \ldots + n_r < m$。
3. 匹配规则：序列中的每个$-k$必须与后续的$k$正确匹配，形成嵌套结构。

解题思路

1. 栈结构模拟：
   使用栈来模拟嵌套过程。遍历序列时：

   • 遇到负数$-k$时，将其压入栈中，表示进入一个新的玩具$k$。
   • 遇到正数$k$时，检查栈顶是否为$-k$。如果不是，则匹配失败；如果是，则弹出栈顶，并检查当前玩具$k$的直接子玩具是否满足$sum < k$。
   • 每次弹出栈顶时，需要将子玩具的和传递给父玩具（即新的栈顶），以便父玩具计算其直接子玩具的总和。

2. 验证条件：

   • 匹配正确性：每个$k$必须与最近的$-k$匹配，否则序列非法。
   • 嵌套合法性：每个玩具$k$的直接子玩具总和必须严格小于$k$，否则非法。
   • 完整性：最终栈必须为空，表示所有玩具正确闭合。

标程

#include <iostream>
#include <cstdio>
#include <stack>
#define MAX 10000005
using namespace std;
struct Node
{
	int x,y;
};
int main()
{
	stack<Node> sta;
	int t;
	char c;
	bool ok=true;
	Node first,temp;
	first.x=-MAX;
	first.y=MAX;
	sta.push(first);
	
	while(cin>>t)
	{
		c=getchar();
		if(ok)
		{
			if(t<0)
			{
				temp.x=t;
				temp.y=-t;
				if(sta.top().y>temp.y)
				{
					if(sta.size()>1)
						sta.top().y-=temp.y;
					sta.push(temp);
				}
				else
					ok = false;
			}
			else
			{
				if(sta.top().x+t!=0)
					ok = false;
				else
					sta.pop();
			}
		}
		
		if(c=='\n')
		{
			if(sta.size()!=1)
				ok=false;
			while(sta.size()!=1)
				sta.pop();
			if(ok)
				printf(":-) Matrioshka!\n");
			else
				printf(":-( Try again.\n");
			ok = true;
		}
	}
	return 0;
}