C - Brackets Stack Query

段代碼的功能是處理一系列關(guān)于括號序列的操作（添加或刪除括號），并在每次操作后判斷當前的括號序列是否為有效的括號序列。

我們可以用cnt記錄左括號右括號數(shù)量是否匹配，若為左括號cnt++,若為右括號cnt--,同時用flag記錄每次操作后得到的字符串是否合法（每個左括號對應(yīng)一個右括號）,當flag為0，并且cnt為0時，滿足條件，輸出“Yes”,否則輸出“No”

查看代碼

void solve(){
    int q;
    cin >> q;
    vector<char> s(q + 1);
    int n = 0;
    int cnt = 0;
    int flag = 0;
    int k; char c;
    while(q--){
        cin >> k;
        if(k == 1){
            cin >> c;
            s[++n] = c;
            if(c == '(') cnt++;
            else cnt--;
            if(cnt < 0) flag++;
        }else{
            if(cnt < 0) flag--;
            if(s[n] == '(') cnt--;
            else cnt++;
            n--;
        }

        if(!flag && !cnt){
            cout << "Yes" << endl;
        }else {
            cout << "No" << endl;
        }
    }   
    return ;
}

---

D - 183184

     

根據(jù)上述推導，得到?的范圍。代碼中，我們每次枚舉d，通過sqrt得到區(qū)間中存在平方數(shù)的個數(shù)，最后得到答案

查看代碼

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
#define int long long

int f(int x){
    int t = (int)sqrtl(x);
    //while(t * t > x) t--;
    //while((t + 1) * (t + 1) <= x) t++;
    return t;
}

void solve(){
    int c ,d;
    cin >> c >> d;
    int ans = 0;
    for(int i = 1, j = 10; i <= 10; i++, j *= 10){
        int l = max(1ll, 1ll * j / 10 - c);
        int r = min(d * 1ll, 1ll * j - 1 - c);
        if(l > r) continue;
        ans += f(j * c + c + r) - f(j * c + c + l - 1);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

---

E - Farthest Vertex

題目要求輸出每個頂點距離最大的節(jié)點編號 ，問題就轉(zhuǎn)化為求樹的直徑，求樹的直徑，通過兩次dfs求解

https://oi-wiki.org/graph/tree-diameter/

得到兩個節(jié)點a, b。分別用dfs求每個節(jié)點到a節(jié)點和b節(jié)點的距離，選取距離最遠的，輸出答案。

查看代碼

void solve(){
    int n;
    cin >> n;
    int u, v;
    vector<vector<int>> G(n + 1);
    for(int i = 1; i < n; ++i){
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    vector<int> dis(n + 1, 0); 
    auto dfs = [&](auto&& self, int u, int cur) -> void{
        for(auto v : G[u]){
            if(v == cur) continue;
            dis[v] = dis[u] + 1;
            self(self, v, u);
        }
    };

    dis[1] = 0;
    dfs(dfs, 1, 0);

    int a = 0;
    for(int i = 1; i <= n; ++i){
        if(dis[i] >= dis[a]) a = i; 
    }

    for(int i = 0; i <= n; ++i) dis[i] = 0;
    dis[a] = 0;
    dfs(dfs, a, 0);
    auto disa = dis;

    int b = 0;
    for(int i = 1; i <= n; ++i){
        if(dis[i] >= dis[b]) b = i;
    }

    for(int i = 0; i <= n; ++i) dis[i] = 0;
    dis[b] = 0;
    dfs(dfs, b, 0);

    for(int i = 1; i <= n; ++i){
        if(disa[i] > dis[i]){
            cout << a << endl;
        }else if(disa[i] < dis[i]){
            cout << b << endl;
        }else{
            cout << max(a, b) << endl;
        }
    }
    return ;
}