# 考幹考題解 Part 1(?) by yungyao
###### tags: 題解 考幹

只有標題裡面是"XX和她/他的XXXX"是我出的ㄛ
其他題的題解請找其他出題人(雖然好像是我沒寫完，是別人要來找我咩噗
\學弟妹特別強/

## A部分
這部分都語法題
個人是希望每個人都能把這裡的500分都拿到
希望我在這裡講題解的時候大家都有做到><（結果我根本還沒寫完題解，慘

### pA3
tags : `string` `implementation` `constructive algorithm`
就是基本的回文性質跟簡單的字串相關語法
理論上分兩個Subtask，也就是25分解跟100分解

但cf不給連續給分，所以可能會有各種奇怪ㄉ分數（像py被卡常之類的www
總之我們只要考慮一個簡單的greedy就好

對於任意一組 $s[i] \neq s[n-i+1]$ ，我們都修改其中任意一項
透過迴文的性質可以很容易的證明做這個改動是好的greedy策略

所以我們只要跑過去數有幾個相異就好了
而滿分解要你輸出改過的字串，也是直接改一下就好了w

:::spoiler AC Code

using namespace std;
#include <iostream>

int main(){
    int n;
    string s;

    cin >> n >> s;
    int cnt = 0;
    for (int i=0;i<n/2;++i){
        if (s[i] != s[n-i-1]){
            ++cnt;
            s[n-i-1] = s[i];
        }
    }

    cout << cnt << '\n' << s;

    return 0;
}

:::

### pA4 浩浩和他的夢想柯基
tags : `stl` `queue` `data structure`
這題的定位是裸queue
算是給有在上上學期大社的人的均標，寫不出來代表你太混惹QQ
（Subtask 1應該算低標ㄛ

因此對於這題你基本上只需要知道一件事
就是`std::queue` 裡面可以放任何C++的element，而不限於variable
或者你要自己刻一個queue也是可以接受的啦

#### Subtask 1 (31%)
這個Subtask因為保證每隻柯基的名字都一樣，也就是說你只需要記錄第一隻柯基的名字
再來只要記錄收容所裡面有幾隻柯基就好了

所以31分只要這樣就能拿了

:::spoiler 31 points

int main(){
    int siz = 0;
    int t;
    string corgi;
 
    cin >> t;
    while (t--){
        char cmd;
 
        cin >> cmd;
        if (cmd == '1'){
            cin >> corgi;
            ++siz;
        }
        else if (cmd == '2'){
            int adp;
            cin >> adp;
 
            if (!adp && siz){
                cout << corgi << '\n';
                --siz;
            }
        }
    }
 
    return 0;
}

:::

#### Subtask 2,3,4
這三個Subtask基本上一樣
只是對於有些操作需要注意不同的事項，所以可以一起講

反正就是要維護一個queue資料結構

##### Subtask 2
這個Subtask保證每次對`queue`做`pop`時`queue`都不為空，所以你可以不用檢查是否`empty`

##### Subtask 3
這裡則保證每一次`pop`都可以輸出東西，其實我不知道什麼情況下會寫爛這件事，大概沒判斷好之類的吧，相信拿到這個Subtask的人，其他應該也不難拿XD

##### Subtask 4
就不保證以上兩個Subtask的事，但我相信你們做出這兩個Subtask應該也不難做滿分解啦

:::spoiler 100 points yea

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0);
    int t;
    queue <string> Q;

    cin >> t;
    while (t--){
        int cmd;

        cin >> cmd;
        if (cmd == 1){
            string s;

            cin >> s;
            Q.push(s);
        }
        else if (cmd == 2){
            int k;

            cin >> k;
            if (Q.size()){
                if (!k){
                    cout << Q.front() << '\n';
                }
                Q.pop();
            }
        }
    }

    return 0;
}

:::

## B部分

這裡會稍難一點，但我相信每個人多少都能拿到一些部分分，有來演算法小社跟算法組的學弟妹應該要至少拿一半的分數，加油ㄛ

### pB1 浩浩和果酒和他們的執秘身高差
tags : `double pointer` `binary-search`
先說一下這題的小故事好了，雖然你們最後沒參加到寒訓
但在籌備過程中，某很電的沉思緯學長一直想知道浩浩跟果酒誰比較高
然後我也是十分之有興趣，但他們每次都會避開站在一起，所以我們一直不知道到底誰比較高
直到某次社遊我跟#yououorz在討論題目的時候討論到[TIOJ 1905 最理想的身高差](https://tioj.ck.tp.edu.tw/problems/1905)

剛好那天我們也是努力的想要知道誰比較高，我就想到可以把那題給簡化一下（其實簡化滿多ㄉ，我到現在還不會寫原題XD）當作你們考幹題，於是就有ㄌ這題

還有就是我為了在最後一筆Subtask卡掉`std::set`，所以$n$給到很大，原本是只打算給到$2\times10^5$ㄉ
反正`std::set`跟`std::map`都是很肥的資結，題目想要搞事~~（像是我）~~就會在這邊卡常（之前寫poj的題目ㄉ時候被卡set大腸懷恨在心辣

#### Subtask 1
這裡保證$0 \leq a_i,b_i \leq 400$，換句話說答案也必定小於400

至於要如何檢查一個數$k$能不能是答案，只要檢查$a_i + k \in b$或$a_i - k \in b$，而這件事可以用一個`bool`陣列或`std::bitset`去存一個值是否被包含在$b$之中，反正都會是$O(1)$
複雜度$O(nC)$ (btw其實有開放$O(nC^2)$，因為我懶得卡，而且其實想法差不多XD)

#### Subtask 2
這個Subtask跟前一個很像，只是$n,a_i,b_i$都變大了，$O(nC)$會過肥

但你只需要做一個小小的優化，就是對於$a$也做跟$b$相同的事
用一個`bool`陣列或`std::bitset`存$a$，就不用對$a$枚舉了，現在只需要對$a$的值域枚舉

複雜度可以降到$O(C^2)$

#### Subtask 3
因為$n \leq 2000$，也就是$O(n^2)$可過，而你會發現差一共也只有$n^2$個，因此你只要兩層`for`迴圈包起來就能拿到分數ㄌ

:::spoiler 枚舉亂做拿分數，建北電資北市賽有望

LL a[3000100];

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0);
    int n;
    LL ans = 1e10;

    cin >> n;
    for (int i=n;i--;)
        cin >> a[i];
    for (int i=n;i--;){
        LL x;
        cin >> x;
        for (int j=n;j--;)
            ans = min(ans,abs(x-a[j]));
    }

    cout << ans;

    return 0;
}

:::

但要特別注意的是，最大的差會是$(2^{31}-1) - (-(2^{31}-1)) = 2^{32}-2$，會爆`int`範圍，要用`long long`去儲存。

#### Subtask 4
這應該是所有Subtask裡面最水的
你可以很輕鬆地發現在$min(a) \geq max(b)$的情況下，最小差一定會是$min(a) - max(b)$

而在$a,b$都呈非嚴格遞減下$min(a) = a_n ,max(b) = b_1$
所以你只要輸出$a_n - b_1$就好了
5分get，這5分沒拿到我應該可以相信你根本沒看題目QQ

#### Subtask 5,6
5,6基本上可以一起講，只有常數差異而已
這題的滿分解基本上有兩種，可以二分搜也可以雙指針

對於這種可以任意挑東西的題目，先sort都是一個好的想法
這題也是這樣，我們先對$a$由小到大排列

接著先考慮雙指針的作法（又稱為爬行法
:::spoiler solution 1 double pointer 我用虛擬碼寫，官解的.cpp檔長的有點醜QQ

int n = input()
array a = input()
array b = input()

sort (a)
sort (b)

int64 ans = 2 ^ 32 - 1
iterator b_ptr = b.begin() //對於b的指針
for element in a{
    while *next(b_ptr) < element and next(b_ptr) != b.end()
        b_ptr = next(b_ptr)
    
    ans = min (ans,abs(n - *b_ptr),abs (n - *next(b_ptr)))
}

print (ans)

:::

這份扣的的概念很簡單
在$a,b$都被排序下

我們對於$a$的每一項都去找到其在$b$當中介於哪兩項之間
由於$b$也已經被排序，所以我們如果維護$a$當中的每一項對應到$b$的哪一項，那這件事會遞增
所以我們就可以利用一個雙指針去好好維護他了

由於像這樣對兩個序列各維護一個遞增指針的作法，其實很像在兩個序列上爬行，所以又被稱為爬行法
但雙指針聽起來比較厲害w

然後我們可以來看一下第二種作法，二分搜的核心概念其實是一樣的
我們想要找到$b$的每一項介於$a$($a,b$反過來其實沒差)的哪兩項之間
如果我們已經將$a$排序的話，應該滿容易可以想到二分搜這個作法
基本上大同小異，差別只是實作查找這個過程而已

:::spoiler solution 2 binary search

LL a[1500100];

int main(){
    theyRSOOOOOOOOODIAN
    int n;

    cin >> n;
    for (int i=0;i<n;++i)
        cin >> a[i];
    sort (a,a+n);
    
    LL ans = maxint64;
    for (int j=0;j<n;++j){
        LL b;

        cin >> b;
        int i = lower_bound(a,a+n,b) - a;
        if (i != n)
            ans = min(ans,a[i] - b);
        if (i)
            ans = min(ans,b - a[i-1]);
    }

    cout << ans;

    return 0;
}

:::

這邊順便介紹一下`lower_bound()`這個函式
他屬於標頭檔`algorithm`
他可以直接幫你在一個排序好的陣列上做二分搜
要餵給三個參數
`lower_bound ( iterator start, iterator end, k )`
分別是迭代器起始點、迭代器終點、及查找的值
前兩項類似sort餵的參數，array 的話就給他 `a,a+n`，`vector`的話就給他`a.begin(),a.end()`
而他會回傳一個指標，指向在你給他的範圍中，大於等於$k$的最小值
而如果$k$比全部的值都大，那就會回傳終點（也就是 `a+n` 或 `a.end()`）
那如果你想把他當index用，就像我前面範例code一樣，讓他剪掉起點就好了

### pB2 青蛙和他的青蛙下蛋
tags : `greedy` `bitwise`
這題是我在躺在床上睡不著的時候想到ㄉ

滿分解需要一點數學跟位元運算
不過部分分也是可以用stl做出來的，希望大家都有喇到分><

#### Subtask 1
對於$\exists k(k \in N), n = 2^k$的情形
你可以發現不管怎麼合併，最後一定都能合併成1杯
所以你只要輸出$t$次1，就得到12分ㄌ，開ㄅ開心

#### Subtask 2
那對於其他狀況我們可以考慮真的去模擬合併的過程
至於要如何好好模擬，也不是太麻煩

我們可以發現合併的過程是由小到大
而只要小的還有剩多於兩個把他們合併起來一定是好的

那我們就可以每次看最小的兩個能不能合併
可以的話就合併起來，不行就算了
理論上 $O(n^2),O(n^2logn)$ 都能過，但我也沒試就是ㄌ~~（反正沒人寫這個Subtask~~

#### Subtask 3
跟上一個Subtask類似，但我們可以優化一下找最小兩個的過程
應該滿顯然的用`priority queue`可以解決
複雜度$O(nlogn)$

:::spoiler priority queue sol

inline void solve(){
    int n;
    priority_queue <int,vector <int>,greater <int>> pq;

    cin >> n;
    int cnt = 0;
    REP (n) pq.push(1);

    while (pq.size()){
        int pop = pq.top();
        pq.pop();

        if (pq.empty() || pop != pq.top())
            ++cnt;
        else
            pq.pop(),pq.push(pop * 2);
    }

    cout << cnt << '\n';
}

//這是我ㄉCF模版
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0);
    int t;
    for (cin >> t;t--;) solve();
    return 0;
}

:::

#### Subtask 4
應該不難發現，最後每一杯飲料的大小都是 $2^k$
而由小到大合併後，最後會併成的杯數變會是將 $n$ 以二進位表示後的bit數量

多數人基本上都有想到這件事，接下來就是看你怎麼實作而而已了
這邊介紹一個最簡潔的實作方式
在C\++中有一系列的builtin函式，這些函式不屬於C++ Standard，但幾乎各家編譯器都有將他們實現
而且不需要引入任何標頭檔就能使用

在競賽領域中最常見的就是我們今天的主題`__builtin_popcount()`
這個函式的功能很簡單，就是回傳你給他的數有幾個bit，也就是我這題要求的東西

所以整份code可以精簡如下
:::spoiler 耶 AC

#include <iostream>
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	for(cin >> t;t--;){
		int n;
		cin >> n;
		cout << __builtin_popcount(n) << '\n';
	}
    return 0;
}

:::

### pB3 湯圓和他的交換禮物
tags : `math` `dp`
數學題加打表(你要本機打也是可以啦)

簡單來說透過簡單的排組，你可以知道$n$個人的排列是$n!$種
而你可以發現一個"相同"的排法會被重複計算$n$次
所以$n$個人的相異送法數會是

$\frac{n!}{n} = (n-1)!$

其實是滿簡單的排組啦我覺得，阿反正你們下次段考就是排組，先預習一下ㄅ

接下來就是怎麼實作他了，不過這應該不難

#### Subtask 1
這個Subtask 是讓你可以用手算ㄉ
反正你就自己畫一畫就好了，也才4種輸入，最多的一組解才24
甚至已經給你兩組輸入的解ㄌ，自己畫圖ㄅw

### Subtask 2
這裡你就分別去算跑一次 $(n-1)!$
複雜度 $O(qn)$
:::spoiler 部分分

#include <iostream>
using namespace std;

int mod = 1e9 + 7;
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	for(cin >> t;t--;){
		int n;
		cin >> n;
        
        LL ans = 1;
        for (LL i = 2;i<n;++i)
            ans = ans * i % mod;
        cout << ans << '\n';
	}
    return 0;
}

:::

#### Subtask 3
這裡你會發現 $O(qn)$ 太慢了
但其實你要輸出的東西是固定的，你可以預處理完再一次輸出

這樣複雜度會是 $O(C) + O(q) = O(max(C,q))$
($C$一般是指值域)

:::spoiler AC Code

const LL mod = 1e9+7;
LL ans[1000100];
 
int main(){
    int q;
    ans[0] = 1;
    for (int i=1;i<=1e6;++i){
        ans[i] = i * ans[i-1];
        ans[i] %= mod;
    }
 
    cin >> q;
 
    while (q--){
        int n;
 
        cin >> n;
        cout << ans[n-1] << '\n';
    }
 
    return 0;
}

:::

## C部分
這邊只有一題是我出的啦，寫不出來不要怪我ㄛ

### pC2 絲襪和他的模擬城市
tags : `tree` `greedy` `sort`

這題其實是抄的
原題是Codeforces 的 Goodbye 2020 contest題目，我賽中寫那題就覺得很有趣一定要拿來自己出

反正我相信你們應該沒有人打過那場啦XD

阿原本我應該要認真打題解，但我好懶
所以直接去看原題ㄅ
[Goodbye 2020 pD](https://codeforces.com/contest/1466/problem/D) [題解](https://codeforces.com/blog/entry/86126)

喔然後subtask 1只要把每個點的點權加起來輸出就好
畢竟你根本沒得分w，這個Subtask 滿多人有拿到的，讚