## Spring Practices 05 心得&題解

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

### 前言

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

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

### pA

首先注意到，如果一個字串裡有 `00` `11` 這種字串肯定是回文的，如果有 `010` `101` 這種也是不行的，那我們會發現當字串長度 > 3 一定無解，在 字串長度 2 以下的 case 很少，就判一下即可。

// 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 t, n;
    string s;
    cin >> t;
    while(t--){
        cin >> n >> s;
        if(s == "0" || s == "1" || s == "01" || s == "10"){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
}

### pB

因為題目 k 只有 10，所以我們可以窮舉 $n$ 以上的數去看他符不符合，窮舉 20 個以內一定會找到一個符合題目條件的。

時間複雜度 $O(t \cdot 20)$

// 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;
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, m;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = n; ; i ++){
            int op = i, bcnt = 0;
            for(int j = 0; j < 10; j++){
                bcnt += op % 10;
                op /= 10;
            }
            bcnt %= m;

            if(bcnt == 0){
                cout << i << '\n';
                break;
            }
        }     
    }
}

### pC

維護一個 pq，然後把所有丟進去，每次選最大的拿出來除以 2 再放回去，直到血條被扣到 0 或裡面沒東西為止，因為每個元素 log 次操作內一定會變成 0。

時間複雜度 $O(n\ log\ n\ log\ a_i)$

#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 t, n, x, z;
    i64 ans = 0, a, b;
    cin >> t;
    while(t--){
       cin >> n >> z;
       ans = 0;
       priority_queue <int> pq;
       for(int i = 0; i < n; i++){
           cin >> x;
           pq.push(x);
       }
       while(pq.size() != 0 && z > 0){
           a = pq.top(); pq.pop();
           z -= a;
           a /= 2;
           ans ++;
           if(a > 0) pq.push(a);
       }
       
       if(z > 0){
           cout << "Evacuate\n";
       }
       else cout << ans << '\n';
    }
}

### pD

先算出敵方需要幾天達到 $Z$，然後接著算出自己在那個天數減 1 後自己方有幾個人，然後需要幾個，就變成 pC ㄌㄌ。

// 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 t, n, u ;
    i64 ans = 0, a, b, x, y, z;
    cin >> t;
    while(t--){
       cin >> n >> a >> b >> x >> y >> z;
       ans = 0;
       priority_queue <int> pq;
       for(int i = 0; i < n; i++){
           cin >> u;
           pq.push(u);
       }
       
       i64 day = (z - b - 1) / y;
       i64 need = z - day * x - a;
       while(pq.size() != 0 && need > 0){
           a = pq.top(); pq.pop();
           need -= a;
           a /= 2;
           ans ++;
           if(a > 0) pq.push(a);
       }
       
       if(need > 0){
           cout << "RIP\n";
       }
       else cout << ans << '\n';
    }
}

### pE

我們對於每個團體裡的人都倆倆合併，然後注意的是如果對於一個團體裡所有數對 $(x,y)$ 都做 union 會退化成 $O(k^2)$，而其實我們只要第 i 個和第 i+1 個做 union 就好。

最後再根據各自所屬團體計算裡面有幾個。

時間複雜度 $O(n+\sum k_i \cdot α(n))$

#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;

const int maxn = 5e5 + 5;
int dsu[maxn], sz[maxn];

int find(int x){
    if(dsu[x] == x){
        return x;
    }
    return dsu[x] = find(dsu[x]);
    
}
void onion(int f, int s){
    int tx = find(f);
    int ty = find(s);
    dsu[tx] = ty;
}

int main() {
    IOS;
    int n, m, k, p, x;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        dsu[i] = i;
    }
    for(int i = 1; i <= m; i++){
        cin >> k;
        for(int j = 0; j < k; j++){
            cin >> x;
            if(j == 0) {
                p = x;
                continue;
            }
            onion(p, x);
            p = x;
        }
    }
    
    for(int i = 1; i <= n; i++){
        sz[find(i)]++;
    }
    for(int i = 1; i <= n; i++){
        cout << sz[find(i)] << ' ';
    }
}