## Spring Practices 06 心得&題解

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

### 前言

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

今天在家 vir QQ
總共有五題，編號 A~E
AC 順序 : ABCE(D)

D 賽後補的。

### pA

枚舉分割起點，每次就暴力掃過一次(其實可以前綴和壓掉一個 $N$，但本題不需要)，時間複雜度 $\Theta(N^2)$。

// 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 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;
mt19937 rng(114514);

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

int main() {
    IOS;
    int n;
    string s;
    cin >> n >> s;
    for(int i = 1; i < n; i++){
        int o1 = 0, l1 = 0, o2 = 0, l2 = 0;
        for(int j = 0; j < i; j++){
            if(s[j] == 'O'){
                o1++;
            }
            else{
                l1++;
            }
        }
        
        for(int j = i ; j < n; j++){
            if(s[j] == 'O'){
                o2++;
            }
            else{
                l2++;
            }
        }
        if(o1 != o2 && l1 != l2){
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

### pB

構造，讓 $b_i = N - a_i$ 可以製造最大值。

// 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 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;
mt19937 rng(114514);
const int mod1 = 998244353;

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

int main() {
    IOS;
    int n, x;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        cout << n + 1 - x << ' ';
    }
    return 0;
}

### pC

注意到，如果在 $p$ 中 $j$ 在 $i$ 後面，則 $i$ 一定不能是 $j$ 的子孫。
如果答案存在，我們試著使最終 $dist_i = i,i \neq root$。

也就是加入時檢查父節點的 $dist_{f}$ 是否有被跑過，有的話構造 $cost = i - dist_{f}$，這時滿足 $dist_i = i$。

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define i64 long long
#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;
mt19937 rng(114514);
const int mod1 = 998244353;

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}

int main() {
    IOS;
    int t, n, x;
    cin >> t;
    while(t--){
        cin >> n;
        int f[n+1], p[n+1], ans[n+1] = {0}, cost[n+1];
        int ok = 1;
        for(int i = 1; i <= n; i++){
            cin >> f[i];
        }
        for(int i = 1; i <= n; i++){
            cin >> p[i];
            cost[i] = -1;
        }
        
        if(f[p[1]] != p[1]){
            ok = 0;
        }
        else{
            cost[p[1]] = 0;
        }
        
        for(int i = 2; i <= n; i++){
            if(cost[f[p[i]]] < 0){
                ok = 0;
                continue;
            }
            else{
                cost[p[i]] = i;
                ans[p[i]] = i - cost[f[p[i]]];
            }
        }
        
        if(!ok){
            cout << -1 << '\n';
        }
        else{
            for(int i = 1; i <= n; i++){
                cout << ans[i] << ' ';
            }
            cout << '\n';
        }
    }
}

### pD

首先，樹要存在的必要條件是 $a = c-1$，因為 $a$ 影響的是分支數，會一路分到最底，也就是 $c$。

接著，我們盡量把 $2$ 放在上面，這樣可以最小化點，假設 $2$ 放了 $l$ 層，還剩下 $t$ 個空位，則先放入 $b, c$ 的點 (順序其實到最後沒差)，然後如果放不完，答案會是 $l + \lceil \frac{b+c-t}{t + 2(2^{l-1} - t)}\rceil$ ，放的完就剛好是 $l$。

// 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 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;
mt19937 rng(114514);
const int mod1 = 998244353;

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
};


int main() {
    int t;
    cin >> t;
    while(t--){
        int a, b, c, l = 1, p = 1;
        int ok = 1, ans = 0;
        cin >> a >> b >> c;
        int bc = b + c;
        if(c - a != 1) ok = 0;
        while(a > p){
            l ++;
            a -= p;
            p <<= 1;
        }
        int last = p - a;
        //cout << l << ' ' << a << ' ' << p ;
        if(bc <= last){
            ans = l;
        }
        else{
            bc -= last;
            ans = l + (bc - 1)/(2 * a + last) + 1;
        }
        if(!ok){
            cout << -1;
        }
        else{
            cout << ans - 1;
        }
        cout << '\n';
    }
}

### pE

暴力實作，然後可以把字串根據字典序轉成獨一無二的數字，會比較好做。

/ 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 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;
mt19937 rng(114514);
const int mod1 = 998244353;

int rnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

i64 gcd(i64 a,i64 b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

i64 lcm(i64 a, i64 b){
    return a/gcd(a, b) * b;
}
vector<vector<int>> mp (3);
bool vis[3][3];
int ans = 48763;

void walk(int x, int y, int cur, int now){
    if(vis[x][y]) return;
    if(x < 0 || y < 0 || y > 2 || x > 2) return;
    vis[x][y] = 1;
    int base = 1;
    for(int i = 0; i < 2 - cur; i++){
        base *= 3;
    }
    now += base * mp[x][y];
    
    if(cur == 2){
        ans = min(ans, now);
        vis[x][y] = 0;
        return;
    }
    
    for(int i = -1; i < 2; i++){
        for(int j = -1; j < 2; j++){
            if(i == 0 && j == 0) continue;
            walk(x+i, y+j, cur+1, now);
        }
    }
    
    vis[x][y] = 0;
}

int main() {
    IOS;
    string s;
    for(int i = 0 ; i < 3; i++){
       cin >> s;
       for(int j = 0; j < 3; j++){
            mp[i].pb(s[j]-'A');
       }
    }
    
    for(int i = 0 ; i < 3 ; i++){
        for(int j = 0; j < 3; j++){
            walk(i, j, 0, 0);
        }
    }
    
    cout << (char)(ans/9 + 'A');
    cout << (char)((ans/3) % 3 + 'A');
    cout << (char)(ans%3 + 'A');
}