csuoj 1328:近似回文語
22216 ワード
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1328
1328:近似回文語Time Limit:1 Sec Memory Limit:128 MB
Description
1行のテキストを入力し、最長近似文語連続サブ列を出力します.近似回文語とは、以下の条件を満たす文字列を指す.
1.Sはアルファベットで始まり、アルファベットで終わる
2.a(S)とb(S)は最大2 kの位置が異なり、ここでa(S)はSがすべての非アルファベット文字を削除し、すべてのアルファベットを小文字に変換した列であり、b(S)はa(S)の逆シーケンス列である.
例えばk=1の場合、Race catはa(S)=racecaとb(S)=tacecarが2つの位置しか異なるため、近似的な回文語である.
Input
入力には25を超えないデータが含まれ、各データには2行が含まれます.1行目は整数k(0<=k<=200)であり、2行目の文字列Sは、少なくとも1文字のアルファベットを含むが1000文字を超えない(改行はカウントされない).Sは、文字、スペース、その他の印刷可能な文字(カンマ、ピリオドなど)のみを含み、空白文字で始まることはありません.
Output
各試験データのセットについて、最長近似回文サブ列の長さと開始位置が出力される(Sの最初の文字は位置1).最長近似文のサブシリアル解が複数ある場合は、開始位置をできるだけ小さくする必要があります.
Sample Input
Sample Output
HINT
Source
湖南省第9回大学生コンピュータプログラム設計コンテスト
分析:
暴力シミュレーション(TLEがあると言われていますが、私はACです.RPでしょう)でいいです.ある点から両側に別々に比較することもできます.
ACコード:
View Code
これは両側に拡張して書いたもので、タイムアウトは存在しません!!!
View Code
1328:近似回文語Time Limit:1 Sec Memory Limit:128 MB
Description
1行のテキストを入力し、最長近似文語連続サブ列を出力します.近似回文語とは、以下の条件を満たす文字列を指す.
1.Sはアルファベットで始まり、アルファベットで終わる
2.a(S)とb(S)は最大2 kの位置が異なり、ここでa(S)はSがすべての非アルファベット文字を削除し、すべてのアルファベットを小文字に変換した列であり、b(S)はa(S)の逆シーケンス列である.
例えばk=1の場合、Race catはa(S)=racecaとb(S)=tacecarが2つの位置しか異なるため、近似的な回文語である.
Input
入力には25を超えないデータが含まれ、各データには2行が含まれます.1行目は整数k(0<=k<=200)であり、2行目の文字列Sは、少なくとも1文字のアルファベットを含むが1000文字を超えない(改行はカウントされない).Sは、文字、スペース、その他の印刷可能な文字(カンマ、ピリオドなど)のみを含み、空白文字で始まることはありません.
Output
各試験データのセットについて、最長近似回文サブ列の長さと開始位置が出力される(Sの最初の文字は位置1).最長近似文のサブシリアル解が複数ある場合は、開始位置をできるだけ小さくする必要があります.
Sample Input
1
Wow, it is a Race cat!
0
abcdefg
0
Kitty: Madam, I'm adam.
Sample Output
Case 1: 8 3
Case 2: 1 1
Case 3: 15 8
HINT
Source
湖南省第9回大学生コンピュータプログラム設計コンテスト
分析:
暴力シミュレーション(TLEがあると言われていますが、私はACです.RPでしょう)でいいです.ある点から両側に別々に比較することもできます.
ACコード:
1 #include <stdio.h>
2 #include <algorithm>
3 #include <iostream>
4 #include <string.h>
5 #include <string>
6 #include <math.h>
7 #include <stdlib.h>
8 #include <queue>
9 #include <stack>
10 #include <set>
11 #include <map>
12 #include <list>
13 #include <iomanip>
14 #include <vector>
15 #pragma comment(linker, "/STACK:1024000000,1024000000")
16 #pragma warning(disable:4786)
17
18 using namespace std;
19
20 const int INF = 0x3f3f3f3f;
21 const int MAX = 2000 + 10;
22 const double eps = 1e-8;
23 const double PI = acos(-1.0);
24
25 char str[MAX] , hw[MAX];
26 int chang[MAX];
27 int k;
28
29 int main()
30 {
31 int cas = 1;
32 while(~scanf("%d",&k))
33 {
34 getchar();
35 gets(str);
36 int len = strlen(str);
37 int cnt = 0;
38 for(int i = 0 ;i < len;i ++)
39 {
40 if((str[i] >= 'A' && str[i] <= 'Z') || (str[i] >= 'a' && str[i] <= 'z'))
41 {
42 char c = str[i];
43 if(c >= 'A' && c <= 'Z')
44 c = c - 'A' + 'a';
45 chang[cnt] = i;
46 hw[cnt ++] = c;
47 }
48 }
49 hw[cnt] = '\0';
50 int maxlen = 1 , pos = 1;
51 for(int j = cnt;j >= 1;j --)
52 for(int i = 0;i + j - 1 < cnt;i ++)
53 {
54 int st = i + j - 1,cnt = 0;
55 int len = chang[st] - chang[i] + 1;
56 if(len < maxlen)
57 continue;
58 for(int l1 = i,l2 = st;l1 < l2;l1 ++ , l2 --)
59 {
60 if(hw[l1] != hw[l2])
61 cnt += 2;
62 if(cnt > 2 * k)
63 break;
64 }
65 if(cnt <= 2 * k)
66 {
67 if(maxlen < len || (maxlen == len && i < pos))
68 {
69 maxlen = len;
70 pos = i;
71 }
72 }
73 }
74 printf("Case %d: %d %d
",cas ++ , maxlen , chang[pos] + 1);
75 }
76 return 0;
77 }
View Code
これは両側に拡張して書いたもので、タイムアウトは存在しません!!!
1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cstring>
5 #include<queue>
6 #include<string>
7 #include<cmath>
8 #include<cctype>
9 using namespace std;
10 char s[1010],s1[1010];
11 int ans[1010];
12 int main()
13 {
14 int T=1,k,i,j;
15 while(~scanf("%d",&k))
16 {
17 int a = 0,kk=0,start = 0,flag;
18 getchar();
19 gets(s);
20 int len = strlen(s);
21 for( i=0;i<len;i++)
22 {
23 if(isalpha(s[i])) //
24 {
25 ans[kk] = i;
26 s1[kk] = toupper(s[i]);//
27 kk++;
28 }
29 }
30 for( i=0; i<kk; i++)
31 {
32 flag = 0;
33 for( j=0;i-j>=0 && i+j<kk; j++)// ;
34 {
35 if(s1[i-j]!=s1[i+j])
36 flag++;
37 if(flag>k)
38 break;
39 }
40 j--;
41 if(ans[i+j]-ans[i-j]+1>a)
42 {
43 a = ans[i+j]-ans[i-j]+1;
44 start = ans[i-j];
45 }
46 flag = 0;
47 for( j=0; i-j>=0 && i+j+1<kk; j++)//
48 {
49 if(s1[i-j]!=s1[i+j+1])
50 flag ++;
51 if(flag>k)
52 break;
53 }
54 j--;
55 if(j<=-1)
56 continue;
57 if(ans[i+j+1]-ans[i-j]+1>a)
58 {
59 a = ans[i+j+1]-ans[i-j]+1;
60 start = ans[i-j];
61 }
62 }
63 printf("Case %d: %d %d
",T++,a,start+1);
64 }
65 return 0;
66 }
View Code