# 學科能力競賽北一區歷屆試題
## 108年
### P1. 電話民調統計
>郭靜黨要以電話民調進行黨內初選，登記初選的人共有N個人，依登記先後順序由小到大編號。電話民調對這N個候選人投票的方式是:由按鍵輸入一串長度為N的按鍵符號所形成的字串，若他要投給第k個候選人，字串的第k個字元就輸入按鍵符號“\*”，否則輸入符號“0”。投票規則是一筆投票中最多可投給 M個候選人。若投票記錄的輸入字串長度不等於候選人的人數、出現“\*”及“0”以外的符號、或是出現大於M個“\*”，都認定為廢票,所投的候選人票數都不計。
>
>請你寫一個程式讀入電訪的投票記錄，算出每個候選人得到的有效票數，依得票數最高到最低列出候選人的名字及票數，若有同票則依姓名開頭字母的英文字母順序由小到大排列，開頭字母若相同再比下一個字母，以此類推。
> **翰入說明**
>(1)第一行為兩個正整數N及M，代表候選人數N，以及一筆投票中最多可投的人數M，以空白區分。$(M \leq N \leq 100)$
>
>(2)接下來緊接著的N行，每一行有一個英文字串，各表示一個候選人名字。字串長度最長為10。
>
>(3)再下一行為一個正整數，代表全部投票的人數P，緊接著P行，每一行有一個字串，表示各投票輸入的符號字串內容。$(P \leq 5000)$
> **翰出說明**
>(1)對每一組測試資料，統計各候選人得到的有效票數，並依得票數最高到最低，在每一行列印候選人名字及他的得票數，以一個空白區分。
> 輸入範例一
>```
>2 1
>Panda
>Cat
>5
>0*
>1*
>*0
>0*
>#0
>```
>輸出範例一
>```
>Cat 2
>Panda 1
>```
>輸入範例二
>```
>3 2
>Sam
>Tony
>Tom
>5
>*00
>**1
>***
>0*0
>00*
>```
>輸出範例二
>```
>Sam 1
>Tom 1
>Tony 1
>```
**解題策略:**
~~很基礎的字元、字串的判斷，硬解就對了~~
解題的重點在於讀懂題目，我們先從題目中找出需要解決的問題
要做的最主要有兩個
- 計算得票數並排序
- 對名字做排序
同時要處裡的例外其況有
- 存在非法輸入
- 投票者投票數超過規定
通過結構**struct**同時儲存名字和票數方便最後進行排序當然二維陣列也可以，
基本上排除非法輸入沒什麼好解釋的，就只是判斷而已
比較特別的是這裡利用了**vecttor**的**sort**函數進行排列
```cpp=
sort(candidates.begin(), candidates.end(), [](Candidate a,Candidate b){
if (a.votes != b.votes) {
return a.votes > b.votes;
}
return a.name < b.name;
});
```
格式為
```
sort(起始位置,結束位置"不包含此位置",[比較目標"空為自身"](兩變數"根據宣告順序區分前後項"){
回傳排序"判斷條件";
});
```
為在票數相同時對名字做排序，在回傳前透過判斷票數是否相同來決定排序的條件，最後輸出即可
**Code:**
```cpp=
#include<bits/stdc++.h>
using namespace std;
struct Candidate {
string name;
int votes{0};
};
int main(){
int N,M,P,O=0;
string tp;
cin>>N>>M;
vector<Candidate> candidates(N);
for(int i=0;i<N;i++) cin>>candidates[i].name;
vector<int> point;
cin>>P;
for(int i=0 ;i<P;i++){
cin>>tp;
if(tp.size()==N){
for(int c=0;c<N;c++){
if(tp[c]=='0') continue;
else if(tp[c]=='*'){
O++;
point.push_back(c);
}
else{
point.clear();
break;
}
}
if(O>0&&O<=M) for(int ip:point) candidates[ip].votes++;
}
O=0;
point.clear();
}
sort(candidates.begin(), candidates.end(), [](Candidate a,Candidate b){
if (a.votes != b.votes) {
return a.votes > b.votes;
}
return a.name < b.name;
});
for (const Candidate candidate : candidates) {
cout <<candidate.name << " " << candidate.votes <<endl;
}
}
```
估算複雜度為$O(PN + NlogN)$。 當P和N都很大時，PN項會佔主導，所以可以簡化為$O（PN）$。
*--Written By Chen*
---
### P2. 採草莓問題
> 王先生有個草莓園，這個草莓園的形狀是階梯狀（如下圖一）
> 
> 王先生把這個草莓園依照階梯狀，水平及垂直切割成方形區城。每個區域生長的草莓數目總數，可以透過各區的攝影機回傳，如各方形區域中顯示的數目。王先生買了一個機器人幫忙採收草莓，草莓園的入口在左上角，出口在右下角。採收機器人到每一個方形區域採收後，只能設定向南方或向東方移動到下一區域（東西南北的相對位置如圖二）。王先生想透過一次的路徑採收到最多的草莓，從入口到出口，請你寫一個程式找出該如何設定機器人的移動路徑。
以上圖為倒，機器人的移動路徑應設定為“東南南南東東南東東東”（如圖三），可採收到最多草莓41顆。
> **翰入說明**
> 1. 第一行為一個正整數 $n$ $( 1 ≤ n ≤ 100)$，代表共有口排階梯方格。
> 2. 第二行到第 $n+1$ 行，每行有大個正整數( $k$ 從 1 到 $n$)表示每排*個方格區域中的草莓數，$草莓數
<=10。$
> **翰出說明**
> 1. 第一行輪出一個由 $S$ 及 $E$ 字母形成的宇串，表示襲投定機器人的移動路徑，其中 $S$ 表示向南移動，$E$ 表示向東移動
> 2. 第二行翰出所能採收的最多草莓總數。
> 3. 若有雨條路徑可採收的草莓總数相同，請输出先往来移動的路徑。
> 輸入範例一
> ```
> 5
> 5
> 4 8
> 3 2 1
> 8 3 4 5
> 2 2 6 3 5
> ```
> 輸出範例一
> ```
> ESSSEESEEE
> 41
> ```
> 輸入範例二
> ```
> 3
> 3
> 2 1
> 1 2 4
> ```
>
> 輸出範例二
> ```
> ESESEE
> 12
> ```
**解題策略：**
這題為基礎的 DP (動態規劃) 問題，掃描陣列後，建立一個新的陣列來存放已經計算的格子。從上到下逐格判斷 *(Top-Down)*，已經計算的上面那一格，和已經計算的左邊那一格的數字大小，將最大的數字存放在新的陣列中，直到最後一個位置就會得出答案。
**Code:**
```cpp=
int main() {
int n;
cin >> n;
vector<vector<int>> map(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < i + 1; j++) {
cin >> map[i][j];
}
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
dp[n - 1][i] = map[n - 1][i] + (i + 1 < n ? dp[n - 1][i + 1] : 0);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = i; j >= 0; j--) {
dp[i][j] = map[i][j] + ((j + 1 < i + 1) ? max(dp[i][j + 1], dp[i + 1][j])
: dp[i + 1][j]);
}
}
string path = "ES";
int currentJ = 0;
for (int i = 1; i < n; i++) {
for (int j = currentJ; j < i + 1; j++) {
if (j + 1 > i + 1) {
path += "S";
currentJ = j;
break;
} else if (i + 1 >= n)
path += "E";
else if (dp[i][j + 1] > dp[i + 1][j])
path += "E";
else if (dp[i][j + 1] < dp[i + 1][j]) {
path += "S";
currentJ = j;
break;
} else
path += "E";
}
}
cout << path << "\n" << dp[0][0];
}
```
估算複雜度為$O(NM)$
*--Written By LIN*
---
### P3. 解碼問題
>古典密碼是密碼學中的其中一個類型，其大部分加密方式都是利用替換式密碼或移項式密碼，有時則是兩者的混合。其於歷史中經常使用，但現代已經很少使用，大部分的已經不再使用。
>根據維基百科「替換式密碼」定義為代换密碼是字母(或是字母群)作有系統的代換，直到訊息被替換成其它難以解讀的字。
>阿華以此為出發點想了一個替換式密碼其規則為: 選擇一個單字或是短片語並去除所有的空格和重複的字母，接著把它當作密碼字母集的開頭。最後記得去除掉關鍵字的字母把其它字母接續排序。
>例如，如果關鍵字是cipher，則密碼字母表是這樣寫的:
>定義一般字母:
>```
>abcdefghijklmnopqrstuvwxyz
>```
>密碼字母:
>```
>cipherstuvwxyzabdfgjklmnoq
>```
>請你寫出一個程式,將此加解密法實做出來。
> **翰入說明**
>
>(1)第一行為一正整數N，N$\in${0,1}，0代表解密、1代表加密。
>
>(2) 第二行為關鍵字，關鍵字僅會以小寫提供。
>
>(3) 第三行為需加密或解密的字串。
>
> **翰出說明**
>
>(1) 解碼出原密碼內容字串,請將題目的大小寫維持輸出。
>輸入範例一
>```
>0
>cipher
>Texxa Mafxh
>```
>輸出範例一
>```
>Hello World
>```
>輸入範例二
>```
>1
>happy birthday
>HowAreYou
>```
>輸出範例二
>```
>TlwHobZlu
>```
**解題策略:**
又是一題簡單的字元、字串判斷，先建立一個A到Z的字串，空格、刪除關鍵字及重複的字母後依照順序串接在關鍵字後面就會成為一個密碼表，接下只要對照密碼表輸出好了，但要記得處裡大小寫的問題。
**Code:**
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<char> alph;
for(int i=0;i<26;i++){
alph.push_back(char(i+97));
}
int mode,dis,num;
cin>>mode;
cin.ignore();
string cipher;
getline(cin,cipher);
cipher.erase(remove_if(cipher.begin(), cipher.end(), ::isspace), cipher.end());
string ipt;
for(char i:cipher){
for(int j=0;j<26;j++){
if(i==alph[j]){
alph.erase(alph.begin()+j);
}
}
}
for(int i=0;i<cipher.size();i++){
vector<char>::iterator point=find(alph.begin(),alph.end(),cipher[i]);
if(point==alph.end()){
alph.insert(alph.begin()+num,cipher[i]);
num++;
}
}
vector<char>::iterator point=find(alph.begin(),alph.end(),alph[a-1]+1);
dis=distance(alph.begin(),point);
for(int i=0;i<dis-a;i++){
alph.push_back(alph[a]);
alph.erase(alph.begin()+a);
}
getline(cin,ipt);
switch (mode)
{
case 0:
for(int i:ipt){
if(i>=97&&i<=122){
vector<char>::iterator op=find(alph.begin(),alph.end(),char(i));
cout<<char(distance(alph.begin(),op)+97);
}
else if (i>=65&&i<=90)
{
vector<char>::iterator op=find(alph.begin(),alph.end(),char(i+32));
cout<<char(distance(alph.begin(),op)+65);
}
else if(i==32){
cout<<' ';
}
}
break;
case 1:
for(int i:ipt){
if(i>=97&&i<=122){
cout<<alph[i-97];
}
else if (i>=65&&i<=90)
{
cout<<char(alph[(i-65)]-32);
}
else if(i==32){
cout<<' ';
}
}
break;
}
}
```
假設字串長度為m，估算複雜度為$O(mn+m+3n+2)$常數因子和低階項可忽略，可以直接簡化成$O(mn)$。 這顯然是一個非常需要優化的程式，但我就是懶。
*--Written By Chen*
---
### P4. 戳戳樂問題
> 老王在夜市租了一個攤位在賣戳戳樂，一開始老王基於心情喜好隨機置放獎品，經過一段時間後的成本持續虧損，他發現許多客人都猜測建續性的格子中有放置獎品，他打算更換獎品放置方式，規劃方式為：任兩個獎品都不能處於同一條横行，縱行或 45 度斜線上。
> 
> 當中 $x$ 表示獎品放置位置，方框標示代表不符合規劃的點。
今天你身為一位程式設計師，請設計一個程式幫老間檢查放置禮物哪些獎品位置不符合他所期待的規則，並由左至右、由上至下標出點座標，最左上角之點座標為(0,0)。
> **翰入說明**
> 1. 第一行為兩個正整數 $M$ 及 $N$，分別代表資料的行數跟列數。
> 2. 接下來 $M$ 行代表每列的戳戳樂獎品放置處，小寫英文字母 $O$ 代表空格，小寫字母 $x$ 代表獎品放置的位登。
> **翰出說明**
> 請由左至右、由上而下輸出非法的點座標，各組座標以括號包圍。
>輸入範倒一
> ```
> 5 6
> X00000
> OOX00X
> 0000X0
> OX0000
> 000X00
>```
>輸出範例一
>```
>(1,2)(1,5)(2,4)
>輸入範例二
>```
>2 3
>oxo
>xoo
>```
>輸出範例二
>```
>(0,1)(1,0)
>```
**解題策略:**
先建立一個座標系，並判斷每一個座標與每一個座標的斜率。可以得知不合法的位置關係存在以下情況:
- 斜率為 0
- 斜率為 1
**Code:**
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct point {
float x;
float y;
};
int main() {
int M, N; // M = y, N = x
cin >> M >> N;
vector<point> points;
vector<point> illegalPoints;
for (float i = 0; i < M; i++) {
int repeat = 0;
string temp;
cin >> temp;
for (float j = 0; j < temp.size(); j++) {
if (temp[j] == 'x') {
points.push_back({i, j});
illegalPoints.push_back({i, j});
repeat++;
}
}
if (repeat == 1) illegalPoints.pop_back();
}
for (auto& i : points) {
for (auto& j : points) {
if (i.x == j.x && i.y == j.y) continue;
// 鉛直線
if (i.y == j.y) illegalPoints.push_back({j.x, j.y});
// 斜線
float slope = (i.y - j.y) / (i.x - j.x);
if (slope * slope == 1) illegalPoints.push_back({j.x, j.y});
}
}
sort(illegalPoints.begin(), illegalPoints.end(),
[](const point& a, const point& b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
});
illegalPoints.erase(unique(illegalPoints.begin(), illegalPoints.end(),
[](const point& a, const point& b) {
return a.x == b.x && a.y == b.y;
}),
illegalPoints.end());
for (const auto& key : illegalPoints) {
cout << "(" << key.x << "," << key.y << ")";
}
}
```
假設獎品數為$x$，估算複雜度為$O(M2*N2+xMN+xlog(x))$
*--Written By LIN*
---
## 106年
### P1. 數字顛倒問題
>顛倒國的數字表示方法和我們傳統慣用的數字表示法不一樣，在傳統的十進位數字系統中，由右至左的數字表示個位數、十位數、百位數、千位數...等，但顛倒國卻是以由左至右的數字代表個位數、十位數、百位數、千位數...等，以三位數123為例，對我們來說，其值為一百二十三，可是以顛倒國的數字來看，其值為三百二十一。
>小明到顛倒國購買物品，他怕身上的現因不夠，需先試算物品購買總額，但是顛倒國的價錢表示法和小明傳統的經驗不同，讓小明覺得很困擾，請你幫小明計算出所需金額，結果以傳統的十進位數字系統視之。
> **翰入說明**
>1. 第一行為一個正整數$n(1\leq n\leq100)$，代表總共有$n$個物品
>2. 第二行到第$n+1$行，代表編號1到$n$的物品價格，每一行有一個正整數$p(1 \leq p \leq 1000)$。
> **翰出說明**
> 輸出一個數字，代表所有物品價錢的總額。
>輸入範倒一
>```
>4
>101
>203
>85
>11
>```
>輸出範例一
>```
>472
>```
>輸入範例二
>```
>6
>45
>12
>333
>155
>333
>234
>```
>輸出範例二
>```
>1724
>```
**解題策略:**
簡單來說就是把1到$n$個物品的價格反轉之後的數全部累加起來，至於要把數字翻轉，最簡單的方法就是對該數取模 $mod$ 當成新數的最後一位，然後再刪除原數的最後一位，聽不懂嗎，沒事，看程式
**Code:**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main ( ) {
int n , o , temp , rem , re ;
cin >> n ;
for ( int i = 0 ; i < n ; i ++ ) {
cin >> temp ;
re = 0 ;
while ( temp != 0 ) {
rem = temp % 10 ;
re = re * 10 + rem ;
temp /= 10 ;
}
o += re ;
}
cout << o ;
}
```
估算複雜度為$O(n)$
*--Written By Chen*
---
### P2. 訊息編碼
Sign in with Wallet
Connect another wallet