banner
YangWithU

YangWithU

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

76
AI 生成的摘要
这篇文章主要介绍了一个暑期集训打卡挑战，作者计划在50天内每天上传自己的题解，并希望通过练习在比赛中取得好成绩。文章中还介绍了两个题目的解法。第一个题目是关于树的问题，通过深度优先搜索来计算节点之间下落果子的组合数目。第二个题目是关于位运算的问题，通过与运算来判断能否达到最终结果。第三个题目是关于序列的问题，通过维护一个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;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。