banner
YangWithU

YangWithU

可能是第一个上链的 Acmer ?! 平时主要记录做题题解，希望我的文章可以启发到你！如有错误，欢迎指正！
封存首頁

76
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
"暑期集訓打卡挑戰(1 / 50) 暑假開始了，我是一個蒟蒻Acmer，打算在這50天內好好訓練。每天我會上傳自己的題解，希望在比賽中取得好成績。希望大家監督我！ 每日例行 1843D Timofey會搖樹直到果子掉下，問兩個節點之間果子下落的組合數目。 解法1: 使用dfs遍歷樹，計算每個節點的子節點數目，最後計算兩個節點下落的組合數目。 解法2: 使用dfs遞歸遍歷樹，計算每個節點的子節點數目，最後計算兩個節點下落的組合數目。 1842B 三列數字，每次從一列拿出一個數字與當前數字進行AND運算，問能否達到最終結果x，當前數字從0開始。 1841B 維護一個01序列，滿足拼接後單調遞增的條件。遍歷序列時，遇到滿足拼接位置的數字

暑期集訓打卡挑戰 (1 / 50)#

Hi! 社區的大家！
暑假開始了，筆者是一個蒻蒟 Acmer，想着透過暑假的 50 天好好訓練，在這 50 天內，我每天都會上傳自己的題解，希望透過每日的大量練習，在之後比賽中能夠拿到一塊牌子
很弱，也很笨，但希望這 50 天我能堅持下去

希望大家狠狠監督！

Daily Routine#

1843D#

  • Timofey 會搖整棵樹直到所有果子掉下，果子按照從父節點到子節點的方式進行下落。之後給出詢問，求詢問兩節點之間下落情況的組合的數目。

分析可得，每個節點處下落果子的數量等於其子節點的數目。掉落方向始終向下，上端的果子總是比下端的晚掉落，子節點全掉完了父節點才會掉。
兩節點落果子的組合數目，應當等於兩節點各自落果數量相乘。

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

vector<vector<int>> e;
vector<i64> cnt; // cnt[i] maintain i's num of subverticles

void dfs(int u, int p) {
    if(e[u].size() == 1 && e[u][0] == p) cnt[u] = 1;

    else {
        for(auto v : e[u]) {
            if(v != p) {
                dfs(v, u);
                cnt[u] += cnt[v];
            }
        }
    }
}

void solve() {
    int n; cin >> n;
    e.assign(n, vector<int>());
    cnt.assign(n, 0);
    for(int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dfs(0, -1); // from head: 0

    int q; cin >> q;
    while (q--) {
        int u, v; cin >> u >> v;
        u--, v--;
        cout << cnt[u] * cnt[v] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

Apporach2:

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

void solve() {
    int n; cin >> n;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> cnt(n);
    auto dfs = [&](auto &self, int u, int p) -> void {
        if(adj[u].size() == 1 && adj[u][0] == p) cnt[u] = 1;
        else {
            for(auto v : adj[u]) {
                if(v != p) {
                    self(self, v, u);
                    cnt[u] += cnt[v];
                }
            }
        }
    };

    dfs(dfs, 0, -1);

    int q; cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        a--, b--;
        cout << 1LL * cnt[a] * cnt[b] << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

1842B#

  • 三列數字，每次從一列拿出一個數字與當前數字進行與運算，問能否達到最終結果 x，當前數字開始為 0

可以想到倒推法，最終結果與滿足條件的數字進行與運算結果，肯定等於最終結果自身，這是與運算特性。
所以只要當前數字與最終結果進行與運算後結果相同，就對當前結果 7 與該數字進行與運算，最終判斷結果是否等於最終結果 xx 即可

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

void solve() {
    int n, x; cin >> n >> x;
    int res = 0;
    for(int i = 0; i < 3; i++) {
        vector<int> a(n);
        for(int j = 0; j < n; j++) cin >> a[j];
        for(int j = 0; j < n; j++) {
            if((x | a[j]) != x) break;
            res |= a[j]; 
        }
    }
    if(res == x) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

1841B#

  • 讓我們維護一個選數的 01 序列，0 表示不選當前數字，1 則選。

該序列滿足能夠從一處 i 將前後分成兩部分，將前半移到後半後序列可重複單調遞增。

我們需要記錄前一個數字，最開頭數字 (拼接處第一個元素，用於比較)

在對序列進行遍歷時，遇到滿足序列拼接位置的數字後，用 down 標記，仔細比較後續的元素

可以想到，在遇到滿足序列拼接位置的數字處開始特別判斷即可，在遍歷序列過程中不需要將 down 復位，因為我們可以隨取隨用，不必擔心最優問題。

整個過程中保證單調可重複遞增。

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

void solve() {
    int n; cin >> n;
    int a0 = -1, prev = -1;
    bool down = false;
    for(int i = 0; i < n; i++) {
        int cur; cin >> cur;
        if(i == 0) {
            a0 = prev = cur;
            cout << 1;
        }
        else if(down) {
            if(cur <= a0 && cur >= prev) {
                prev = cur;
                cout << 1;
            } else cout << 0;
        }

        else if(cur >= prev) {
            prev = cur;
            cout << 1;
        }

        else if(cur <= a0) {
            down = true;
            prev = cur;
            cout << 1;
        }
        else cout << 0;
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

1840D#

  • 給我們一串數字，三個木匠每位選一個數字
    每人選的數字和這一串數字存在差，記差的和為等待時間，使最多等待時間最小
    木匠每人選的數字任意，可以不同

顯然，最優的分配方式是將整串數字分成三份，每位木匠一份。

題目提示很明顯：找每個人最多等待時間的最小值

所以我們考慮二分。這個最小值有明顯的區間，是整個答案的範圍的左半區間。

進行二分時，可以發現每次枚舉出的 mid 單調遞減，直到最後增的一剎那停止。

所以我們的 check 函數應該在當前 mid 過大時返回 true ，在小了的時候返回 false 終結搜索

mid 是答案，所以我們在 check 中應該針對該 mid 進行驗證。
本題中，我們可以先通過 mid 推導出第一和第三個木匠選的數字，以此確定第二個木匠負責範圍內的差值，將該值與 mid比較即可判斷 mid 的正確性

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    
    auto chk = [&](int mid) {
        int vall = a[0] + mid;
        int valr = a[n-1] - mid;

        int l = 1e9, r = 0;
        for(auto x : a) {
            // out of second carp's interval, continue
            if(abs(x - vall) <= mid || abs(x - valr) <= mid) continue;
            l = min(l, x);
            r = max(r, x);
        }
        return mid * 2 >= r - l;
    };

    // search in left interval: (l + r) >> 1
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if(chk(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

1840B#

一個人手裡有 k 個蛋糕，則應當有 $ 2^k $ 種組合方式，數學規律，與本題說的二進制無關

所以可以說，他有無限錢的時候，組合方式 $ ans = 2 ^ k $

從 0 開始記位，各個蛋糕的價值為:

1(20),2(21),4(22)...1(2^0), \quad 2(2^1), \quad 4(2^2) ...

前綴和即為從買 1 個蛋糕開始的花費。買 k 個蛋糕花費為 $ 2^k - 1 $，而 $ ans = (2^k - 1) + 1 $

沒有蛋糕數目 k 限制時，我們 n 塊錢可以買 n + 1 種方案

原因在於：對於任意錢 x，最貴可買 $ 2^y \leq x $ 蛋糕，最便宜可以不買。
中間的任意金額都可以用蛋糕價格 (二進制數) 表示出來
算上 0, 可以有 x + 1 種表示方式

所以，不限制蛋糕數目時，他擁有的錢 n 再加一，就是一共的表示方案數 $ ans = x + 1 $

所以我們取上述兩種方案最小的結果，就是所需答案。

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;

void solve() {
    int n, k; cin >> n >> k;
    k = min(k, 30);
    cout << min(n, (1 << k) - 1) + 1 << '\n';
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int _; cin >> _;
    while (_--) solve();
    return 0;
}

今日份知識點：單調隊列#

p1886#

  • 對一個長 n 的隊列上滑動長度為 k 的區間，求每時刻區間的最大，最小值。

肯定不能每時刻都去遍歷一次整個隊列，所以考慮維護一個存儲結構，使得該結構滿足單調性質。

可以通過在每次新存儲元素時，都對之前隊列中的元素進行檢查比較進行。由於我們只需要最值，所以不用考慮額外性質，遇到舊元素不滿足新性質，直接刪除即可。

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
const int N = 100010;

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    deque<int> q;
    for(int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] > a[i]) q.pop_back();
        q.push_back(i);
        if(i >= k) {
            while (!q.empty() && i - q.front() >= k) q.pop_front();
            cout << a[q.front()] << " ";
        }
    }
    cout << '\n';
    q.clear();
    for(int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] < a[i]) q.pop_back();
        q.push_back(i);
        if(i >= k) {
            while (!q.empty() && i - q.front() >= k) q.pop_front();
            cout << a[q.front()] << " ";
        }
    }
    return 0;
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。