URAL 2019Pair: normal and paranormal 暴力？

题目描述：

Description 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. Problem illustration 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 2 n 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 n lowercase letters and exactly n uppercase letters. Output If the problem has a solution, output n space-separated integers g 1, g 2, …, g n, where g i 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 g i must be pairwise different. If the problem has several solutions, output any of them. If the problem has no solution, output “Impossible”. Sample Input input

2 AbBa

output

2 1

input

2 AbaB

output

Impossible

input

1 Ab

output

Impossible

题目分析：

这题是真的难读懂，大概意思就是在一个半圆内，有2*n个点，其中有大写字母和小写字母。其中你需要连接大写字母到小写字母，其中需要保证这些连接的线段之间没有相交。如果能够实现，将大写字母对应的小写字母的序号按序输出。 其实可以将这个问题模型改成在一条直线上，合法的情况就属于线段之间没有相交，就是线段之间只有包含和不相关的情况。 找相邻的字母是配对的，然后将这两个字母标记之后继续找没有被标记的相邻字母，并将这两个配对的字母存在一个数组里。 最后将这些2*n的序号变成n的序号就可以。

代码如下：

#include <iostream> #include <cstdio> #include <cstring> const int maxn=10100; using namespace std; int n; char s[maxn]; bool vis[maxn]; int ans[maxn]; int ans2[maxn]; void add(int i,int j) { if(s[i]+32==s[j]) ans[i]=j; else ans[j]=i; } int main() { while(scanf("%d",&n)!=-1) { scanf("%s",s); memset(vis,0,sizeof(vis)); int count=0; while(1) { bool f=0; for(int i=0; i<2*n; i++) { if (vis[i]) continue; int j=i+1; while(j<2*n) { if (vis[j]) { j++; continue; } if ((s[i]-s[j]==32) || (s[j]-s[i]==32)) { f=1; vis[i]=vis[j]=1; add(i,j); count++; break; } else break; } i=j-1; } if (count==n || !f) break; } if (count!=n) { printf("Impossible\n"); continue; } int cnt=0; for(int i=0; i<2*n; i++) { if(s[i]>='a' && s[i]<='z') ans2[i]=++cnt; } cnt=0; for(int i=0; i<2*n; i++) { if(s[i]>='A' && s[i]<='Z') { cnt++; printf("%d%c", ans2[ans[i]], cnt==n?'\n':' '); } } } return 0; }