题解：P15119 [ICPC 2024 LAC] Expanding STACKS!
前言
题目传送门
思路讲解
一语道破天机。
如果两位顾客排队时间有交集，那么这两位顾客排在不同的队伍。
证明过程
假设有两位客人，输入为：+1 +2 -1 -2
很明显，两人在不同的队伍。
假设第一个人排在第一队，第二个人也排在第一队，这时候栈顶是第二个人，第一个人被压住了，无法出队，所以他们只能在两个不同的队伍里。
所以我们可以根据顾客的两个队伍作二分图，跑一边即可。
AC Code
#include <bits/stdc++.h>
#define int long long
#define MAXN 2005
using namespace std;
int a[MAXN], push[MAXN], pop[MAXN];
int n;
vector<int> v[MAXN];
int vis[MAXN];
inline void dfs(int u)
{for (auto v : v[u]){if (!vis[v]){vis[v] = 3 - vis[u];dfs(v);}else{if (vis[v] != 3 - vis[u]){puts("*");exit(0);}}}
}
signed main()
{cin >> n;for (int i = 1; i <= n * 2; i++){cin >> a[i];if (a[i] > 0) push[a[i]] = i;else pop[-a[i]] = i;}for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){if ((push[i] > push[j] || pop[j] > pop[i]) && (push[j] > push[i] || pop[i] > pop[j]) && pop[i] > push[j] && pop[j] > push[i]){v[i].push_back(j);v[j].push_back(i);}}}for (int i = 1; i <= n; i++){if (!vis[i]) vis[i] = 1, dfs(i);}for (int i = 1; i <= n; i++){if (vis[i] == 1) cout << "G";else cout << "S";}return 0;
}