3、算法练习专栏——牛客练习——天梯备赛练习01

题目A：大雄的糖果

链接

众所周知，哆啦A梦的口袋无奇不有，嘴馋的大雄想要哆啦A梦从口袋里拿点糖果出来吃。

可是哆啦A梦不想大雄轻易的得到糖果，所以从口袋里拿出了三堆卡片，数量分别是a,b,c。

每次允许大雄从其中的两堆中各拿走1张卡片(两堆的卡片不能为空)，大雄即可得到一颗糖果，然后大雄可以继续执行上面操作，直至不能执行操作为止。

大雄想要知道能够得到最多的糖果是多少？聪明的你能帮帮他吗?

输入描述:

$$
输入包括三个正整数a,b,c，分别是三堆卡片的数量。\
(1≤a,b,c≤105)
$$

输出描述:

1
输出大雄能够得到的最多糖果数。

示例1

输入

复制

1
2 4 6

输出

复制

1
6

示例2

输入

复制

1
4 4 6

输出

复制

1
7

代码(可简化)

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>

using namespace std;
int ans;

int main()
{
    int a, b ,c, Max = 0;
    cin >> a >> b >> c;
    
    if (a > b) {
        swap(a, b);
    } else if (a > c) {
        swap(a, c);
    } else if (b > c) {
        swap(b, c);
    } 
    
    while (c && a && b) {
        if (a > b) a--;
        else b--;
        c--;
        ans ++;
    }
    if (c == 0) ans += min(a, b); 
    else if (a == 0) ans += min(b, c);
    else ans += min(a, c);
    
    cout << ans;
    return 0;
}

题目B：最长回文子串

链接

既然大家都知道回文串是怎么回事了，那我们就长话短说，现在有一个字符串，长度小于1200，我想知道最长的回文子串长度是多少。

输入描述:

1
多组输入，输入字符串只包含小写字母。

输出描述:

1
每组输出一个数字，表示最长的回文子串。

示例1

输入

复制

1
2
aqppqole
ebcml

输出

复制

1
2
4
1

代码一：暴力写法1（O（n^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
29
30
31
32
#include <iostream>
#include <algorithm>

using namespace std;

bool check(string s,int i, int j) {
    string ss = s;
    while (i <= j) {
        if (s[i++] != s[j--]) return false;
    }
    
    return true;
}

int main(){
    string s;
    while (cin >> s) {
        int ans = 1;
        int len = s.length();
        if (len == 1) {
            cout << "1\n";
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (check(s, i, j)) ans = max(ans, j - i + 1);
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}

代码二：中心扩散（O(n^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
33
34
#include <iostream>
#include <algorithm>

using namespace std;

int calc(string s,int l, int r) {
    int count = 0;
    int len = s.size();
    while (l >= 0 && r < len && s[l] == s[r]) {
        l--;
        r++;
    }
    return r - l - 1;
}

int main(){
    string s;
    while (cin >> s) {
        int len = s.length(), Max = 0;
        if (len <= 1) {
            cout << len << '\n';
            continue;
        }
        for (int i = 0; i < len; i++) {
            int ans, res;
            ans = calc(s, i, i);  
            res = calc(s, i, i + 1);
            Max = max(Max, max(res, ans));
        }
        cout << Max << '\n';
    }
    
    return 0;
}

代码三：二分+哈希（O(nlogn)）亲自讲解

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
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2010;
const int base=131;
ull hr[2*N],hl[2*N],p[2*N];//超过ull自动取余
char s[N * 2];
ull get_hash(ull h[],int l,int r)//获取某段长度字符串的hash值
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int t=1;
    while(~scanf("%s",s+1))
    {
        int res=0;
        int n=strlen(s+1);
        for(int i=2*n;i>0;i-=2)
        {
            s[i]=s[i/2];
            s[i-1]='z'+1;//添加#(未出现字符)
        }
        n *= 2,p[0]=1;
        for(int i=1,j=n;i<=n;i++,j--)
        {
            hl[i]=hl[i-1]*base+s[i]-'a'+1;//处理hash值
            hr[i]=hr[i-1]*base+s[j]-'a'+1;
            p[i]=p[i-1]*base;
        }
        
        for(int i=1;i<n;i++)
        {
            int l=0,r=min(i-1,n-i),mid;//二分寻找以str[i]为中心的最长回文子串的长度
            while(r>l)
            {
                mid=l+r+1>>1;
                if(get_hash(hl,i-mid,i-1)==get_hash(hr,n-(mid+i)+1,n-(i+1)+1))
                    l=mid;
                else r=mid-1;
            }
            if(s[i-l]=='z'+1)
               res=max(res,l);
            else res=max(res,l+1);
        }
        
        printf("%d\n", res);
    }
    return 0;
}

代码四：Manacher算法（O（n）进阶知识）亲自讲解

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
const int N = 3010;
string s;
char b[N];
int p[N];
int n, idx, len;

void init() {
    b[idx++] = '$';
    b[idx++] = '#';
    for (int i = 0; i < len; i++) {
        b[idx++] = s[i];
        b[idx++] = '#'; 
    }
    b[idx] = '^';
    n = idx;
}

void manacher() {
    int MaxR = 0, mid;
    for (int i = 0; i < n; ++i){
        if (i < MaxR) {
            p[i] = min(p[2 * mid - i], MaxR - i);
        } else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i]++;
        if (i + p[i] > MaxR) 
        {
            MaxR = i + p[i];
            mid = i;
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    while (cin >> s){
        memset(p, 0, sizeof p);
        int ans = 0;
        len = s.length();
        idx = 0;
        init();    
        manacher();
        for (int i = 0; i < n; i++) {
            ans = max(ans, p[i]);        
        }
        cout << ans - 1 << '\n';
    }
    
    return 0;
}

题目C：杨辉三角

链接

题目描述

杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

下面给出了杨辉三角形的前4行：

​ 1

​ 1 1

​ 1 2 1

1 3 3 1

给出n，输出它的前n行。

输入描述:

1
输入包含一个数n。

输出描述:

1
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面和后面输出多余的空格。

示例1

输入

复制

1
4

输出

复制

1
2
3
4
1
1 1
1 2 1
1 3 3 1

说明

1
1 <= n <= 34。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 40;
int a[N][N];
int n;
int main()
{
    int n;
    cin >> n;
    a[1][1] = 1;
    cout << a[1][1] << '\n';
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            cout << a[i][j] << " ";
        }
        puts("");
    }
    

    return 0;
}

題目D：打印质数

链接

输入一个自然数N，按质数定义从小到大输出1~N（包含N）中所有的质数

输入描述:

1
2
3
输入一行，包含一个整数N

1 <= N <= 2000

输出描述:

1
输出一行，包含所有的质数，按照从小到大的顺序输出，以空格隔开。

示例1

输入

复制

1
20

输出

复制

1
2 3 5 7 11 13 17 19

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;
int n;

bool check(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if(check(i)) {
            cout << i << " ";
        }
    }
    
    return 0;
}

题目E：扫雷

链接

题目描述

小sun上课的时候非常喜欢玩扫雷。他现小sun有一个初始的雷矩阵，他希望你帮他生成一个扫雷矩阵。

​

扫雷矩阵的每一行每一列都是一个数字，每个数字的含义是与当前位置相邻的8个方向中，有多少个雷（在下图中，雷用表示）；如果当前位置就是雷的话，仍输出一个。

比如初始的雷矩阵如下： 

1
2
3
4
....  
..**  
*.*.  
.*.*

对应的数字矩阵为： 

1
2
3
4
0122   
13**   
*4*4   
2*3*

输入描述:

1
2
3
第一行两个整数n,m，代表矩阵有n行m列

接下来共n行，每行m个字符

输出描述:

1
输出共n行m列，为扫雷矩阵。

示例1

输入

复制

1
2
3
4
5
4 4
....
..**
*.*.
.*.*

输出

复制

1
2
3
4
0122
13**
*4*4
2*3*

示例2

输入

复制

1
2
3
4
3 4
....
*..*
.*.*

输出

复制

1
2
3
1111
*23*
2*3*

备注:

1
2
数据范围：
1≤n,m≤10001 \leq n,m\leq 10001≤n,m≤1000

代码

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
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, count;
char a[N][N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {    
        getchar();
        for(int j=1;j<=m;j++)
            scanf("%c",&a[i][j]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='*')
                printf("*");
            else
            {
                for(int p=i-1;p<i+2;p++)
                {
                for(int q=j-1;q<j+2;q++)
                {
                    if(a[p][q]=='*')
                        count++;
                }
                }
                printf("%d",count);
                count=0;}
        }
        printf("\n");
    }
    return 0;
}

题目F：求距离

链接

给你一个1 -> n的排列，现在有一次机会可以交换两个数的位置，求交换后最小值和最大值之间的最大距离是多少？

输入描述:

1
2
第一行一个数n
之后一行n个数表示这个排列

输出描述:

1
输出一行一个数表示答案

示例1

输入

复制

1
2
5
4 5 1 3 2

输出

复制

1
3

说明

1
2
3
4
把1和2交换后
序列为4 5 2 3 1
最大值5在数组的2位置，最小值1在数组的5位置
距离为3

备注:

1
对于100%的数据，1 <= n <= 100

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

using namespace std;
int a, b, ans;
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) a = i;
        else if (x == n) b = i;
    }
    ans = max(ans, max(a - 1, n - a));
    ans = max(ans, max(b - 1, n - b));
    cout << ans;
    return 0;
}

题目G：约瑟夫环

链接

题目描述

n个人（0,1,2,3,4…n-1），围成一圈，从编号为k的人开始报数，报数报到m的人出队（报数是1,2,…m这样报的）。下次从出队的人之后开始重新报数，循环往复，当队伍中只剩最后一个人的时候，那个人就是大王。现在，给定n，k，m，
请你求出大王的编号。

输入描述:

1
2
3
输入一行包含三个整数n,k,m

1<=n<=100,1<=k<=n-1,1<=m<=100

输出描述:

1
输出一个整数

示例1

输入

复制

1
5 1 2

输出

复制

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 <algorithm>

using namespace std;
const int N = 1010;
int n, k, m;
int a[N];

int main()
{
    cin >> n >> k >> m;
    
    for(int i = 0 ;i < n; i++){
        a[i] = i + 1;
    }
    while(n > 1){
        k=(k + m - 1)%n;
        for(int i=k + 1;i < n; i++){
            a[i - 1] =a [i];
        }
        n--;
        if(k == n){
            k = 0;
        }
    }
    cout<< a[k] - 1 << endl;
    return 0;
}

题目H：简写单词

链接

规定一种对于复合词的简写方式为只保留每个组成单词的首字母，并将首字母大写后再连接在一起

比如 “College English Test”可以简写成“CET”，“Computer Science”可以简写为“CS”，“I am Bob”简写为“IAB”

输入一个长复合词（组成单词数 sum,sum≥1且sum≤100sum,sum\geq1且sum\leq100sum,sum≥1且sum≤100,每个单词长度len,len≥1且len≤50），请你输出它的简写

输入描述:

1
输入一个复合词

输出描述:

1
输出一行，表示复合词的简写

示例1

输入

复制

1
College English Test

输出

复制

1
CET

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
string word;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string s;
    while (cin >> s) {
        word += toupper(s[0]);
    }
    
    cout << word;
    return 0;
}

题目I：统计单词数

链接

题目描述

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。
现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章
中的某一独立单词在不区分大小写的情况下完全相同（参见样例1 ），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2 ）

输入描述:

1
2
3
共 2 行。
第 1 行为一个字符串，其中只含字母，表示给定单词；
第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章

输出描述:

1
一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 0 开始）；如果单词在文章中没有出现，则直接输出一个整数 -1。

示例1

输入

复制

1
2
To
to be or not to be is a question

输出

复制

1
2 0

说明

1
输出结果表示给定的单词 To 在文章中出现两次，第一次出现的位置为0。

示例2

输入

复制

1
2
to
Did the Ottoman Empire lose its power at that time

输出

复制

1
-1

说明

1
表示给定的单词 to 在文章中没有出现，输出整数-1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,f;
    int ans = 0 ,a = 0;
    getline(cin,f);
    getline(cin,s);
    for(int i = 0;i<f.length();i++) f[i]=tolower(f[i]);
    for(int i = 0;i<s.length();i++) s[i]=tolower(s[i]);
    s=' '+s+' ';
    f=' '+f+' ';
    while(s.find(f, a) != -1)
    {
        a=s.find(f,a) + f.length()-1;
        ans++;
    }
    if(ans) cout<< ans << " " <<s.find(f);
    else cout<<-1;
}

题目J：乘法表打印

链接

题目描述

输出九九乘法表，输出格式见样例。

输入描述:

1
此题没有输入

输出描述:

1
输出乘法表，对齐方式见样例输出

示例1

输入

复制

1
无

输出

复制

1
2
3
4
5
6
7
8
9
1*1= 1
1*2= 2 2*2= 4
1*3= 3 2*3= 6 3*3= 9
1*4= 4 2*4= 8 3*4=12 4*4=16
1*5= 5 2*5=10 3*5=15 4*5=20 5*5=25
1*6= 6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36
1*7= 7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49
1*8= 8 2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64
1*9= 9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int n;

int main()
{
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= i; j++) {
            printf("%d*%d=%2d ", j, i, i * j);           
        }
        puts("");
    }

    return 0;
}

题目K：疫情死亡率

链接

题目描述

请根据各国报告的疫情确诊数和死亡数，计算新冠疫情在各国的死亡率。

输入描述:

1
输入仅一行，有两个整数（范围1 ~2^31-1），第一个为确诊数，第二个为死亡数。

输出描述:

1
输出仅一行，甲流死亡率，以百分数形式输出，精确到小数点后3位。

示例1

输入

复制

1
10433 280

输出

复制

1
2.684%

代码

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    double c = 1.0 * b / a * 100;
    printf("%.3lf%%",c);
}

题目L：反向输出一个四位数

链接

题目描述

将一个四位数，反向输出。

输入描述:

1
一行，输入一个整数n（1000 <= n <= 9999）。

输出描述:

1
针对每组输入，反向输出对应四位数。

示例1

输入

复制

1
1234

输出

复制

1
4321

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <algorithm>

using namespace std;
int main()
{
    string s;
    cin >> s;
    reverse(s.begin(),s.end());
    
    cout << s;    
    
    return 0;
}

题目M：珂朵莉的假动态仙人掌

链接

珂朵莉想每天都给威廉送礼物，于是她准备了n个自己的本子

她想送最多的天数，使得每天至少送一个本子，但是相邻两天送的本子个数不能相同

珂朵莉最多送几天礼物呢

输入描述:

1
第一行一个整数n

输出描述:

1
第一行输出一个整数，表示答案

示例1

输入

复制

1
4

输出

复制

1
3

说明

1
2
3
第一天送1个本子
第二天送2个本子
第三天送1个本子

备注:

1
对于100%的数据，有1 <= n <= 1000000000

代码

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;
int main()
{
    int n, k;
    cin >> n;
    if (n % 3 == 0) k = n / 3 * 2;
    else k = n / 3 * 2 + 1;
    cout << k;
}

题目N：爱因斯坦的名言

链接

题目描述

初出茅庐的小伙伴们，你们对编程了解多少？希望你们记住爱因斯坦的这句名言，好好学习，天天向上。

img

输入描述:

1
无

输出描述:

1
2
输出下面这句话：
"Genius is 1% inspiration and 99% perspiration."

代码

1
2
3
4
5
6
#include <iostream>
using namespace std;
int main()
{
    cout << "\"Genius is 1% inspiration and 99% perspiration.\"";
}