TOIP 202412程式碼

P1 旅遊計畫 (Travel)

分析

功能：
該程式在兩個數列 ptr 和 ptrr 中找到一對數字，使得總成本公式最小，並輸出結果。

公式： total = ptr[i] + ptrr[j] + 1000 * abs(i - j)

步驟：

1. 輸入數據：

   • 讀取兩個固定大小為 10 的數列 ptr 和 ptrr。

2. 變數初始化：

   • total = INT_MAX：存儲當前最小總成本。
   • ii, jj：存儲最小總成本對應的索引（1-based）。

3. 計算總成本：

   • 雙重迴圈遍歷所有可能的 ( (i, j) ) 配對。
   • 計算公式：
     [
     \text{total} = \text{ptr}[i] + \text{ptrr}[j] + 1000 \times |i - j|
     ]
   • 如果當前總成本小於 total，更新 total 和索引 ( ii, jj )。

4. 輸出結果：

   • 輸出最小總成本對應的索引 ( ii, jj ) 和 total。

程式碼

#include <bits/stdc++.h>
using namespace std;
//JAckis666
int main(){
    int n=10;
    int ptr[10];
    int ptrr[10];
    int dp[10];
    for(int i=0;i<10;i++){
        cin>>ptr[i];
    }
    for(int i=0;i<10;i++){
        cin>>ptrr[i];
    }
    int ii,jj,total=INT_MAX;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(ptr[i]+ptrr[j]+1000*abs(i-j)<total){
                total=ptr[i]+ptrr[j]+1000*abs(i-j);
                ii=i+1;
                jj=j+1;
            }
        }
    }
    cout<<ii<<" "<<jj<<" "<<total;
    
}

P2香料 (Spices)

分析

1. 結構定義與變數初始化

   ​​​struct findddd{
   ​​​    int a=0, b=0;
   ​​​};
   

   • 定義結構 findddd，儲存香料所在的層數 (a) 和位置 (b)。
   • 預設屬性 a 和 b 為 0，表示香料尚未找到。
   ​​​int n;
   ​​​cin >> n;
   ​​​int f[10001];
   

   • 讀入要查找的香料數量 n。
   • 陣列 f 儲存要查找的香料編號。

2. 輸入目標香料編號

   ​​​for (int i = 0; i < n; i++) {
   ​​​    cin >> f[i];
   ​​​}
   

   • 使用迴圈讀入香料編號並存入 f 陣列。

3. 初始化貨架資訊

   ​​​findddd pur[20001];
   ​​​int aa, bb;
   ​​​cin >> aa >> bb;
   

   • pur[20001]：大小為 20001 的陣列，儲存每個香料的層數與位置。
   • 讀入 aa 和 bb，分別表示貨架層數和每層的香料數量。

4. 貨架資料存入結構

   ​​​for (int i = 0; i < aa; i++) {
   ​​​    for (int j = 0; j < bb; j++) {
   ​​​        int buy;
   ​​​        cin >> buy;
   ​​​        pur[buy].a = i + 1;
   ​​​        pur[buy].b = j + 1;
   ​​​    }
   ​​​}
   

   • 雙重迴圈遍歷貨架，讀入每個香料編號 buy。
   • 根據所在層數與位置更新 pur[buy] 的 a 和 b。

5. 查詢香料位置

   ​​​for (int i = 0; i < n; i++) {
   ​​​    if (pur[f[i]].a != 0)
   ​​​        cout << pur[f[i]].a << " " << pur[f[i]].b << endl;
   ​​​    else
   ​​​        cout << "-1" << endl;
   ​​​}
   

   • 遍歷目標香料列表 f。
   • 若 pur[f[i]].a 不為 0，則輸出其層數與位置。
   • 若為 0，則表示香料不存在，輸出 -1。

---

程式重點

1. 使用結構儲存每個香料的位置信息，有效解決貨架數據的查詢需求。
2. 使用香料編號作為索引，快速找到對應位置，減少查詢時間。

---

時間複雜度

1. 讀取貨架資料： O(R*C)。
2. 查詢香料位置： O(n)。
   • 查詢每個香料時直接訪問索引，為 O(1)。
3. 總時間複雜度： O(R*C)。

#include <bits/stdc++.h>
using namespace std;
struct findddd{
    int a=0,b=0;

};
int main(){
    int n;
    cin>>n;
    int f[10001];
    for(int i=0;i<n;i++){
        cin>>f[i];
    }
    findddd pur[20001];
    int aa,bb;
    cin>>aa>>bb;
    for(int i=0;i<aa;i++){
        for(int j=0;j<bb;j++){
            int buy;
            cin>>buy;
            pur[buy].a=i+1;
            pur[buy].b=j+1;
        }
    }
    for(int i=0;i<n;i++){
            if(pur[f[i]].a!=0)
        cout<<pur[f[i]].a<<" "<<pur[f[i]].b<<endl;
        else{
            cout<<"-1"<<endl;
        }
    }





}

P3 p902. 凱撒密碼 (Cipher)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string input;
    getline(cin, input);

    int shift;
    cin >> shift;

    shift %= 26;

    for (char &ch : input) {
        if (isupper(ch)) {
            ch = 'A' + (ch - 'A' + shift) % 26;
        } else if (islower(ch)) {
            ch = 'a' + (ch - 'a' + shift) % 26;
        }
    }

    cout << input << endl;

}
Jackis666

只後有空用chatgpt生題解