URAL 2019. Pair: normal and paranormal（***栈模拟）

2019. Pair: normal and paranormal

If you find yourself in Nevada at an abandoned nuclear range during Halloween time, you’ll become a witness of an unusual show. Here Ghostbusters hold annual tests for new versions of their proton packs. There are n Ghostbusters and n portable traps with ghosts, all are located on a semicircle. Each trap contains exactly one ghost. The ghosts may be of different types, but each Ghostbuster can neutralize with his weapon only one type of the evil spirits.

On the count of three all ghost traps open at once and all Ghostbusters start to fire. Of course, each Ghostbuster shoots at the ghost, which his proton gun is able to neutralize. The most important thing here is not to cross proton beams of the guns.

You know positions of all Ghostbusters and all the traps in this year’s tests. For each Ghostbuster determine which ghost he should shoot at, so that all the ghosts are neutralized and no two gun beams cross. You can assume that all proton beams are in the same horizontal plane and they don’t shoot ghosts through in case of a hit.

Input

In the first line there is an integer n that is the number of Ghostbusters (1 ≤ n ≤ 5 000). In the second line the sequence of 2n Latin letters is written, describing the allocation of the Ghostbusters and the traps on the semicircle. Uppercase letters correspond to the Ghostbusters and lowercase letters correspond to the traps. For example, “a” stands for a trap with the ghost of type “a”, while “A” stands for the Ghostbuster with the gun neutralizing ghosts of type “a”. The sequence has exactly nlowercase letters and exactly n uppercase letters.

Output

If the problem has a solution, output n space-separated integers g1, g2, …, gn, where gi is the number of the ghost i-th Ghostbuster should shoot at. Both Ghostbusters and ghosts are numbered with integers from 1 to n in the order of their positions along the semicircle. All gi must be pairwise different. If the problem has several solutions, output any of them. If the problem has no solution, output “Impossible”.

Samples

input	output
2 AbBa	2 1
2 AbaB	Impossible
1 Ab	Impossible

Problem Author: Denis Dublennykh (prepared by Oleg Merkurev)

题意：有n个人每人拿着一把枪想要杀死n个怪兽，大写字母代表人，小写字母代表怪兽。A只能杀死a，B只能杀死b，如题目中的图所示，枪的弹道不能交叉。人和怪兽的编号分别是1到n，问是否存在能全部杀死的情况，如果存在则输出编号1到n的每个人杀死的怪兽的编号，如果不能输出"Impossible"。

题解：

找相邻的字母是配对的，然后将这两个字母标记之后继续找没有被标记的相邻字母，并将这两个配对的字母存在一个数组里。 
最后将这些2*n的序号变成n的序号就可以。

突然想起括号匹配来，这种不就是有点像吗，只不过还算有点特点，首先是括号的种类多了，再者）（也算是匹配的，想法还算巧妙。

#include <bits/stdc++.h>
using namespace std;
struct T{
  char ch;
  int idx;
  T(char a,int b){ch=a,idx=b;}
};

stack<T> st;
const int maxn=10100;
int n;
char s[maxn];
int ans[maxn];  ///结果记录
int tmp[maxn];  ///记录小写字母的排序

void add(int i,int j)
{
    if(s[i]<s[j]) ans[i]=tmp[j];
    else ans[j]=tmp[i];
}

int main()
{
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",s);
        while(!st.empty())st.pop();
        for(int i=0,cnt=0; i<2*n; i++){
            if(s[i]>='a' && s[i]<='z')
                tmp[i]=++cnt;
        }
        for(int i=0;i<2*n;i++){
            if(!st.empty() && abs(st.top().ch-s[i])==32 )
               add(i,st.top().idx),st.pop();
            else
                st.push(T(s[i],i));
        }
        if(!st.empty())
            printf("Impossible
");
        else
        {
            for(int i=0,cnt=1; i<2*n; i++)
                if(s[i]>='A' && s[i]<='Z')
                    printf("%d%c", ans[i], cnt==n? '
' : ' '),cnt++;
        }
    }
    return 0;
}

网上不少这种思路，感觉有点low，不过也算是一种思路，时间比我上面的长好多！！！

#include <bits/stdc++.h>
using namespace std;

const int maxn=10100;

int n;
char s[maxn];
bool vis[maxn];
int ans[maxn];
int tmp[maxn];

void add(int i,int j)
{
    if(s[i]<s[j]) ans[i]=tmp[j];
    else ans[j]=tmp[i];
}

int main()
{
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",s);
        memset(vis,0,sizeof vis);
        for(int i=0,cnt=0; i<2*n; i++)
            if(s[i]>='a' && s[i]<='z')
                tmp[i]=++cnt;
        int coun=0;
        bool flag = 1;   ///每一趟都必须有删掉的，否则永远不会再删掉了
        while(coun<n&&flag)
        {
            flag=0;
            for(int i=0; i<2*n; i++)
            {
                if (vis[i]) continue;
                int j;
                for(j=i+1; j<2*n; j++)
                {
                    if(vis[j]) continue;
                    if(abs(s[i]-s[j])!=32)  break;
                    flag=1 , vis[i]=vis[j]=1 , add(i,j) , coun++;
                    break;
                }
                i=j-1;
            }
        }
        if (coun!=n)
            printf("Impossible
");
        else
        {
            for(int i=0,cnt=1; i<2*n; i++)
                if(s[i]>='A' && s[i]<='Z')
                    printf("%d%c", ans[i], cnt==n? '
' : ' '),cnt++;
        }
    }
    return 0;
}