## Spring Practices 06 心得&題解

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

### 前言

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

今天在家 vir QQ
總共有五題，編號 A~E

### pA

找不比輸入 $n$ 大的最高的 $10^x$，那答案會是 $n-10^x$。

// 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, t, p;
    cin >> t;
    while(t--){
        cin >> n;
        p = 1;
        while(10*p <= n) p *= 10;
        cout << n - p << '\n';
    }
}

### pB

怪怪輸出題目。

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

//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 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, t, p;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                for(int k = 0; k < n; k++){
                    if(!(i&1))cout << "##";
                    else cout << "..";
                    k++;
                    if(k >= n)break;
                    if(!(i&1)) cout << "..";
                    else cout << "##";
                }
                cout << '\n';
            }
        }
    }
}

### pC

如果兩個點有一個維度的數值一樣，則它們中間有一個邊，數有幾個連通塊，答案會是連通塊-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 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 vis[1005];
vector<vector<int>> E(1005);

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

void walk(int now){
    if(vis[now]) return;
    vis[now] = 1;
    for(auto &i:E[now]){
        walk(i);
    }
}

int main() {
    IOS;
    int n;
    cin >> n;
    int xy[n][2];
    for(int i = 0; i < n; i++){
        cin >> xy[i][0] >> xy[i][1];
    }
    
    for(int z = 0; z <= 1; z++){
        for(int i = 0 ; i < n; i++){
           for(int j = 0 ; j < n; j++){
                if(xy[i][z] == xy[j][z]){
                    E[i].pb(j);
                }
            } 
        }
    }
    int ans = -1;
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            ans++;
            walk(i);
        }
    }
    cout << ans << '\n';
}

### pD

同 pC，用上禮拜 E 的方法壓邊的數量。

// 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 vis[200005];
vector<vector<int>> E(200005);

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;
}
void walk(int now){
    if(vis[now]) return;
    vis[now] = 1;
    for(auto &i:E[now]){
        walk(i);
    }
}

int main() {
    IOS;
    int n;
    cin >> n;
    int xy[n][26];
    memset(xy, 0, sizeof(xy));
    string s;
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0 ; j < s.length(); j++){
            xy[i][s[j] - 'a'] = 1;
        }
    }
    
    for(int z = 0; z < 26; z++){
        int pre = -1;
        for(int i = 0 ; i < n; i++){
            if(!xy[i][z]) continue;
            if(pre != -1){
                E[pre].pb(i);
                E[i].pb(pre);
            }
            pre = i;
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            ans++;
            walk(i);
        }
    }
    cout << ans << '\n';
}

### pE

假設輸出有 n 個點，因為題目編號沒照順序，要離散化。
檢查 :
1. 是否連通
2. 是否是 n-1 個邊
3. 是否一個點的父節點不超過 1 個。

// Author : rickytsung
// Problem : 
// Date : 
#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;
}

/*
6 8 5 3 5 2 6 4
5 6 0 0

8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0

3 8 6 8 6 4
5 3 5 6 5 2 0 0

-1 -1
*/

int cnt = 0;
void walk(vector<vector<int>> &T, bool* vis, int now){
    if(vis[now]) return;
    vis[now] = 1;
    cnt++;
    for(auto &i:T[now]){
        walk(T, vis, i);
    }
}

int main() {
    //cin.ignore();
    int t = 1, a, b, pa, pb;
 
    while(1){
        int ok = 1;
        int edge = 0, vertex = 0;
        set<int> fa;
        map<int,int> has;
        vector<vector<int>> T(200005);
        bool vis[200005] = {0};
        while(1){
            cin >> a >> b;
            if(a < 0){
                return 0;
            }
            if(a == 0){
                break;
            }
            edge++;
            if(has.find(a) == has.end()){
                has[a] = vertex++;
            }
            if(has.find(b) == has.end()){
                has[b] = vertex++;
            }
            pa = has[a];
            pb = has[b];
            
            T[pa].pb(pb);
            T[pb].pb(pa);
            if(a == b) ok = 0;
            if(fa.count(b)){
                ok = 0;
            }
            fa.insert(b);
        }
        if(edge != vertex - 1){
            ok = 0;
        }
        cout << "Case " << t++ << " ";
        cnt = 0;
        walk(T, vis , 0);
        if(vertex == 0 || (fa.size() == vertex - 1 && ok && cnt == vertex)){
            cout << "is a tree.\n";
        }
        else{
            cout << "is not a tree.\n";
        }
    }
}