whust 2016 #1 H - Pair: normal and paranormal
题目链接
其实就是括号匹配的模型。。用栈即可。。被我写挂好几发。。该死该死。。。
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月07日 星期日 17时34分13秒 4File Name :code/whust2016/#1/HH.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10 11#include <algorithm> 12#include <vector> 13#include <queue> 14#include <stack> 15#include <set> 16#include <map> 17#include <string> 18#include <cmath> 19#include <cstdlib> 20#include <deque> 21#include <ctime> 22#include <cctype> 23#define fst first 24#define sec second 25#define lson l,m,rt<<1 26#define rson m+1,r,rt<<1|1 27#define ms(a,x) memset(a,x,sizeof(a)) 28typedef long long LL; 29#define pi pair < int ,int > 30#define MP make_pair 31 32using namespace std; 33const double eps = 1E-8; 34const int dx4[4]={1,0,0,-1}; 35const int dy4[4]={0,-1,1,0}; 36const int inf = 0x3f3f3f3f; 37const int N=1E4+7; 38char st[N]; 39int s[N]; 40int n; 41int plow[N]; 42int pup[N]; 43int ans[N]; 44stack<int>stk; 45 46 47bool ok(int x, int y) 48{ 49 // cout<<"x:"<<x<<" y:"<<y<<endl; 50 if (plow[x]>0&&pup[y]>0) 51 { 52 ans[pup[y]] = plow[x]; 53 return true; 54 } 55 if (plow[y]>0&&pup[x]>0) 56 { 57 ans[pup[x]] = plow[y]; 58 return true; 59 } 60 return false; 61} 62int main() 63{ 64 #ifndef ONLINE_JUDGE 65 freopen("code/in.txt","r",stdin); 66 #endif 67 68 cin>>n>>st; 69 n*=2; 70 int cntA = 0 ; 71 int cnta = 0 ; 72 ms(pup,0); 73 ms(plow,0); 74 for ( int i = 0 ; i < n ; i++) 75 { 76 if (st[i]>='a'&&st[i]<='z') 77 { 78 cnta++; 79 plow[i] = cnta; 80 } 81 else 82 { 83 cntA++; 84 pup[i] = cntA; 85 } 86 } 87// for ( int i = 0 ; i < n ; i++) cout<<"plow[i]:"<<plow[i]<<" pup[i]:"<<pup[i]<<endl; 88 for ( int i = 0 ; i < n ; i++) 89 { 90 st[i] = toupper(st[i]); 91 } 92// cout<<"st:"<<st<<endl; 93 ms(ans,-1); 94 while (!stk.empty()) stk.pop(); 95 stk.push(0); 96 for ( int i = 1 ; i < n ; i++) 97 { 98 while (!stk.empty()&&st[stk.top()]==st[i]&&ok(stk.top(),i)&&i<n) 99 { 100 stk.pop(); 101 i++; 102 } 103 stk.push(i); 104 } 105 for ( int i = 1 ; i <= n/2 ; i++) 106 { 107 if (ans[i]==-1) 108 { 109 puts("Impossible"); 110 return 0; 111 } 112 } 113 for ( int i = 1 ; i < n/2 ; i++) printf("%d ",ans[i]); 114 printf("%d\n",ans[n/2]); 115 116 #ifndef ONLINE_JUDGE 117 fclose(stdin); 118 #endif 119 return 0; 120}