【C++ 算法练习题】数组下标应用

问题一

问题描述

小A参加了一个越野比赛,比赛路线中有 n 个任务点。比赛说明中给出了每个任务点距离前一个任务点的距离，所有选手会统一从起点出发，按照任务点编号顺序进行徒步比赛。

小A在比赛过程中，有 k 次机会可以向组委会询问任意两个任务点（可能不相邻）之间的总距离，从而分配体力，你作为组委会的成员之一要尽快回答他的提问。

输入输出量较大，请使用 scanf/printf 进行输入输出。

输入格式

输入包含三部分：

• 第一部分有一行，为两个空格隔开的整数 n ，k，

  

   表示任务点的个数和询问的次数；
• 第二部分有一行，为 n−1 个用空格隔开的整数，为每个任务点距离前一个任务点的距离，每个数为不超过

  

   的正整数；
• 第三部分有 k 行，每行有两个空格隔开的整数 a, b, 

  

   ，分别为两个任务点的编号。

输出格式

输出包含 k 个空格隔开的整数，为蒜头君每次询问的两个任务点之间的距离。

样例输入

4 3
3 5 1
1 2
2 3
3 4
           

样例输出

3 5 1
           

问题分析

我们可以开一个 long long 数组来记录前缀和，通过这个前缀和的数组，我们可以直接做差得到任何两点之间的距离。

代码

#include<bits/stdc++.h>
using namespace std;
int n, k;
int d[100005];
long long sum[100005];//前缀和
int main(){
    scanf("%d %d", &n, &k);
    for(int i = 2; i <= n; i++){
        scanf("%d", &d[i]);
    }
    for(int i = 2; i <= n; i++){
        sum[i] = sum[i - 1] + d[i];
    }
    int a, b;
    while(k--){
        scanf("%d %d", &a, &b);
        printf("%lld", sum[b] - sum[a]);
        if(k != 0) printf(" ");
    }
    return 0;
}
           

问题二

问题描述

小A在数学课中学到了如何进行两个多项式相乘的操作，例如要计算：

， 先要利用分配律将两个式子拆开相乘，再合并幂次相同的项。当我们计算

时，前面的系数相乘作为结果的系数，幂次数相加作为结果的幂次数，

，因此上面的式子可以这样计算：

那么，我们可以使用数组下标来表示幂次数，数组元素的值表示系数，模拟一下上面的计算过程，就能得到两个多项式相乘的结果了。

输入格式

输入有 4 行，每行有两个空格隔开的整数 a，b，1 ≤ a ≤ 10，0 ≤ b ≤ 10，分别代表系数和幂次数，例如 2 3 代表

。其中前两行属于第一个多项式，后两行属于第二个多项式.

输出格式

输出若干行，表示多项式相乘的结果，每一项输出一行，按照幂次数从大到小输出。

输入样例

2 1
4 2
3 1
4 0
           

输出样例

12 3
22 2
8 1
           

问题分析

通过创建一个数组 res[25] 来存储最终结果，下表记录 n 次方，res[n] 表示 

 前的系数。

代码

#include<bits/stdc++.h>
using namespace std;
int a[2][2], b[2][2];
int res[25];
int main(){
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
             cin >> a[i][j];
        }
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
             cin >> b[i][j];
        }
    }
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            res[a[i][1] + b[j][1]] += a[i][0] * b[j][0];
        }
    }
    for(int i = 20; i >= 0; i--){
        if(res[i]){
            cout << res[i] << " " << i << endl;
        }
    }
    return 0;
}