一、P5661 公交換乘

1. 審題

2. 思路

總花費中，地鐵是必須花費的，公交車可能不花錢（坐地鐵后有贈票），但是與時間和價格有一定關系。

我們來分析一下輸出的 $36$ 是如何得出的。

第一行：$ans+10$
第二行：不用花錢
第三行：$ans+12$
第四行：$ans+3$
第五行：$ans+5$
第六行：$ans+6$

3. 參考答案

#include <iostream>
using namespace std;int n, way, price, t;
int pos = 1, ans;struct Node
{int freeP;int endT;bool used;
}a[100005];int main()
{// 輸入數據cin >> n;while (n--){cin >> way >> price >> t;if (way == 0){ans += price;a[pos].freeP = price;a[pos].endT = t + 45;a[pos].used = false;pos++;}else{while (a[l].endT < t && l < pos-1) // 排除掉過期的贈票{l++;}bool flag = false;for (int i = l; i <= pos-1; i++) // 遍歷贈票{if (price <= a[i].freeP && t <= a[i].endT && a[i].used == false) // 價格、時間、是否被用過{a[i].used = true;flag = true;break;}}if (!flag){ans += price;}}}cout << ans;return 0;
}

二、P1003 鋪地毯

1. 審題

題目描述

為了準備一個獨特的頒獎典禮，組織者在會場的一片矩形區域（可看做是平面直角坐標系的第一象限）鋪上一些矩形地毯。一共有 $n$ 張地毯，編號從 $1$ 到 $n$。現在將這些地毯按照編號從小到大的順序平行于坐標軸先后鋪設，后鋪的地毯覆蓋在前面已經鋪好的地毯之上。地毯鋪設完成后，組織者想知道覆蓋地面某個點的最上面的那張地毯的編號。注意：在矩形地毯邊界和四個頂點上的點也算被地毯覆蓋。

輸入描述

輸入文件名 carpet.in
輸入 $n+2$ 行。第一行，一個整數 $n$，表示總共有 $n$ 張地毯。
接下來的 $n$ 行中，第 $i+1$ 行表示編號 $i$ 的地毯的信息，包含四個整數 $a$，$b$，$g$，$k$，每兩個整數之間用一個空格隔開，分別表示鋪設地毯的左下角的坐標（$a$，$b$）以及地毯在 $x$ 軸和 $y$ 軸方向的長度。
第 $n+2$ 行包含兩個整數 $x$ 和 $y$，表示所求的地面的點的坐標（$x$，$y$）。

輸出描述

輸出文件名 carpet.out
輸出共 $1$ 行，一個整數，表示所求的地毯的編號；若此處沒有被地毯覆蓋則輸出 $?1$。

樣例1

輸入

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

輸出

3

提示

對于 $100\%$ 的數據，$0\le n\le 10^4$，$0\le a,b,g,k\le 10^5$。

2. 參考答案

#include <iostream>
#include <cstdio>
using namespace std;int n;
int tx, ty;
int point[10005][5];int main()
{freopen("carpet.in", "r", stdin);freopen("carpet.out", "w", stdout);// 輸入數據cin >> n;for(int i = 1; i <= n; i++){cin >> point[i][0] >> point[i][1]>>point[i][2] >> point[i][3];point[i][2] += point[i][0];point[i][3] += point[i][1];}cin >> tx >> ty;// 模擬bool flag = false;for (int i = n; i >= 1; i--){if (tx >= point[i][0] && tx <= point[i][2] && ty >= point[i][1] && ty <= point[i][3]){flag = true;cout << i << endl;break;}}if (flag == false){cout << -1 << endl;}fclose(stdin);fclose(stdout);return 0;
}

三、P1071 潛伏者

1. 審題

題目描述

$R$ 國和 $S$ 國正陷入戰火之中，雙方都互派間諜，潛入對方內部，伺機行動。歷盡艱險后，潛伏于 $S$ 國的 $R$ 國間諜小 $C$ 終于摸清了 $S$ 國軍用密碼的編碼規則：

1. $S$ 國軍方內部欲發送的原信息經過加密后在網絡上發送，原信息的內容與加密后所得的內容均由大寫字母'A'$?$'Z'構成（無空格等其他字符）。
2. $S$ 國對于每個字母規定了對應的"密字"。加密的過程就是將原信息中的所有字母替換為其對應的"密字"。
3. 每個字母只對應一個唯一的"密碼"，不同的字母對應不同的“密字”。“密字”可以和原字母相同。

例如，若規定 'A' 的密字為'A'，'B' 的密字為'C'（其他字母及密字略），則原信息 "ABA" 被加密為 "ACA"。
現在，小 $C$ 通過內線掌握了 $S$ 國網絡上發送的一條加密信息及其對應的原信息。小 $C$ 希望能通過這條信息，破譯 $S$ 國的軍用密碼。小 $C$ 的破譯過程是這樣的：掃描原信息，對于原信息中的字母 $x$（代表任一大寫字母），找到其在加密信息中的對應大寫字母y，并認為在密碼里 $y$ 是 $x$ 的密字。如此進行下去直到停止于如下的某個狀態：

1. 所有信息掃描完畢，'A'$?$'Z' 所有 $26$ 個字母在原信息中均出現過并獲得了相應的“密字”。
2. 所有信息掃描完畢，但發現存在某個（或某些）字母在原信息中沒有出現。
3. 掃描中發現掌握的信息里有明顯的自相矛盾或錯誤（違反 S 國密碼的編碼規則）。例如某條信息 "XYZ" 被翻譯為 "ABA" 就違反了“不同字母對應不同密字”的規則。
   在小 $C$ 忙得頭昏腦漲之際，$R$ 國司令部又發來電報，要求他翻譯另外一條從 $S$ 國剛剛截取到的加密信息。現在請你幫助小 $C$：通過內線掌握的信息，嘗試破譯密碼。然后利用破譯的密碼，翻譯電報中的加密信息。

輸入格式

共 $3$ 行，每行為一個長度在 $1$ 到 $100$ 之間的字符串。
第 $1$ 行為小 $C$ 掌握的一條加密信息。
第 $2$ 行為第 $1$ 行的加密信息所對應的原信息。
第 $3$ 行為 $R$ 國司令部要求小 $C$ 翻譯的加密信息。
輸入數據保證所有字符串僅由大寫字母'A'$?$'Z'構成，且第 $1$ 行長度與第 $2$ 行相等。

輸出格式

共 $1$ 行。
若破譯密碼停止時出現 $2,3$ 兩種情況，請你輸出 Failed（注意首字母大寫，其它小寫）。
否則請輸出利用密碼翻譯電報中加密信息后得到的原信息。

樣例1

輸入

AA
AB
EOWIE

輸出

Failed

提示

樣例 $1$ 中原信息中的字母 'AA' 和 'BB' 對應相同的密字，輸出 Failed。

2. 思路

我們可以直接用一個一維數組（桶），來存儲密碼（下標）和對應的原碼（數據）。

3. 參考答案

#include <iostream>
#include <string>
using namespace std;string y, m, ans; // y: 原碼 m: 密碼 ans: 密碼答案
int cnt = 0; // 記錄出現次數
int bm[130]; // bm[]: 編碼存儲
bool yused[130]; // yused[]: 記錄原下標是否被使用過int main()
{cin >> m >> y >> ans;// 特例int len = m.length();if (len < 26) // 密碼長度<26直接輸出{cout << "Failed";return 0;}// 正常情況for (int i = 0; i <= len-1; i++){if (bm[m[i]] == 0 && yused[y[i]] == false) // 新的{bm[m[i]] = y[i];cnt++;yused[y[i]] = true;}else{if (bm[m[i]] == y[i]){continue;}else // 誘惑的原碼{cout << "Failed";return 0;}}}if (cnt < 26){cout << "Failed";return 0;}int len2 = ans.length();for (int i = 0; i <= len2-1; i++){cout << char(bm[ans[i]]);}return 0;
}