C语言课程设计——25道蓝桥杯练习题_蓝桥杯c语言题目

一、基础练习

1.fib数列

题目

题目链接

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

数据规模与约定

1 <= n <= 1,000,000。

解题思路

很明显，数据规模并不大，O(n)时间复杂度便可解决。

但如果数据规模非常庞大，我们可以利用到下面这张图的矩阵递推公式再根据矩阵快速幂解决：

解题代码

解法一(简单递推)：时间复杂度O(n)

适用于数据量少于10^8的情况

#include <stdio.h>
const int MOD = 10007;
int main() {
    int n;
    scanf("%d", &n);
    int a=1,b=1;
    if(n<=2)printf("1");
    else{
        int tmp;
				int i;
        for(i=3;i<=n;i++) {
            tmp = b;
            b = (a+b)%MOD;
            a = tmp;
        }
        printf("%d",b);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解法二(矩阵快速幂)：时间复杂度O(logn)

适用于数据量大于10^8的情况

//
// Created by Alone on 2021/11/19.
//
#include <bits/stdc++.h>
using namespace std;

typedef long long ll ;

//TODO To design a matrix class to solve this problem
class Matrix{
    ll** date;
    int m;
    int n;
public: static const int MOD;
public:
    Matrix(ll** rec,int n,int m):date(rec),n(n),m(m){}//C format to init
    Matrix():date(NULL),m(0),n(0){} //aefault
    Matrix(Matrix& b):n(b.n),m(b.m){//copy struct
        assert(b.date!=NULL && b.n>0 && b.m>0);
        date = new ll*[n];
        copy(b.date,b.date+n,date);
        for(int i=0;i<n;i++){
            date[i] = new ll[m];
            copy(b.date[i],b.date[i]+m,date[i]);
        }
    }
    ~Matrix(){//destruct
        assert(date!=NULL && n>0 && m>0);
        for (int i = n-1; i >=0 ; --i) {
            delete [] date[i];
        }
        delete[] date;
    }
    Matrix& operator*(Matrix& b){//TODO operator* to overload
        assert(b.date!=NULL && date!=NULL && m==b.n);
        ll tmp[n][b.m];
        for(int i=0;i<n;i++){
            for(int j=0;j<b.m;j++){
                ll sum = 0;
                for(int k=0;k<m;k++){
                    sum = (sum + date[i][k]*b.date[k][j])%MOD;
                }
                tmp[i][j] = sum;
            }
        }
        this->m = b.m;
        for(int i=0;i<n;i++){
            for (int j = 0; j < m; ++j) {
                date[i][j] = tmp[i][j];
            }
        }
        return *this;
    }
    void init(){//TODO initialized to unit matrix
        assert(date!=NULL && n>0 && m>0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if(i==j)date[i][j] = 1;
                else date[i][j] = 0;
            }
        }
    }
    void quickPow(ll c){//TODO quick pow for matrix
        if(c==1||c<0)return;
        if(c==0){
            init();
            return;
        }
        Matrix tmp(*this);
        init();
        while (c){
            if(c&1)
                *this = *this * tmp;
            c >>= 1;
            tmp = tmp*tmp;
        }
    }
    void print(){//TODO to print this matrix
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cout<<date[i][j]<<' ';
            }
            cout<<endl;
        }
    }
    int get(int x,int y){//TODO provide access to the outside
        assert(date!=NULL && x<n && y<m);
        return date[x][y];
    }
};
const int Matrix::MOD = 1007;//TODO set the factor for mod operation

int main(){
    ll c;
    cin>>c;
    ll** matrix = new ll*[2];
    matrix[0] = new ll[2]{1,1};
    matrix[1] = new ll[2]{1,0};
    Matrix mat(matrix,2,2);
    mat.quickPow(c-1);

    ll** res = new ll*[2];
    res[0] = new ll[1]{1};
    res[1] = new ll[1]{1};
    Matrix fib(res,2,1);
    Matrix ret(mat*fib);
    cout<<ret.get(1,0);
    return 0;
}


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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

2.闰年判断

题目

题目链接

解题思路

只要挑选处闰年即可，闰年有个判断方式将其判断：

关于闰年的解释：

1. 普通年份能被4整除，且不能被100整除的，是闰年。（ 如2004年就是闰年）
2. 世纪年份能被400整除的是闰年。（ 如2000年是闰年，1900年不是闰年）

如果年份是闰年，那么它的二月份就会比平常多1天。

解题代码

#include<stdio.h>
int main(){
    int n;
    const char* res[]= {"no","yes"};
    scanf("%d",&n);
    int index = 0;
    if(n%400==0||(n%4==0&&n%100!=0))
        index = 1;
    fputs(res[index],stdout);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

3. 数列特征

题目

题目链接

解题思路

求一个数组的最大值和最小值以及所有数字的和。。

解题代码

#include<iostream>
#include<algorithm>
#include<limits>
using namespace std;
int main(){
    int n;
    cin>>n;
    int nums[n];
    int mx=INT_MIN,mn=INT_MAX,sum = 0;
    for(int i=0;i<n;i++){
        cin>>nums[i];
        mx = max(mx,nums[i]);
        mn = min(mn,nums[i]);
        sum += nums[i];
    }
    printf("%d\n%d\n%d",mx,mn,sum);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.查找整数

题目

题目链接

解题思路

按照题目意思来就行，直接查找第一次出现的位置即可。

解题代码

解法一：C风格

#include <iostream>
using namespace std;

int main(){
    int n,target;
    int res = -1;
    cin>>n;
    int nums[n];
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    cin>>target;
    for (int i = 0; i < n; ++i) {
        if(nums[i]==target){
            res = i+1;
            break;
        }
    }
    cout<<res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解法二：C++风格

由于C++98不支持lamda表达式，所以需要把传入的函数单独写出来了。

#include <bits/stdc++.h>
using namespace std;
void input(int& a){cin>>a;}
int main(){
    int n,target,res;
    cin>>n;
    int nums[n];
    for_each(nums,nums+n,input);
    cin>>target;
    res = find(nums,nums+n,target)-nums+1;
    if(res>n)
        res = -1;
    cout<<res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

C++11风格

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,target;
    int res;
    cin>>n;
    int nums[n];
    for_each(nums,nums+n,[](int& a){cin>>a;});
    cin>>target;
    res = find(nums,nums+n,target)-nums+1;
    if(res>n)
        res = -1;
    cout<<res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.杨辉三角形

题目

题目链接

解题思路

根据杨辉三角的性质来做，对于杨辉三角第 i 行、第 j 列的元素，我们用 dp[i][j] 来进行表示，那么有以下关系：
d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] ( 0 < j < m ) 1 ( j = 0 , j = m ) dp[i][j] = \left\{

$$\begin{array}{l} dp[i-1][j]+dp[i-1][j-1](0<j<m) \\ 1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(j=0,j=m) \end{array}$$ \right. dp[i][j]={dp[i−1][j]+dp[i−1][j−1](0<j<m)1(j=0,j=m)​

解题代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int nums[n][n];
    memset(nums,0,sizeof(nums));
    int cnt = 1; //表示该层有多少列需要更新
    for(int i=0;i<n;i++,cnt++){
        for(int j=0;j<cnt;j++){
            if(j==0||j==n-1)
                nums[i][j] = 1;
            else
                nums[i][j] = nums[i-1][j]+nums[i-1][j-1];
        }
    }
    //打印结果
    cnt = 1;
    for (int i = 0; i < n; ++i,++cnt) {
        for (int j = 0; j < cnt; ++j) {
            printf("%d ",nums[i][j]);
        }
        printf("\n");
    }
    return 0;
}
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

6.数列排序

题目

题目链接

解题思路

排序算法，有很多，有冒泡/插入/选择/基数/基尔/快速/堆/归并/桶排序等等等，这些大概是10大必会的排序，其中以快排运用最广，而快排，又分几种实现方式，大概分两类，基于比较的挖坑填补实现，以及直接基于比较的交换实现。我这里手写的快排用的是交换实现。

解题代码

#include <bits/stdc++.h>
using namespace std;
//快速排序
void qsort(int* nums, int l, int r) {
    if (l >= r)return;
    int tl = l, tr = r;
    int cmp = nums[(l + r) / 2];
    while (tl <= tr) {
        while (nums[tl] < cmp)tl++;
        while (nums[tr] > cmp)tr--;
        if (tl <= tr) {
            swap(nums[tl], nums[tr]);
            tl++;
            tr--;
        }
    }
    qsort(nums, l, tr);
    qsort(nums, tl, r);
}
//快排入口
void quickSort(int* nums, int len) {
    qsort(nums, 0, len - 1);
}

int main(){
    int n;
    cin>>n;
    int nums[n];
    for (int i = 0; i < n; ++i) {
        cin>>nums[i];
    }
    quickSort(nums,n);
    for (int i = 0; i < n; ++i) {
        cout<<nums[i]<<' ';
    }
    return 0;
}
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

7.算法训练 P0701 单词变复数

题目

题目链接

题目详解

简单明了的三种分类讨论，我这里实现一个专门判断是否以某个字符结尾的函数，然后一切就引刃而解了。

解题代码

完全的纯种C优质代码：

#include <stdio.h>
#include <string.h>
#define false 0
#define true 1
typedef unsigned char bool;
//TODO 判断字符串是否以某个字符串结尾
bool endWith(char* s,int n,const char* cmp,int m){
    int cnt ;//用于反向记录有多少个字符相同
    for (cnt = 0; n-1-cnt >=0&& m-1-cnt>=0 ; ++cnt) {
        if(s[n-1-cnt]!=cmp[m-1-cnt])
            return false;
    }
    return cnt == m;
}
//TODO 判断是否是元音字母
inline bool isvowel(char ch){
    return ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u';
}
int main(){
    char s[50];
    gets(s);
    int n = strlen(s);
    //TODO 三种情况
    if(endWith(s,n,"s",1)||endWith(s,n,"z",1)||
    endWith(s,n,"x",1)||endWith(s,n,"ch",2)||endWith(s,n,"sh",2)){
        strcat(s,"es");
    } else if(endWith(s,n,"y",1)&&n-2>=0&&!isvowel(s[n-2])){
        s[n-1] = 0;
        strcat(s,"ies");
    }else{
        strcat(s,"s");
    }
    fputs(s,stdout);
    return 0;
}
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

8.算法训练 P0702 实现strcmp

题目

题目链接

解题思路

• 由于我平时是比较对源码感兴趣的，所以本人也比较喜欢写这种造轮子的题目。

strcmp的比较无非就是三种情况：

1. 完全匹配，如"abc",“abc”
2. 部分匹配，如"abcd",“abf”
3. 单方面完全匹配，如"abcd",“ab”

而计算差值的时候我们就需要对以上三种情况进行思考。

接下来结合代码应该就非常好理解了。

解题代码

#include <stdio.h>
int strcmp(const char* s1,const char* s2){
    int i = 0;
    int ret = 0;
    //TODO 跳出循环后无非就三种情况：1.完全匹配 2.部分匹配 3.单方面完全匹配
    while (s1[i]!=0&&s2[i]!=0){
        if(s1[i]!=s2[i]){
            ret = s1[i] - s2[i];
            break;
        }
        i++;
    }
    //TODO 处理单方面完全匹配的情况
    if((s1[i] == 0&&s2[i] != 0)||(s1[i] != 0&&s2[i] == 0))
        ret = s1[i]==0?-s2[i]:s1[i];
    return ret;
}
int main(){
    char s1[1005],s2[1005];
    gets(s1);
    gets(s2);
    printf("%d",strcmp(s1,s2));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9.试题 算法训练 P0703 反置数

题目

题目链接

解题思路

我认为有至少两种解题思路：

1. 按照题目给的过程进行模拟，这个过程其实也很简单，直接就写两个函数就可以解决问题：
   一个用于去掉后缀0的函数以及一个用于把整数的数值反转的函数。这个方法非常好写，也很快，但如果数字很大就没法了。
2. 通过字符串模拟加法过程，恰好字符串大数加减的正常过程就是先反转再加减的，而这题正好就是需要反向加减。所以完全可以用字符串模拟大数加减解决。但我们需要对字符串前后的0进行处理，否则不符合打印要求。（正好后面还有大数加减的题目，我就偷个懒用它了）

解题代码

#include <stdio.h>
#include <string.h>

char sum[20];

//TODO 处理尾部的0，长度参数传入指针，方便同时修改长度
void solveBack(char *s, int *l) {
    int cnt = 0;
    int n = l == NULL ? strlen(s) : *l;
    while (n - cnt - 1 >= 0) {
        if (s[n - cnt - 1] == '0') {
            s[n - cnt - 1] = 0;
            if (l != NULL)(*l)--;
        } else break;
        cnt++;
    }
}

//TODO 处理前面的0
char *solvePre(char *s, int *l) {
    int cnt = 0;
    int n = l == NULL ? strlen(s) : *l;
    while (cnt < n) {
        if (s[cnt] == '0') {
            s[cnt] = 0;
            if (l != NULL)(*l)--;
        } else break;
        cnt++;
    }
    return s + cnt;
}

int main() {
    char s1[10], s2[10];
    scanf("%s %s", s1, s2);
    //TODO 直接的大数相加即可
    int n1 = strlen(s1), n2 = strlen(s2);
    solveBack(s1, &n1);
    solveBack(s2, &n2);
    int maxS = n1 > n2 ? n1 : n2;
    int up = 0;
    int a1, a2;
    int index = 0;
    //TODO 大数加减的逻辑部分
    for (int i = 0; i < maxS; ++i) {
        a1 = i < n1 ? s1[i] - '0' : 0, a2 = i < n2 ? s2[i] - '0' : 0;
        int base = up + a1 + a2;
        up = base / 10;
        sum[index++] = base % 10 + '0';
    }
    while (up) {
        sum[index++] = up % 10 + '0';
        up /= 10;
    }
    sum[index] = 0;
    solveBack(sum, NULL);
    char *ret = solvePre(sum, NULL);
    puts(ret);
    return 0;
}
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

10.试题 算法训练 P0704 满足条件的回文数和质数

题目

题目链接

解题思路

分离连个逻辑函数即可简单实现功能：

1. 判断是否为质数。
2. 判断是否是回文数。

这两个数的判断都有多种方法进行，这里不过多赘述。

我用的都是最质朴的方法进行判断。

解题代码

#include <stdio.h>
#include <string.h>

bool isPrim(int n){
    if(n<2)return false;
    if(n==2)return true;
    if(n%2==0)return false;//为偶数比不可能为质数
    for (int i = 2; i*i <= n ; ++i) {
        if(n%i==0)
            return false;
    }
    return true;
}
bool isPal(int n){
    char s[10];
    sprintf(s,"%d",n);
    int l=0,r = strlen(s)-1;
    while (l<r){
        if(s[l]!=s[r])
            return false;
        l++;
        r--;
    }
    return true;
}
int main() {
    int min,max;
    scanf("%d %d",&min,&max);
    for (int i = min; i < max; ++i) {
        if(isPal(i)&&isPrim(i))
            printf("%d ",i);
    }
    return 0;
}
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

11.试题 算法训练 P0601 实现删除字符函数

题目

题目链接

解题思路

如果这题只是为了解题，那么很简单，直接碰到这个字符就不打印即可。

如果是为了实现这个删除给定字符的函数功能，我有两种思路：

1. 如果不创建新的内存进行删除，那么最直观的方法就是一个一个字符的来进行删除操作，如果等于这个字符，那么直接进行一轮删除后的平移。时间复杂度较高，最坏为O(n^2)。当然可以优化为O(n)级别的，那就是我们采取给整个数组赋值的思路，从左到右扫描赋值，如果等于对应字符，那么就跳过不赋值，最后在后面加个 ‘\0’ 即可。
2. 如果创建新内存进行，那么很简单的就可以实现O(n)级别的。

解题代码

解法一：只为解题的解题(适合真正比赛时)

#include <stdio.h>
int main() {
    char s[100];
    gets(s);
    char target = getchar();
    int i = 0;
    while (s[i]!=0){
        if(s[i]!=target){
            putc(s[i],stdout);
        }
        i++;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法二：从左到右的扫描更新法 O(n) （使用于面试官问你后，你的回答）

#include <stdio.h>

int main() {
    char s[100];
    gets(s);
    char target = getchar();
    int i = 0;
    //TODO 删除逻辑处理
    int index = 0;
    while (s[i]!=0){
        if(s[i]!=target){
            s[index++] = s[i];
        }
        i++;
    }
    s[index] = 0;
    //
    puts(s);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

12.试题 算法训练 P1103 复数加减乘除类的设计

题目

编程实现两个复数的运算。设有两个复数 和 ，则他们的运算公式为：

要求：（1）定义一个结构体类型来描述复数。
　　（2）复数之间的加法、减法、乘法和除法分别用不用的函数来实现。
　　（3）必须使用结构体指针的方法把函数的计算结果返回。
　　说明：用户输入：运算符号(+,-,*,/) a b c d.
　　输出：a+bi，输出时不管a,b是小于0或等于0都按该格式输出，输出时a,b都保留两位。

输入：

• 2.5 3.6 1.5 4.9
  输出：
• 1.00±1.30i

解题思路

• 把高中那套负数加减乘除的公式套用进去即可！

这里C的话可用函数式的面向的对象实现，C++的话用一个类重载所有的运算符即可。

解题代码

#include <bits/stdc++.h>
struct complex{
    double x,y;
    complex(double x,double y):x(x),y(y){}
    complex():x(0),y(0){}
    //TODO overload operator+ to redefine +
    complex operator+(complex& src){
        double tx = x+src.x;
        double ty = y+src.y;
        return complex(tx,ty);
    }
    //TODO overload operator- to redefine -
    complex operator-(complex& src){
        double tx = x - src.x;
        double ty = y- src.y;
        return complex(tx,ty);
    }
    //TODO overload operator* to redefine *
    complex operator*(complex& src){
        double tx = x*src.x - y*src.y;
        double ty = x*src.y + y*src.x;
        return complex(tx,ty);
    }
    //TODO overload operator* to redefine /
    complex operator/(complex& src){
        double t = src.x*src.x + src.y*src.y;
        double tx = (x*src.x+y*src.y)/t;
        double ty =(src.x*y-x*src.y)/t;
        return complex(tx,ty);
    }
};

int main() {
    char op;double x1,y1,x2,y2;
    scanf("%c %lf %lf %lf %lf",&op,&x1,&y1,&x2,&y2);
    complex a(x1,y1);
    complex b(x2,y2);
    complex res;
    //TODO What operations are performed according to your choice
    switch (op) {
        case '+':
            res = a+b;
            break;
        case '-':
            res = a-b;
            break;
        case '*':
            res = a*b;
            break;
        case '/':
            res = a/b;
            break;
    }
    //TODO print the result by two decimal places
    printf("%.2lf+%.2lfi",res.x,res.y);
    return 0;
}
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

13.试题 算法训练 删除数组零元素

题目

题目链接

解题思路

这和之前的删除字符的题目没有任何的本质区别。就是直接通过一个指针从左到右遍历，而另一个指针从左到右更新。

代码即是思路。

解题代码

#include <bits/stdc++.h>
//TODO 删除数组指定的值，然后删除后的数组长度
int remove_nums(int* nums,int len,int val){
    int index = 0;
    int i = 0;
    while (i<len){
        if(nums[i]!=val){
            nums[index++] = nums[i];
        }
        i++;
    }
    return index;
}
int main() {
    int n;
    std::cin>>n;
    int nums[n];
    for (int i = 0; i < n; ++i) {
        std::cin>>nums[i];
    }
    int res_len = remove_nums(nums,n,0);
    printf("%d\n",res_len);
    for (int j = 0; j < res_len; ++j) {
        printf("%d ",nums[j]);
    }
    return 0;
}
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

14.试题 算法训练 大整数加法

题目

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

任意输入两个正整数a,b，求两数之和。（注：本题会输入超过32位整数限制的大整数）

样例输入

4611686018427387903 4611686018427387903

样例输出

9223372036854775806

数据规模和约定

1=<a,b<=4611686018427387903

解题思路

由于前面都用到了大整数加法，所以直接拿前面的代码来用了。具体实现思路也很简单，就是一个加法的模拟过程，一般来说三步走：

1. 把数组逆置。
2. 用另一个数组计算答案，注意要分进位和本位进行模拟运算。
3. 如果最后的进位不为0，则继续往前加法。

解题代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
//TODO 删除数组指定的值，然后删除后的数组长度
char sum[50] = {0};
void reverse(char* s,int len){
    int i = 0,j = len-1;
    while (i<j){
        std::swap(s[i],s[j]);
        i++;j--;
    }
}
int main() {
    char a[50],b[50];
    scanf("%s %s",a,b);
    //TODO 1.reverse
    int na = strlen(a);reverse(a,na);
    int nb = strlen(b);reverse(b,nb);
    //TODO 2.calculate
    int maxL = na>nb?na:nb;
    int up = 0,base,ta,tb,i;
    for (i = 0; i < maxL; ++i) {
        ta = i<na?a[i]-'0':0;
        tb = i<nb?b[i]-'0':0;
        base = ta+tb+up;
        up = base/10;
        sum[i] = base%10+'0';
    }
    while (up){
        sum[i++] = up%10+'0';
        up /= 10;
    }
    //TODO Print
    for (int j = i-1; j >=0 ; --j) {
        putc(sum[j],stdout);
    }
    return 0;
}
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

15.试题 算法训练 最小乘积(基本型)

题目

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

给两组数，各n个。
　　请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。
　　例如两组数分别为:1 3　　-5和-2 4 1

那么对应乘积取和的最小值应为：
　　(-5) * 4 + 3 * (-2) + 1 * 1 = -25

输入格式

第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。
　　n<=8,T<=1000

输出格式

一个数表示答案。

样例输入

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
1
2
3
4
5
6
7

样例输出

-25
6
1
2

解题思路

根据题目意思，很明显，我们把数组的位置，一个排成从小到大，一个排成从大到小，对应相乘即可。

解题代码

#include <iostream>
#include <algorithm>
int nums1[10];
int nums2[10];
int main() {
    int n;
    std::cin>>n;
    //TODO 思路：一个数组从小到大排序，一个数组从大到小排序，最后输出它们的对应乘积即可
    while (n--){
        int c;
        std::cin>>c;
        for (int i = 0; i < c; ++i) {
            std::cin>>nums1[i];
        }
        std::sort(nums1,nums1+c);
        for (int i = 0; i < c; ++i) {
            std::cin>>nums2[i];
        }
        std::sort(nums2,nums2+c,std::greater<int>());
        int sum = 0;
        for (int i = 0; i < c; ++i) {
            sum += nums1[i]*nums2[i];
        }
        std::cout<<sum<<'\n';
    }
    return 0;
}
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

16.试题 算法训练 矩阵运算

题目

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

给定一个n*n的矩阵A，求A+AT的值。其中AT表示A的转置。

输入格式

输入的第一行包含一个整数n。1<=n<=100。
　　接下来n行，每行n个整数，表示A中的每一个元素。每个元素的绝对值不超过10000。

输出格式

输出n行，每行n个整数，用空格分隔，表示所示的答案。

样例输入

3
1 2 3
4 5 6
7 8 9

样例输出

2 6 10
6 10 14
10 14 18

解题思路

这里直接用二维数组存下矩阵然后得到另一个转置矩阵再相加即可。

我一般碰到这类关于某种数据类型的运算，我喜欢把它们抽象为类，然后再进行计算。所以我这题是设计了一个mat类，里面重载了加法等。

解题代码

#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
struct Mat{
    int** nums;
    int n;
    Mat(int** src,int n):nums(src),n(n){}
    Mat(int n):n(n){
        nums = new int*[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = new int[n];
            //TODO 把输入过程放到初始化里面来了
            for (int j = 0; j < n; ++j) {
                cin>>nums[i][j];
            }
        }
    }
    Mat get_transform(){
        int** t_nums = new int*[n];
        for (int i = 0; i < n; ++i) {
            t_nums[i] = new int[n];
            for (int j = 0; j < n; ++j) {
                t_nums[i][j] = nums[j][i];//TODO 转置赋值过程
            }
        }
        return Mat(t_nums,n);
    }
    //TODO 重载加法
    Mat& operator+(Mat& src){
        assert(src.n==n&&nums!=NULL&&src.nums!=NULL);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                nums[i][j] += src.nums[i][j];
            }
        }
        return *this;
    }
    void print(){
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                printf("%d ",nums[i][j]);
            }
            putc('\n',stdout);
        }
    }
};
int main() {
    int n;
    cin>>n;
    Mat a(n);
    Mat b = a.get_transform();
    (a+b).print();
    return 0;
}
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

17.试题 算法训练 百鸡百钱

题目

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

输出格式

满足条件的鸡翁、鸡母和鸡雏的只数，中间空格隔开。每种情况输出到一行。
　　例如 ：
　　0 25 75
　　4 18 78

解题分析

纯纯的用代码解方程，分析草稿如下图：

解题代码

#include <iostream>
using namespace std;

int main() {
    for (int i = 0; i <= 14 ; ++i) {
        for (int j = 0; j <= 25; ++j) {
            if(7*i+4*j==100){
                printf("%d %d %d\n",i,j,100-i-j);
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

18.试题 算法训练 数据传递加密

题目

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

某个公司传递数据，数据是四位整数，在传递过程中需要进行加密的，加密规则如下：每位数字都加上5,然后除以10的余数代替该位数字。再将新生成数据的第一位和第四位交换，第二位和第三位交换。要求输入4位整数，输出加密后的4位整数。比如：输入一个四位整数1234，则输出加密结果为9876。

样例输入

1234

样例输出

9876

题目解析

• 只需要进行两个过程：

1. +5除以10得到余数替换每一位。
2. 交换数据（第一位和第四位交换，第二位和第三位交换）。

解题代码

#include <iostream>
#include <cstring>
using namespace std;
//TODO 替换操作
void replace(char* s){
    int i =0,data;
    while (s[i]!=0){
        data = s[i] - '0';
        s[i] = (data+5)%10 + '0';
        i++;
    }
}
//TODO 交换操作
void swap(char* s){
    int i=0,j = strlen(s)-1;
    char tmp;
    while (i<j){
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        i++,j--;
    }
}

int main() {
    char s[10];
    gets(s);
    replace(s);
    swap(s);
    puts(s);
    return 0;
}
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

二、算法提高

19. 试题 算法提高 心形

题目

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

根据给出的最大宽度，输出心形（注意空格，行末不加多余空格）。

输入格式

一行一个整数width，表示最宽的一行中有多少个“*”。

输出格式

若干行表示对应心形。注意为让选手更清晰观察样例，样例输出中用“-”表示空格，请选手在提交的程序中不要输出“-”。

样例输入

13

样例输出

数据规模和约定

width总是4的倍数加一，且width >= 13。

题目解析

这种打印类型题目要学会逐一找规律剖析！

在我的写法里面，这个心形能够解分为三个部分：(如下图)

首先我们需要确认一个元素的组成长度！本题输入的就是第二部分的长度，比如样例的13，而我们发现每个部分由两个字符构成，所以我们下面的讨论都是以两个字符为单位。而拆分成不同的元素种类的话也只有两种：1. " "(两个空格)称为空白元素 2. " *"(一个空格一个星)称为星元素。

以下所有用到的 n 均表示输入的变量值。

一、第一部分

关于第一部分我还是分为三个部分进行每一行的打印：

1. 左边的空白元素：它的起始长度很明显就是第一部分的深度，而第一部分的深度 = ((n-1)/2)/2。
   后续这部分元素都以每次递减一个的趋势。
2. 中间的空白元素：它的起始长度应该从第一部分的底层往上推，你发现从最底层长度为1开始，每层+2。
   *所以起始元素长度为：1+(deep-1)2 ，而后续以每次递减2个的趋势。
3. 星元素：这个算是两个部分并作一个部分，因为这两个部分没有任何区别。一个在左边空白和中间空白的中间，而另一个在最右边。从1个开始往下递增，每次递增两个。

二、第二部分

第二部分就没有那么多弯弯绕绕了，直接 n 是多少就打印多少个星。

三、第三部分

第三部分分为两部分：

1. 左边的空白元素：从1开始往下递增。
2. 右边的星元素：从n-1往下递减两个元素。

当星元素递减为1个的时候结束！

解题代码

AC图片：

#include <iostream>
using namespace std;
//TODO 用于打印n个“  ”
void print1(int n){
    for (int i = 0; i < n; i++)
    {
        putc(' ',stdout);
        putc(' ',stdout);
    }
}
//TODO 用于打印n个" *"
void print2(int n){
    for (int i = 0; i < n; i++)
    {
        putc(' ',stdout);
        putc('*',stdout);
    }
}

int main(){
    int n;cin >> n;
    int deep = (n-1)/4;
    int p1 = deep;
    int p2 = 1;
    int p3 = 1+2*(deep-1);
    //TODO 第一部分的打印
    for (int i = 0; i < deep; i++)
    {
        print1(p1);
        print2(p2);
        print1(p3);
        print2(p2);
        p1 -= 1;
        p2 += 2;
        p3 -= 2;
        putc('\n',stdout);
    }
    //TODO 第二部分打印：最简单的纯一行
    print2(n);
    putc('\n',stdout);
    //TODO 第三部分打印
    int n1 = 1,n2 = n-2;
    while (n2>=1){
        print1(n1);
        print2(n2);
        n1++;
        n2-=2;
        putc('\n',stdout);
    }
    return 0;
}
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

20.试题 算法提高 字符串查找

题目

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

给定两个字符串a和b，查找b在a中第一次出现的位置。
　　如a=“hello world”，b=“world”时，b第一次出现是在a的第7个字符到第11个字符，按照C++的习惯，位置从0开始编号，所以b在a中第一次出现的位置为6。

输入格式

输入包括两行，分别为两个字符串a和b，字符串中可能含有空格。字符串的长度不超过500。请注意读入一行字符串的方法。

输出格式

输出b在a中第一次出现的位置。如果b没有在a中出现，则输出-1。

样例输入

hello world
world

样例输出

6

样例输入

hello world
tsinsen

样例输出

-1

题目链接

题目解析

不知道是不是这道题的缘故，好像只能提交一个函数体内的代码，不能提交完整代码！

所以我都AC代码如下所示：

int n = 0;while (b[n]!=0)n++;//计算b的长度
    int i=0,j;
    while (a[i]!=0){
        j = 0;
        while (b[j]!=0){
            if(a[i+j]!=b[j]){
                break;
            }
            j++;
        }
        if(j==n){
            return i;
        }
        i++;
    }
    return -1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

AC截图：

解题代码

其实本题我是想拿来练练kmp算法的，奈何只能写部分代码块进行提交，连函数都不能写，所以只好作罢。

实际直接调用语言的内部函数库的话，可以像下面这样：

C version

#include <string.h>
#include <stdio.h>
int main() {
    char s1[100],s2[100];
    gets(s1);
    gets(s2);
    char* res = strstr(s1,s2);
    if(res==NULL){
        printf("-1");
    }
    else{
        printf("%d",res-s1);
    }
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cpp version

#include <iostream>
#include <string>
int main() {
   using namespace std;
   string s1,s2;
   getline(cin,s1);
   getline(cin,s2);
   cout<<int(s1.find(s2));
   return 0;
}
1
2
3
4
5
6
7
8
9
10

21.试题 算法提高 校门外的树

题目

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数 轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已 知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树 都移走后，马路上还有多少棵树。

输入格式

输入文件的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点 和终止点的坐标。

输出格式

输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

500 3
150 300
100 200
470 471

样例输出

298

数据规模和约定

对于20%的数据，区域之间没有重合的部分；
　　对于其它的数据，区域之间有重合的情况。

题目链接

解题思路

这题蓝桥杯平时训练的时候，只能说是写烂了。。这题本可以按照首尾区间 =1 +1 的方式来处理，但是由于本题是删除区间内的元素后不能重复删除的情况，所以目前我只能想到用直接暴力的覆盖法