A
记得以前做过 当时好像没做对 就是找个子串 满足括号的匹配 []最多的
开两个栈模拟 标记下就行
1 #include <iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #include<stack> 10 using namespace std; 11 #define N 100010 12 char s[N]; 13 char st[N]; 14 int sn[N][3]; 15 int main() 16 { 17 int i,k,top=0; 18 cin>>s; 19 k = strlen(s); 20 sn[0][0] = -1;sn[0][2] = -1; 21 for(i = 0 ;i < k ;i++) 22 { 23 if(s[i]==‘(‘||s[i]==‘[‘) 24 { 25 st[++top] = s[i]; 26 sn[top][0] = i; 27 sn[top][1] = 0; 28 sn[top][2] = i; 29 } 30 else 31 { 32 if(s[i]==‘)‘) 33 { 34 if(top&&st[top]==‘(‘) 35 { 36 top--; 37 sn[top][1] += sn[top+1][1]; 38 sn[top][2] = i; 39 } 40 else 41 { 42 st[++top] = s[i]; 43 sn[top][0] = i; 44 sn[top][1] = 0; 45 sn[top][2] = i; 46 } 47 } 48 else 49 { 50 if(top&&st[top]==‘[‘) 51 { 52 top--; 53 sn[top][1] += sn[top+1][1]+1; 54 sn[top][2] = i; 55 } 56 else 57 { 58 st[++top] = s[i]; 59 sn[top][0] = i; 60 sn[top][1] = 0; 61 sn[top][2] = i; 62 } 63 } 64 } 65 } 66 int maxz=0,x=0; 67 for(i = 0 ; i <= top ; i++) 68 { 69 if(maxz<sn[i][1]) 70 { 71 maxz = sn[i][1]; 72 x = i; 73 } 74 } 75 cout<<maxz<<endl; 76 for(i = sn[x][0]+1 ; i <= sn[x][2] ; i++) 77 cout<<s[i]; 78 puts(""); 79 return 0; 80 }
B
这题。。描述的很抽象。 按我的话来说 就是对于每一个s[i]总能找到一个子串包含它 而且与t串相等 t串还必须包含了s串的所有字母
做法：开个标记数组 标记每个字母向前以及向后最大的匹配位置 是否大于等于t串的长度
1 #include <iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<stdlib.h> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #include<stack> 10 using namespace std; 11 #define N 200010 12 char s[N],t[N]; 13 int o[N],f[27],w[N]; 14 int main() 15 { 16 int i,j,k,tk; 17 while(cin>>s) 18 { 19 memset(o,0,sizeof(o)); 20 memset(w,0,sizeof(w)); 21 memset(f,0,sizeof(f)); 22 k = strlen(s); 23 cin>>t; 24 tk = strlen(t); 25 for(i = tk-1 ; i >= 0 ; i--) 26 { 27 f[t[i]-‘a‘] = 1; 28 } 29 for(i = k-1 ; i >= 0 ; i--) 30 { 31 if(!f[s[i]-‘a‘]) break; 32 } 33 if(i!=-1||s[0]!=t[0]) 34 { 35 puts("No"); 36 continue; 37 } 38 j = 0 ; 39 for(i = 0 ; i < k ;i++) 40 { 41 if(s[i]==t[j]) 42 { 43 j++; 44 o[i] = j; 45 f[s[i]-‘a‘] = j; 46 } 47 else 48 { 49 o[i] = f[s[i]-‘a‘]; 50 } 51 } 52 memset(f,0,sizeof(f)); 53 j = tk-1; 54 for(i = k-1 ; i >=0 ;i--) 55 { 56 if(s[i]==t[j]) 57 { 58 j--; 59 w[i] = tk-1-j; 60 f[s[i]-‘a‘] = tk-1-j; 61 } 62 else 63 { 64 w[i] = f[s[i]-‘a‘]; 65 } 66 } 67 for(i = 0 ; i < k ;i++) 68 { 69 if(o[i]+w[i]<=tk) break; 70 //cout<<o[i]<<" "<<w[i]<<endl; 71 } 72 if(i==k) 73 puts("Yes"); 74 else puts("No"); 75 } 76 return 0; 77 }
Codeforces Round #138 (Div. 1)
原文：http://www.cnblogs.com/shangyu/p/3564179.html
