【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;
}