## Spring Practices 04 心得&題解

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 前言

因為是學校練習用的，不知道題目能不能公開，但還是寫個心得好了。

總共有五題，編號 A~E，以下照 AC 順序:

### pA

這題想成位元運算就好，弄到最低 bit 不是 1 就結束。

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;

int main() {
    IOS;
    int n, ans = 0;
    cin >> n;
    while(!(n&1)){
        n >>= 1;
        ans++;
    }
    cout << ans << '\n';
}

### pB

我用 int128 做，就不用怕 overflow，如果超過 $10^{18}$ 就立刻歸零，要注意的是要找裡面有沒有 0。

有另個方法是取 log，去估看看他會不會 $10^{18}$，超過就可以不要算。

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;

//i128 io template
inline void read(i128 &n){
    i128 x = 0,f = 1;
    char ch = getchar();
    while(ch < '0'||ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    n = x * f;
}

inline void print(i128 n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n % 10 + '0');
}

int main() {
    IOS;
    bool cero = 0;
    int n;
    i64 in;
    i128 now = 1;
    cin >> n;
    while(n--){
        cin >> in;
        now *= in;
        if(now > (i128)1e18){
            now = 0;
        }
        if(in == 0) cero = 1;
    }
    if(!cero && !now) now = -1;
    print(now);
}

### pC

排序陣列，用雙指針找，當左指標右移的時候，因為往右數值單調遞增，右指標一定是適當的往左調整(找更小的數)，時間複雜度 $O(n)$，要注意不能找重複的。

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;

int main() {
    IOS;
    int n, a, x;
    cin >> n >> a;
    pii s[n];
    for(int i = 0; i < n; i++){
        cin >> x;
        s[i] = make_pair(x, i);
    }
    sort(s, s+n, cmp);
    for(int i = 0, ptr = n-1; i < n; i++){
        while(ptr != 0 && (s[i].f + s[ptr].f > a || ptr == i)) ptr--;
        if(s[i].f + s[ptr].f == a && ptr != i){
            cout << s[i].s+1 << ' ' << s[ptr].s+1 << '\n';
            return 0;
        }
    }
    cout <<  "IMPOSSIBLE\n";
    return 0;
}

### pD

首先先離散化重新編號，把 $a_i \rightarrow b_i$，其中 $1 \le b_i \le n$，造出序列 $b(x)$。

定義一個序列 $c(x)$ ，如果現在 sliding window 裡有 $x$，則 $c(x) = 1$，否則 $c(x) = 0$。

維護一個 BIT (Binary Indexed Tree)，維護一個對於陣列 $c(x)$ $1 \sim n$ 項的前綴和 $p(x)$，也就是 $p(i) = \sum_{k=1}^i c_k$，並且能 $O(log\ n)$ 做加值操作。

最後，在這上面二分搜即可，找到 $c_i$ 前綴有一半大小的最小值 $m$ ，也就是最小的 $m$ 滿足 $p(m) \ge \lceil k/2 \rceil$ 再轉回 $a_i$ 的值就行。

時間複雜度 $O(n\ log^2\ n)$。

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;

// binary indexed tree
const int maxn = 2e5+5;
i64 bit[maxn];

void update(i64* a, int x, int v){
    for(int i = x; i < maxn; i += (i&(-i))){
        a[i] += v;
    }
}

i64 query(i64* a,int x){
    i64 cnt = 0;
    for(int i = x; i > 0; i -= (i&(-i))){
        cnt += a[i];
    }
    return cnt;
}

int main() {
    IOS;
    int n, k, x;
    cin >> n >> k;
    
    pii s[n];
    int u[n], v[n+1];
    for(int i = 0; i < n; i++){
        cin >> x;
        s[i] = make_pair(x, i);
    }
    
    sort(s, s+n, cmp);
    for(int i = 0; i < n; i++){
        u[s[i].s] = i + 1; 
        v[i + 1] = s[i].f;
    }
    
    for(int i = 0; i < k-1; i++){
        update(bit, u[i], 1);
    }
    
    for(int i = k-1; i < n; i++){
        update(bit, u[i], 1);
        if(i >= k) update(bit, u[i-k], -1);
        int l = 1, r = n;
        int tar = (k+1) / 2;
        while(l != r){
            int mid = (l + r) / 2;
            if(query(bit, mid) >= tar){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        cout << v[l] << ' ';
    }
}

### pE

priority queue

嗷嗷待補

// Author : rickytsung
// Problem : 
// Date : 
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#define i128 __int128
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define f first
#define s second
#define pb(x) push_back(x)
using namespace std;

int main() {
    IOS;
    int n, x;
    i64 ans = 0, a, b;
    while(1){
       cin >> n;
       ans = 0;
       if(!n) return 0;
       priority_queue <int, vector<int>, greater<int>> pq;
       for(int i = 0; i < n; i++){
           cin >> x;
           pq.push(x);
       }
       while(pq.size() > 1){
           a = pq.top(); pq.pop();
           b = pq.top(); pq.pop();
           ans += a + b;
           pq.push(a + b);
       }
       cout << ans << '\n';
    }
}