4、算法练习专栏——牛客练习——牛客周赛Round34

题目A：小红的字符串生成

链接

题目描述

小红拿到了两个字符，请你输出这两个字符可以生成的所有字符串。按任意顺序输出均可。

输入描述:

1
两个小写字母，用空格隔开。

输出描述:

1
2
第一行输出一个正整数nnn，代表可以生成的不同字符串数量。
接下来的nnn行，每行输出一个仅由小写字母组成的字符串。

示例1

输入

复制

1
a b

输出

复制

1
2
3
4
5
4
a
ba
ab
b

示例2

输入

复制

1
d d

输出

复制

1
2
3
2
d
dd

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main()
{
    string a, b;
    cin >> a >> b;
    if (a == b) {
        cout << "2" << '\n';
        cout << a << '\n';
        cout << a + a << '\n';
    } else {
        cout << "4" << '\n';
        cout << a << '\n';
        cout << b << '\n';
        cout << a + b << '\n';
        cout << b + a << '\n';
    }
    return 0;
}

题目B：小红的非排列构造

链接

题目描述

小红拿到了一个数组，她修改尽可能少的元素使其变成 非排列 。你能帮帮她吗？
定义排列为一个长度为nnn的数组，其中1到nnn每个元素恰好出现一次。

输入描述:

$$
第一行输入一个正整数n，代表数组的大小。\
第二行输入n个正整数a_i，用空格隔开。代表数组的元素。\
1≤n≤10^5\
1≤a_i≤10^9
$$

输出描述:

$$
首先输出一个整数m，代表操作次数。\
接下来的m行，每行输出两个正整数i,x_i，用空格隔开，代表将第i个元素修改为x。\
有多种合法方案时，输出任意一种均可。\
请注意，输入的i,x必须满足1 <= i <= n且1 <= x <= 10^9
$$

示例1

输入

复制

1
2
4
1 2 3 1

输出

复制

1
0

说明

1
不需要修改，其本身就不是排列。

​ 示例2

输入

复制

1
2
3
1 2 3

输出

复制

1
2
1
1 3

代码

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
#include <iostream>
#include <unordered_map>

using namespace std;
unordered_map<int, int> Map;

int main()
{
    int n, m = 0, a, b, flag = 1;
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        int x;
        cin >> x;
        Map[x] ++;
        if (Map[x] > 1 || x > n) {
            cout << "0";
            flag = 0;
            break;
        } else {
            a = i;
            b = n + 1;
        }
    }
    if (flag) cout << "1\n" << a << " " << b;
    
    return 0;
}

题目C：小红的数字拆解

链接

题目描述

小红拿到了一个偶数，她希望你将其切割成尽可能多的偶数。你能帮帮她吗？

输入描述:

$$
一个偶数x。\
1≤x≤10^5
$$

输出描述:

1
输出若干行，从小到大输出每个偶数。

示例1

输入

复制

1
1024

输出

复制

1
2
3
2
4
10

说明

1
拆分成"10"+"2"+"4"三个偶数。

示例2

输入

复制

1
999999999999999999999999990

输出

复制

1
999999999999999999999999990

示例3

输入

复制

1
202020

输出

复制

1
2
3
4
5
6
0
0
0
2
2
2

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, k;
string s;
string a[N];
bool cmp(string x,string y) {
    if (x.length() != y.length()) return x.length() < y.length();
    else return x < y;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> s;
    int len = s.length();
    if ((s[len - 1] - '0') % 2 == 0) {
        for (int i = 0; i < len;) {
            string ss;
            while ((s[i++] - '0') % 2 == 1) {
                ss += s[i - 1];
            }            
            ss += s[i - 1];
            a[k++] = ss;
        }
    }  
    sort(a, a + k, cmp);
    for (int i = 0; i < k; i++) cout << a[i] << '\n';
    return 0;
}

题目D：

链接

题目描述

小红定义一个数组的陡峭值为相邻两数差的绝对值之和。
现在小红拿到了一个长度为nnn的、仅由正整数组成的数组，但她有一些元素看不清了，只记得数组的陡峭值恰好等于 1。
小红希望你能还原整个数组，你能帮帮她吗？

输入描述:

$$
第一行输入一个正整数n，代表数组的大小。\
第二行输入n个整数a_i，其中如果a_i为 0 代表小红看不清该元素，大于 0 代表能看清该元素。\
2≤n≤105\
0≤a_i≤10^9
$$

输出描述:

1
2
3
如果无解，请输出 -1。
否则输出n个正整数，用空格隔开，代表小红还原的数组。
有多解时输出任意即可。

示例1

输入

复制

1
2
4
9 0 0 8

输出

复制

1
9 9 9 8

示例2

输入

复制

1
2
3
0 1 0

输出

复制

1
1 1 2

示例3

输入

复制

1
2
5
0 1 2 1 0

输出

复制

1
-1

代码

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
#include <iostream>
#include <cmath>

using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    if (n == 1) {
        cout << "-1";
        return 0;
    }
    int flag = 0;
    for (int i = 1, t; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 0) {
            if (i == 1) flag = 1;
            else if (i == n) flag = 2;
            a[i] = a[i - 1];
        }
    }
    if (a[n] == 0) a[n] = 5;
    for (int i = n; i >= 1; i--) {
        if (a[i] == 0) a[i] = a[i + 1];
    }
    int To = 0;
    for (int i = 2; i <= n; i++){
        To += abs(a[i] - a[i - 1]);
    }
    if (To == 0 && flag) {
        if (flag == 1) a[1] = (a[2] == 1)?2 : a[2] - 1;
        else if (flag == 2) a[n] = (a[n - 1] == 1 ? 2 : a[n - 1] - 1);
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
    }
    else if (To == 1) {
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
    }
    else cout << "-1";
    return 0;
}