# 12/29 期末考

連結
--
https://hackmd.io/@sa072686/HJ6wCaaUp

題目(共四題)
--
* **PA** :

**題意** :
::: success
一張純白的矩形
會有 $N$ 種圖案
然後會有 $M$ 行的需要插入第P種的圖案
:::

**解題思路** :
::: info
先用動態陣列創造出矩形 ==(一定要將每一格先初始化為`'.'`**!!!**==
~~不要問我為什麼 問了就是辛酸血淚史XD~~
再來是創造出一個三維陣列去儲存pattern ([第幾種圖案][x][y])
接著是輸入進去 (這邊我用的是暫存二維陣列 'Cause ~~我就單純求穩~~
之後就簡單多了 輸入m行 然後左上(x,y)第幾種圖形
這邊第幾種記得要-1轉成index不然會錯
放進去矩形時也要小心邊界
:::

:::spoiler **程式碼**

    #include <iostream>
    #include <vector>
    #include <map>

    #define X first
    #define Y second

    using namespace std;

    int main() {
        int r, c;
        cin >> r >> c;
        vector<vector<char>> list(r, vector<char> (c, '.'));
        map<int,vector<vector<char>>> pattern;
        vector<pair<int,int>> patternn;
        int n; cin >> n;
        for(int i = 0; i < n; i++) {
            int ri, ci;
            cin >> ri >> ci;
            vector<vector<char>> temp(ri, vector<char> (ci, '.'));
            for(int j = 0; j < ri; j++) {
                for(int k = 0; k < ci; k++) {
                    cin >> temp[j][k];		
                }
            }
            pattern[i] = temp;
            patternn.push_back({ri,ci});
        }
        int m; cin >> m;
        while(m--) {
            int q, t, p;
            cin >> q >> t >> p;
            p--;
            int x = 0, y = 0;
            for(int i = q; i < min(r,q+patternn[p].X) ; i++) {
                y = 0;
                for(int j = t; j < min(c,t+patternn[p].Y); j++) {
                    list[i][j] = (pattern[p])[x][y];
                    y++;
                }
                x++;
            }
        }

        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                cout << list[i][j];
            }
            cout << endl;
        }

    }

:::

**解題心得** :
:::warning
因為我都習慣先從第一題開始做起
所以每次遇到難的題目都不會跳題
~~我才每次都拿不到其他題的首殺XD~~
這次遇到硬碴 三維陣列
其實我是第一次遇到這種三維陣列的題目
所以一開始是有點矇的
~~不過想說期末考就算考零分也不會被當就繼續寫下去了~~
不過這題寫完的成就感非常高 推爆
:::

* **PB** :

**題意** :
::: success
輸入r、s 方程式代入
求得之後四捨五入為整數
:::

**解題思路** :
:::info
cmath解沒難度
:::

:::spoiler **程式碼**

    #include <iostream>
    #include <iomanip>
    #include <cmath>

    using namespace std;

    int main() {
        int r;
        double s;
        while(cin >> r >> s) {
            int v = 0;
            v = sqrt((r*(s+0.16))/0.067)+0.5;
            cout << v << endl;
        }
    }

:::

**解題心得** :
:::warning
沒看到四捨五入 :disappointed:
:::

* **PC** :

**題意** :
:::success
給定一個字串S(有N個字元)
將此S字串排序成回文
假如沒辦法就輸出無解
:::

**解題思路** :
:::info
首先從字串中取出英文字母對應的次數
我是用`<map>`的解法 ~~我平常都這樣用ㄏㄏ~~
接著分析到底有沒有解
假如有二組以上的字母是奇數
那麼就是無解 不難理解
JUST LIKE THIS : 
之後就將所有字母砍半
(包括奇數的字母
後面就無腦排入前段陣列
再來就輸出前段 (中間) 後段
後段為前段倒反
中間是奇數字母(可有可無)

:::spoiler **程式碼**

    #include <iostream>
    #include <vector>
    #include <map>
    #include <algorithm>

    #define X first
    #define Y second

    using namespace std;

    int main() {
        string a;
        cin >> a;

        map<char, int> alphas;
        for(const char c : a) {
            alphas[c]++;
        }

        int sum = 0;
        char lll = ' ';
        int hhh = 0;
        for(const auto d : alphas) {
            if(d.Y%2) {
                sum++;
                hhh--;
                lll = d.X;
            }
            alphas[d.X] /=2;
            hhh+=d.Y;
        }

        if(sum >1) {
            cout << "NO SOLUTION" << endl;
            return 0;
        }
        else{
            vector<char> flist;
            while(hhh--) {
                for(auto c : alphas) {
                    if(c.Y==0) {
                        continue;
                    }
                    flist.push_back(c.X);
                    alphas[c.X]--;
                }
            }

            for(int i = 0; i < flist.size(); i ++) {
                cout << flist[i];
            }
            if(sum==1) {
                cout << lll;
            }
            for(int i = flist.size()-1; i >=0; i --) {
                cout << flist[i];
            }
        }
    }

:::

**解題心得** :
:::warning
上次偷喵到社長用了 `#define X first` 的用法
~~偷偷學起來~~
這題是屬於沒寫過類似的題型
我提心吊膽地在寫
然後一大堆人寫出來了 ~~壓力超大~~
:::

* **PD** :

**題意** :
:::success
跑馬燈
多組測資
k組字串 ~~雖然有輸入w但我覺得用處不大~~
將k組字串其中字尾字頭假如有子字串相同
省略其一
最終輸出字串大小
:::

**解題思路** :
:::info
`sub_str`
然後要注意一點是須求最大長度的子字串
:::

:::spoiler **程式碼**

    #include <iostream>
    #include <vector>
    #include <cmath>

    using namespace std;

    int main() {
        int n; cin >> n;
        while(n--) {
            int k, w;
            cin >> k >> w;
            vector<string> blist(w);
            for(int i = 0; i < w; i++) {
                cin >> blist[i];
            }
            for(int i = 1; i < w; i++) {
                int p = -1;
                for(int j= 0; j < k; j++) {
                    if((blist[i]).substr(0,j+1) == (blist[i-1]).substr(blist[i-1].size()-1-j, blist[i-1].size())) {
                        p = j;
                    }
                }
                blist[i-1] = blist[i-1].substr(0,blist[i-1].size()-1-p);
                blist[i] = blist[i-1] + blist[i];	
            }

            cout << blist[w-1].size() << endl;
        }
    }

:::

**解題心得** :
:::warning
~~這題沒解出來是個意外~~
> 幫我自己找個藉口 :
當初我慢進教室十分多鐘
然後最近在學DFS、BFS有點頭暈
還有....
算了 我就廢嗚嗚嗚

剩下十分鐘才解
> 看到很多人沒解出來
且一開始忘記`sub_str`怎麼用 (最後是爬老師允許的語法百科找到的
就沒有想寫這題的意思了

雖說最後完成比賽後還是差了一點 ~~EMO了大概一星期~~
才發現我的p = -1 而不是 = 0
~~直接痛哭~~
但最終對於自己有解出這題的概念感到開心
:::

賽後心得
--
這次期末考主要打得是心態
然後遲到 下次不敢了
> ~~我真的忘記今天要考試ㄚㄚㄚ~~

關於題目難度 :
* 第一題很難
* 第三題要思考
* 第四題小細節
* 除了第二題以外真的有挑戰性的感覺

考完試也發現自己又變強了一點 ~~雖然CF 800還是要想很久XD~~

附上照片 :

::: danger
**UPD :**
結果回去刷歷屆考古題
發現沒有一屆是沒破台的
好丟臉QQ
:::