# 2022 01/09 APCS 題解
## [程式交易](https://zerojudge.tw/ShowProblem?problemid=h081)
存兩個變數 : 現在手上有沒有股票和上一次交易金額
然後暴搜
$O(N)$

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

signed main(){
    int n, d, hav = 1, lst, p, ans = 0;
    cin >> n >> d >> p;
    lst = p;
    for(int i = 1; i < n; i++){
        cin >> p;
        if(hav * (p - lst) >= d){
            if(hav > 0) ans += p - lst;
            hav *= -1;
            lst = p;
        }
    }
    cout << ans << "\n";
    return 0;
}

## [贏家預測](https://zerojudge.tw/ShowProblem?problemid=h082)
開vector存現在場上的人，遞迴下去暴搜
$O(NM)$

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int m;
array<int, 1004> S, T, los;
int fight(vector<int> &P){
    if(P.size() == 1) return P[0];
    int a, b, tmp;
    vector<int> W, F;
    for(int i = 0; i < P.size(); i += 2){
        if(i + 1 >= P.size()){
            W.pb(P[i]);
            continue;
        }
        a = P[i], b = P[i + 1];
        if(S[a] * T[a] < S[b] * T[b]) swap(a, b);
        tmp = S[a];
        S[a] += (S[b] * T[b]) / (T[a] << 1);
        T[a] += (S[b] * T[b]) / (tmp << 1);
        S[b] += S[b] >> 1;
        T[b] += T[b] >> 1;
        los[b]++;
        W.pb(a), F.pb(b);
    }
    for(int f : F){
        if(los[f] >= m) continue;
        W.pb(f);
    }
    return fight(W);
}
signed main(){
    int n, p;
    vector<int> P;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> S[i];
    for(int i = 1; i <= n; i++) cin >> T[i];
    for(int i = 0; i < n; i++){
        cin >> p;
        P.pb(p);
    }
    cout << fight(P) << "\n";
    return 0;
}

## [數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083)
先對每個字串做前綴 hash ，然後把整個字串的 hash value 丟進 set 裏面
接著枚舉每個字串，再對每個字串暴搜籤的一半長度，然後檢查該字串的前綴和後綴是否相同(這邊會用到模逆元)，然後再拿中間的子字串去 set 裏面找有沒有跟他一樣的字串就可以判斷能不能構成「允籤」了
$O(MlenlogM)$

HASH :
把一個字串變成數字
$abcde \ \implies \ ax^0 + bx^1 + cx^2 + dx^3 + ex^4$
其中 $x$ 可以是任何大於字母範圍的數字
且由於 hash value 可能會過大，變數存不下，所以通常都會拿去模一個很大但是塞得下的數字
$abcde \ \implies \ (ax^0 + bx^1 + cx^2 + dx^3 + ex^4) mod \ m$
通常 $x$ 和 $m$ 都會選擇質數，比較不容易發生不同字串 hash 出來長一樣的問題

模逆元 :
根據費馬小定理
$p$ 為質數，則 $x^{p - 1} \equiv 1 (mod \ p)$，$x$ 可為任何數
因此 $x^{p - 2}$ 就相當於 $\frac{1}{x}$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 2147483647;
array<int, 104> C, I;
array<string, 50004> S;
array<array<int, 104>, 50004> H;
array<set<int>, 104> Z;
int pow(int x, int k){
    int ans = 1;
    for(int i = 1; i <= k; i <<= 1){
        if(i & k) ans = ans * x % mod;
        x = x * x % mod;
    }
    return ans;
}
void build(int n){
    C[0] = I[0] = 1;
    for(int i = 1; i <= n; i++){
        C[i] = 29 * C[i - 1] % mod;
        I[i] = pow(C[i], mod - 2);
    }
}
void hsah(string &s, int p){
    int n = s.size();
    H[p][0] = s[0] - 'a' + 1;
    for(int i = 1; i < n; i++){
        H[p][i] = (H[p][i - 1] + (s[i] - 'a' + 1) * C[i]) % mod;
    }
    Z[n].insert(H[p][n - 1]);
}
int see(int p, int l, int r){
    if(!l) return H[p][r];
    return ((H[p][r] - H[p][l - 1] + mod) % mod) * I[l] % mod;
}
int match(int m){
    int ans = 0, n;
    for(int i = 0; i < m; i++){
        n = S[i].size();
        for(int j = 1; j < n; j++){
            if(2 * j <= n) continue;
            if(see(i, 0, n - j - 1) == see(i, j, n - 1)){
                if(Z[2 * j - n].find(see(i, n - j, j - 1)) != Z[2 * j - n].end()) ans++;
            }
        }
    }
    return ans;
}
signed main(){
    int m;
    cin >> m;
    build(101);
    for(int i = 0; i < m; i++){
        cin >> S[i];
        hsah(S[i], i);
    }
    cout << match(m) << "\n";
    return 0;
}

## [牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)
對值域二分搜，看海報最高能貼多高
$O((N + K)logC)$

#include <bits/stdc++.h>
using namespace std;
array<int, 50004> W;
array<int, 200004> H;
int post(int n, int h){
    int con = 0, cnt = 0;
    for(int i = 0; i < n; i++){
        if(!W[cnt]) break;
        if(H[i] >= h) con++;
        else con = 0;
        if(con >= W[cnt]){
            con = 0;
            cnt++;
        }
    }
    return cnt;
}
int BIS(int n, int k){
    int l = 0, r = 1e9, mid;
    while(l != r){
        mid = ((l + r) >> 1) + 1;
        if(post(n, mid) < k) r = mid - 1;
        else l = mid;
    }
    return l;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> H[i];
    for(int i = 0; i < k; i++) cin >> W[i];
    cout << BIS(n, k) << "\n";
    return 0;
}