7.26-STOIRegularMatch-08-#14

A-3 SRM 08

描述

给一个 01 串设为其 S，询问是否存在只出现两次的 01 串 T。

这里的出现定义为存在一串下标 $a_1,a_2,...,a_m$ ，满足 $a_1<a_2<...<a_m$ 且 $S_{a_i}=T_i$ 。

输入格式

一行，一个 01 串

输出格式

一行，字母 Y 表示存在，N 表示不存在

样例输入 1

样例输出 1

样例输入 2

样例输出 2

数据范围与约定

设串 S 的长度为 n， $2\leq n\leq 5000$
数据为随机生成

样例解释

第一个样例中，"000"出现了一次（[1+2+3]），"00"出现了三次（[1+2],[2+3],[1+3]），"0"出现了三次（[1],[2],[3]）

第二个样例中，"0"出现了两次。

-------------

条件中 $S_{a_i}=T_i$ 用来保证T为S子串。

在A-1中，n的长度为2≤n≤3，打表就好了，想怎么打怎么打。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 char s[4];
 6 bool ans;
 7 int main()
 8 {
 9     int n;
10     scanf("%s",s);
11     n=strlen(s);
12     if (n==2) {
13         if (s[1]==s[0]) ans=1; else ans=0;
14     } else {
15         if (s[1]==s[2] && s[2]==s[0]) ans=0;
16         else ans=1;
17     }
18     if (ans==1) printf("Y\n"); else printf("N\n");
19     return 0;
20 }

A-1

A-2数据不大，可以直接用dfs水过。

写法请教过nbc姐姐>_<

f[i][j]代表t的前i位在s的前j位中出现的次数。

如果s的第j位作为t的第i位，那就是f[i-1][j-1]，不过得保证s[j]=t[i]。

如果s的第j位不用作t的第i位，那就转移到了f[i][j-1]。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 using namespace std;
 6 char __input[12];
 7 int N,S[11],T[11],f[11][11];
 8 void Check (int M)
 9 {
10     for (int i=0; i<=N; i++) f[0][i]=1;
11     for (int i=1; i<=M; i++) {
12         f[i][0]=0;
13         for (int j=1; j<=N; j++) {
14             f[i][j]=f[i][j-1];
15             if (T[i]==S[j]) f[i][j]+=f[i-1][j-1];
16         }
17     }
18     if (f[M][N]==2) {
19         printf("Y\n");
20         exit(0);
21     }
22 }
23 void DFS(int k)
24 {
25     Check(k);
26     if (k<N) {
27         T[k+1]=0;
28         DFS(k+1);
29         T[k+1]=1;
30         DFS(k+1);
31     }
32 }
33 int main()
34 {
35     scanf("%s",__input+1);
36     while (__input[N+1]) N++;
37     for (int i=1; i<=N; i++) S[i]=__input[i]-'0';
38     DFS(0);
39     printf("N\n");
40     return 0;
41 }

A-2

A-3我们可以简单地分情况处理。小于等于3的情况我们可以直接吧A-1的表弄过来。当n大于3时，需要分情况。

1.如1001 110000 10100000这样的情况，都属于只有两个1或2个0的情况，这种是一定成立的。

2.第二种情况。如00111101010101 100101010101这样的情况，有两个0或两个1靠在一起，也是一定成立。

如第一个串00111101010101，可以取下标为a[1],a[3-n]的数作为子串1，a[2],a[3-n]的数作为子串2，可以证明当两个0或两个1靠在一起时是成立的。

3.第三点。如11101 1010000111，这两个串都有相邻的0或1，但却是不成立的。因为相邻的数个数大于等于3，如第一个串，我们可以取下标a[1],a[4-n];a[2],a[4-n];a[3],a[4-n]三个子串，个数不为2.

综合起来就是，n大于3时，只要找相邻的0或1且保证这组相邻数连续个数等于2，结果就是Y。反之则为N。

（天呐我怎么讲话舌头打结…

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int x=0,y=0;
 6 int main()
 7 {
 8     bool ans;
 9     char s[5010];
10     scanf("%s",s);
11     int n=strlen(s);
12     if (n==2)
13       if (s[1]==s[0]) ans=1; else ans=0;
14     else if (n==3 && s[1]==s[2] && s[2]==s[0]) ans=0; else ans=1;
15     if (n==2 || n==3) {
16         if (ans==1) printf("Y\n"); else printf("N\n");
17         return 0;
18     }
19     for (int i=0; i<n; i++) if (s[i]=='0') x++; else y++;
20     if (x==2 || y==2) ans=1; else {
21         ans=0;
22         for (int i=0; i<n-1; i++) if (s[i-1]!=s[i] && s[i]==s[i+1] && s[i+1]!=s[i+2]) ans=1;
23     }
24     if (ans==1) printf("Y\n"); else printf("N\n");
25     return 0;
26 }

A-3

正解A-3代码

维修中_(:з」∠)_