首页 > 其他 > 详细

Codeforces Round #138 (Div. 1)

时间:2014-02-25 08:46:14      阅读:363      评论:0      收藏:0      [点我收藏+]

A

记得以前做过 当时好像没做对 就是找个子串 满足括号的匹配 []最多的

开两个栈模拟 标记下就行

bubuko.com,布布扣
 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 }
View Code

这题。。描述的很抽象。 按我的话来说 就是对于每一个s[i]总能找到一个子串包含它 而且与t串相等 t串还必须包含了s串的所有字母

做法:开个标记数组 标记每个字母向前以及向后最大的匹配位置 是否大于等于t串的长度

bubuko.com,布布扣
 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 }
View Code

Codeforces Round #138 (Div. 1)

原文:http://www.cnblogs.com/shangyu/p/3564179.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!