每日一练c++题目日刊 | 第十二期

第一题

题目背景故事

在一个数学竞赛中，一个小学生在做题时遇到了这道题目，但是他不会等差数列求和公式，于是他请教了你，作为一个编程高手，你帮他写了一个程序来完成这道题目。

题目描述

给定一个整数 n n n，求出 ∑ i = 1 n i 3 \sum_{i=1}^{n}i^3 ∑i=1n​i3 的值。

输入描述

一个整数 n n n ( 1 ≤ n ≤ 1 0 9 ) (1≤n≤10^9) (1≤n≤109)。

输出描述

一个整数，表示 ∑ i = 1 n i 3 \sum_{i=1}^{n}i^3 ∑i=1n​i3 的值。

输入样例

5

输出样例

225

解题思路

首先我们可以把题目中的公式简化一下，得到： ∑ i = 1 n i 3 = n 2 ( n + 1 ) 2 4 \sum_{i=1}^{n}i^3=\frac{n^2(n+1)^2}{4} ∑i=1n​i3=4n2(n+1)2​。

C++参考程序

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << (long long)n * n * (n + 1) * (n + 1) / 4 << endl;
    return 0;
}

说明：本题中使用了long long类型，来防止溢出。

第二题

题目背景故事

在这个世界上，有一种叫做“钻石”的矿物，它们排列在一个序列中，每一颗钻石都有一个价值，我们只能从这个序列中选出一些钻石，使得它们的价值是不下降的，并且要求出最多能选出多少颗钻石。

题目描述

给定一个长度为 n n n 的序列 a a a，求这个序列的最长不下降子序列的长度。

输入描述

一个整数 n n n ( 1 ≤ n ≤ 1 0 5 ) (1≤n≤10^5) (1≤n≤105)，表示序列 a a a 的长度。
一个长度为 n n n 的序列 a a a。

输出描述

一个整数，表示最长不下降子序列的长度。

输入样例

6
5 6 7 8 1 2

输出样例

4

解题思路

这是一道动态规划问题，我们可以建立一个 n n n 个元素的数组 d p dp dp， d p i dp_i dpi​ 表示以第 i i i 个元素结尾的最长不下降子序列长度。

对于第 i i i 个元素，我们可以从 0 0 0 到 i − 1 i-1 i−1 枚举所有的元素，如果 a j ≤ a i a_j \le a_i aj​≤ai​，那么 d p i = m a x ( d p i , d p j + 1 ) dp_i = max(dp_i, dp_j+1) dpi​=max(dpi​,dpj​+1)。

C++参考程序

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], dp[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

代码说明（此部分有ChatGPT补充说明）：

1. 初始化一个长度为 n n n的序列 a a a和 d p dp dp数组
2. 从 1 1 1到 n n n遍历 a a a数组，每次读入一个数，并将 d p i dp_i dpi​初始化为 1 1 1
3. 从 1 1 1到 n n n遍历 a a a数组，对于每个 i i i，枚举 j j j，如果 a j ≤ a i a_j \le a_i aj​≤ai​，那么更新
   d p i = m a x ( d p i , d p j + 1 ) dp_i = max(dp_i, dp_j+1) dpi​=max(dpi​,dpj​+1)
4. 从 1 1 1到 n n n遍历 d p dp dp数组，取 m a x max max，最后输出结果。

第三题

题目背景故事

在研究一种新型材料的性质时，科学家们发现这种材料的性质与其成分之间存在线性关系，科学家们希望通过线性方程组来求解这种材料的组成成分。

题目描述：给出一个n元线性方程组 A × X = B A \times X=B A×X=B，其中 A A A是n*n的矩阵， X X X是n维的未知向量， B B B是n维的常数向量。求解此线性方程组的解 X X X。

输入描述

第一行一个整数n，表示方程组的元数。
接下来n行，每行n个浮点数，表示矩阵A的元素。
接下来n行，每行1个浮点数，表示向量B的元素。

输出描述

n个浮点数，表示向量X的元素。

输入样例

3
1 2 3
4 5 6
7 8 9
1
2
3

输出样例

-0.2857142857142857
0.8571428571428571
-0.2857142857142857

解题思路

高斯消元法

C++参考程序

#include <iostream>
#include <cmath>
using namespace std;
const int N = 110;
double a[N][N], b[N], x[N];
int n;

void Gauss()
{
    for(int i = 0; i < n; i ++)
    {
        int k = i;
        for(int j = i + 1; j < n; j ++)
            if(fabs(a[j][i]) > fabs(a[k][i])) k = j;
        if(k != i)
            for(int j = 0; j <= n; j ++)
                swap(a[i][j], a[k][j]);
        for(int j = i + 1; j < n; j ++)
        {
            double t = a[j][i] / a[i][i];
            for(int k = i; k <= n; k ++)
                a[j][k] -= t * a[i][k];
        }
    }
    for(int i = n - 1; i >= 0; i --)
    {
        for(int j = i + 1; j < n; j ++)
            a[i][n] -= a[i][j] * x[j];
        x[i] = a[i][n] / a[i][i];
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    for(int i = 0; i < n; i ++)
        cin >> b[i];
    for(int i = 0; i < n; i ++)
        a[i][n] = b[i];
    Gauss();
    for(int i = 0; i < n; i ++)
        cout << x[i] << endl;
    return 0;
}

上面的参考程序中的C++代码并没有考虑矩阵的特殊情况，如行列式为0，所以在实际应用中需要判断。