字符串的展开

题意

根据 $p1,p2,p3$ 展开合法的字母或数字递增区间，处理大小写、重复次数和逆序规则。

思路

扫描到连字符时，先判断两侧是否同类且严格递增；不合法则保留 -。合法时枚举两端之间的字符，按 p1 改写、按 p2 重复，再按 p3 决定是否整体逆序。两端字符由普通扫描自然保留。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/*-----------------
* author: Rainboy
* email: rainboylvx@qq.com
* time: 2019年 07月 22日 星期一 12:24:19 GMT
* problem:  luogu-P1098
*----------------*/
#include <bits/stdc++.h>
using namespace std;

int p1,p2,p3;
char str[1000];
char tmp[500];
int idx = 0;


int main(){
    
    scanf("%d%d%d",&p1,&p2,&p3);
    scanf("%s",str+1);
    int len = strlen(str+1);
    int i,j,k;
    for (i=1;i<=len;i++){
        char c = str[i];
        if(c == '-'){
            if(!((str[i-1] >='a' && str[i+1]<='z') || (str[i-1] >='0' && str[i+1]<='9')) ){
                printf("-");
                continue;
            }
            if( str[i-1]  >= str[i+1]){
                printf("%c",c);
            }
            else if( str[i-1]  +1 == str[i+1])
                continue;
            else {
                idx = 0;
                memset(tmp,0,sizeof(tmp));
                for(j=str[i-1]+1 ;j<str[i+1];j++){
                    for (k=1;k<=p2;k++){
                        if( p1 == 1)
                            tmp[idx++] = tolower(j);
                        else if( p1 == 2)
                            tmp[idx++] = toupper(j);
                        else 
                            tmp[idx++] = '*';
                    }
                }
                if( p3 == 1) {
                    printf("%s",tmp);
                } else {
                    int l = strlen(tmp);
                    for(k=l-1;k>=0;k--){
                        printf("%c",tmp[k]);
                    }
                }
            }
        }
        else
            printf("%c",c);

    }
    return 0;
}

复杂度

总结

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28mode, repeat_count, direction = map(int, input().split())
text = input().strip()
answer = []

for index, character in enumerate(text):
    if character != "-" or index == 0 or index == len(text) - 1:
        answer.append(character)
        continue

    left, right = text[index - 1], text[index + 1]
    same_kind = (left.islower() and right.islower()) or (left.isdigit() and right.isdigit())
    if not same_kind or left >= right:
        answer.append("-")
        continue

    middle = []
    for code in range(ord(left) + 1, ord(right)):
        character_to_fill = chr(code)
        if mode == 2:
            character_to_fill = character_to_fill.upper()
        elif mode == 3:
            character_to_fill = "*"
        middle.append(character_to_fill * repeat_count)

    expanded = "".join(middle)
    answer.append(expanded if direction == 1 else expanded[::-1])

print("".join(answer))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62/*-----------------
* author: Rainboy
* email: rainboylvx@qq.com
* time: 2019年 07月 22日 星期一 12:24:19 GMT
* problem:  luogu-P1098
*----------------*/
#include <bits/stdc++.h>
using namespace std;

int p1,p2,p3;
char str[1000];
char tmp[500];
int idx = 0;


int main(){
    
    scanf("%d%d%d",&p1,&p2,&p3);
    scanf("%s",str+1);
    int len = strlen(str+1);
    int i,j,k;
    for (i=1;i<=len;i++){
        char c = str[i];
        if(c == '-'){
            if(!((str[i-1] >='a' && str[i+1]<='z') || (str[i-1] >='0' && str[i+1]<='9')) ){
                printf("-");
                continue;
            }
            if( str[i-1]  >= str[i+1]){
                printf("%c",c);
            }
            else if( str[i-1]  +1 == str[i+1])
                continue;
            else {
                idx = 0;
                memset(tmp,0,sizeof(tmp));
                for(j=str[i-1]+1 ;j<str[i+1];j++){
                    for (k=1;k<=p2;k++){
                        if( p1 == 1)
                            tmp[idx++] = tolower(j);
                        else if( p1 == 2)
                            tmp[idx++] = toupper(j);
                        else 
                            tmp[idx++] = '*';
                    }
                }
                if( p3 == 1) {
                    printf("%s",tmp);
                } else {
                    int l = strlen(tmp);
                    for(k=l-1;k>=0;k--){
                        printf("%c",tmp[k]);
                    }
                }
            }
        }
        else
            printf("%c",c);

    }
    return 0;
}

复杂度

设输出长度为 $L$ ，时间复杂度为 $O(L)$ ，额外空间复杂度为 $O(L)$ 。

总结

字符串展开题的难点在合法区间判定；把无效连字符先原样保留，可明显简化后续逻辑。

目录

题意

思路

代码

复杂度

总结

Python代码

C++代码

复杂度

总结