T O P

[资源分享]     2023牛客寒假算法基础集训营2 ABCDEFHJKL

  • By - 楼主

  • 2023-01-19 02:00:01
  • 比赛链接

    A

    题解

    知识点:数学。

    \(n\) 减去区间1的端点得到匹配的一个区间,求一下与区间2的交集。

    一个小公式,两区间 \([L_1,R_1]\)\([L_2,R_2]\) 的交集长度为 \(\max(0, \min(R_1, R_2) - \max(L_1, L_2) + 1)\)

    时间复杂度 \(O(1)\)

    空间复杂度 \(O(1)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    bool solve() {
        int n;
        cin >> n;
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int y = n - l1, x = n - r1;
        cout << max(0, min(y, r2) - max(x, l2) + 1) << '\n';
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    B

    题解

    知识点:数学。

    \(n\) 减去区间1的端点得到匹配的一个区间,求一下与区间2的交集。

    一个小公式,两区间 \([L_1,R_1]\)\([L_2,R_2]\) 的交集长度为 \(\max(0, \min(R_1, R_2) - \max(L_1, L_2) + 1)\)

    时间复杂度 \(O(1)\)

    空间复杂度 \(O(1)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    bool solve() {
        int n;
        cin >> n;
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int y = n - l1, x = n - r1;
        cout << max(0, min(y, r2) - max(x, l2) + 1) << '\n';
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    C

    题解

    知识点:枚举,差分,前缀和。

    枚举每个区间 \([L,R]\) 的匹配区间 \([n-R,n-L]\) ,匹配区间的每个点被其他区间覆盖的次数总和。

    我们可以预处理出每个点被区间覆盖的次数 \(d_i\) ,可以用差分再前缀和得到。对此,再做一次前缀和,就可以快速得到 \([n-R,n-L]\) 每个点被所有区间覆盖的次数总和, \(d_{n-L} - d_{n-R-1}\)

    再减去与 \([L,R]\) 重合部分的一段,可以用公式 \(\max(0, \min(R, n-L) - \max(L, n-R) + 1)\)

    要注意先特判 \(n-R>2\times 10^5\)\(n-L<0\) 的无交集情况。

    之后,再处理 \(n-L>2 \times 10^5\)\(n-R<1\) 的越界情况。

    时间复杂度 \(O(2 \cdot 10^5 \cdot m)\)

    空间复杂度 \(O(2 \cdot 10^5 + m)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    const int P = 998244353;
    int L[400007], R[400007];
    ll d[200007];
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int n, m;
        cin >> n >> m;
        for (int i = 1;i <= m;i++) {
            cin >> L[i] >> R[i];
            d[L[i]]++;
            d[R[i] + 1]--;
        }
        for (int i = 1;i <= 2e5;i++) d[i] += d[i - 1];
        for (int i = 1;i <= 2e5;i++) d[i] += d[i - 1];
        ll ans = 0;
        for (int i = 1;i <= m;i++) {
            int y = n - L[i], x = n - R[i];
            if (y <= 0 || x > 2e5) continue;
            x = max(x, 1);
            y = min(y, 200000);
            ans = ans + d[y] - d[x - 1] - max(0, min(y, R[i]) - max(x, L[i]) + 1);
            ans %= P;
        }
        cout << ans << '\n';
        return 0;
    }
    

    D

    题解

    知识点:贪心。

    一个节点的深度就是这个节点的能量能被获取的次数,显然深度越大的节点能量应该越大,所以直接求完深度从小到大排序,能量也从小到大排序,乘在一起加起来就行。

    因为 \(1 \leq f_i \leq i-1\) ,所以可以直接求出每个点的深度,不需要树形dp。

    时间复杂度 \(O(n \log n)\)

    空间复杂度 \(O(n)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    const int N = 200007;
    
    int a[N];
    int dep[N];
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int n;
        cin >> n;
        dep[1] = 1;
        for (int i = 2;i <= n;i++) {
            int f;
            cin >> f;
            dep[i] = dep[f] + 1;
        }
        for (int i = 1;i <= n;i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        sort(dep + 1, dep + n + 1);
        ll ans = 0;
        for (int i = 1;i <= n;i++) {
            ans += 1LL * dep[i] * a[i];
        }
        cout << ans << '\n';
        return 0;
    }
    

    E

    题解

    知识点:数学,二分。

    通过一些不容易的证明,可以知道全局最小值一定出现在 \(\left\lfloor \sqrt n \right\rfloor,\left\lceil \sqrt n \right\rceil\) 两个点。

    具体的,我们考虑 \(g(x) = \dfrac{n}{x} + x - 1\) 容易知道 \(\sqrt n\) 就是最小值点,但对于 \(f(x) = \left\lfloor \dfrac{n}{x} \right\rfloor + x - 1\) ,考虑 \(\sqrt n\) 两边的变化率。若 \(x \in \Z^+\)\(\sqrt n\) 右侧 \(\dfrac{n}{x}\) 的减量小于 \(x\) 的增量,所以 \(\left\lfloor \dfrac{n}{x} \right\rfloor\) 的减量小于等于 \(x\) 增量;左侧 \(\dfrac{n}{x}\) 的增量大于 \(x\) 的减量,所以 \(\left\lfloor \dfrac{n}{x} \right\rfloor\) 的增量大于等于 \(x\) 减量,所以全局最小值一定出现在 \(\left\lfloor \sqrt n \right\rfloor,\left\lceil \sqrt n \right\rceil\) 两个点,就可以比较得出最小值所在点了。

    设全局最小值点为 \(x\) ,若 \(L \geq x\) 显然答案为 \(L\)

    否则,考虑区间 \([L,R]\) 的局部最小值点,因为 \([1,x]\) 递减,所以局部最小值点为 \(t = \min(R,x)\) ,我们在 \([1,t]\) 内二分找到最左侧的最小值点即可。

    注意这道题直接三分不行,考虑三分:

    2211222|2222222|2222222
    2222222|2222222|2221122
    

    显然此时我们就无法判断是向左还是向右收缩。当然可以动用人类智慧,三分找到个局部点左右枚举 \(1000\) 个数qwq。

    时间复杂度 \(O(\log n)\)

    空间复杂度 \(O(1)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    ll n, L, R;
    ll x;
    ll f(ll x) {
        return n / x + x - 1;
    }
    
    bool check(ll mid) {
        return f(mid) - f(x) > 0;
    }
    
    bool solve() {
        cin >> n >> L >> R;
        x = sqrt(n);
        x = f(x) <= f(x + 1) ? x : x + 1;//全局最小值点
        if (L >= x) cout << L << '\n';
        else {
            x = min(R, x);//[L,R]的最小值点
            ll l = L, r = x;
            while (l <= r) {
                ll mid = l + r >> 1;
                if (check(mid)) l = mid + 1;
                else r = mid - 1;
            }
            cout << l << '\n';
        }
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    F

    题解

    知识点:BFS。

    找到同时能到起点和终点的点即可,于是从起点和终点分别搜索。

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(n)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    int n, k;
    bool dt[500007][10];
    
    struct node {
        int x, y;
    };
    queue<node> q;
    void bfs(node st, vector<vector<int>> &vis, vector<vector<int>> &dir) {
        vis[st.x][st.y] = 1;
        q.push(st);
        while (!q.empty()) {
            node cur = q.front();
            q.pop();
            for (int i = 0;i < 2;i++) {
                int xx = cur.x + dir[i][0];
                int yy = cur.y + dir[i][1];
                if (xx <= 0 || xx > n || yy <= 0 || yy > 3 || vis[xx][yy] || dt[xx][yy]) continue;
                vis[xx][yy] = 1;
                q.push({ xx,yy });
            }
        }
    }
    
    
    bool solve() {
        cin >> n >> k;
        for (int i = 1;i <= n;i++) dt[i][1] = dt[i][2] = dt[i][3] = 0;
        for (int i = 1;i <= k;i++) {
            int x, y;
            cin >> x >> y;
            dt[x][y] ^= 1;
        }
        vector<vector<int>> vis1(n + 1, vector(4, 0));
        vector<vector<int>> vis2(n + 1, vector(4, 0));
        vector<vector<int>> dir1 = { {1,0},{0,1} };
        vector<vector<int>> dir2 = { {-1,0},{0,-1} };
        bfs({ 1,1 }, vis1, dir1);
        bfs({ n,3 }, vis2, dir2);
        if (!vis1[n][3]) cout << 0 << '\n';
        else {
            int ans = 0;
            for (int i = 1;i <= n;i++) {
                for (int j = 1;j <= 3;j++) {
                    if (vis1[i][j] && vis2[i][j]) ans++;
                }
            }
            cout << ans - 1 << '\n';
        }
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    H

    题解

    方法一

    知识点:枚举,差分,贪心。

    因为分成子序列,因此可以随意分配,我们优先把一个数字分在一个序列里,剩下的分在同一个。

    因此,我们可以先求出每个数字的出现次数,再考虑出现次数对答案的贡献:

    k/贡献/出现次数 1 2 3 4 5
    1 1 0 0 0 0
    2 1 2 1 1 1
    3 1 2 3 2 2
    4 1 2 3 4 3
    5 1 2 3 4 5

    我们发现规律 \(k<cnt\) 时为 \(k-1\) ,否则为 \(cnt\)

    我们对此进行两次差分得到表格:

    k/贡献二次差分/出现次数 1 2 3 4 5
    1 1 0 0 0 0
    2 -1 2 1 1 1
    3 0 -2 1 0 0
    4 0 0 -2 1 0
    5 0 0 0 -2 1

    我们在 \(ans_2 ,ans_{cnt}\) 处加 \(1\)\(ans_{cnt+1}\) 处减一即可。

    最后前缀和两次,就是答案了。

    时间复杂度 \(O(n + 10^5)\)

    空间复杂度 \(O(n+10^5)\)

    方法二

    知识点:枚举,贪心,前缀和,二分。

    利用上面发现的规律:

    \(k<cnt\) 时为 \(k-1\) ,否则为 \(cnt\)

    我们先求出每个数字出现的次数,然后按照次数从小到大排序,随后枚举 \(k\)

    我们用二分找到 \(cnt > k\) 的位置,于是 \(cnt\leq k\) 的部分为 \(cnt\) 用前缀和得到总和,否则就是个数乘 \(k-1\)

    时间复杂度 \(O(n \log 10^5)\)

    空间复杂度 \(O(n + 10^5)\)

    代码

    方法一

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    int cnt[100007];
    int ans[100007];
    bool solve() {
        int n;
        cin >> n;
        for (int i = 1;i <= 1e5;i++) ans[i] = cnt[i] = 0;
        for (int i = 1;i <= n;i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        for (int i = 1;i <= 1e5;i++) {
            if (!cnt[i]) continue;
            ans[2]++;
            ans[cnt[i]]++;
            ans[cnt[i] + 1] -= 2;
        }
        for (int i = 1;i <= n;i++) ans[i] += ans[i - 1];
        for (int i = 1;i <= n;i++) ans[i] += ans[i - 1];
        for (int i = 1;i <= n;i++) cout << ans[i] << '\n';
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    方法二

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    int cnt[100007];
    int sum[100007];
    bool solve() {
        int n;
        cin >> n;
        for (int i = 1;i <= 1e5;i++) cnt[i] = 0;
        for (int i = 1;i <= n;i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        sort(cnt + 1, cnt + 100000 + 1);
        for (int i = 1;i <= 1e5;i++) sum[i] = sum[i - 1] + cnt[i];
        for (int i = 1;i <= n;i++) {
            int idx = upper_bound(cnt + 1, cnt + 100000 + 1, i) - cnt;
            cout << sum[idx - 1] + (100000 - idx + 1) * (i - 1) << '\n';
        }
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    J

    题解

    知识点:数学。

    分类讨论:

    \[\begin{aligned} a_i<0,a_j<0 &\Rightarrow \max(|a_i-a_j|,|a_i+a_j|) = a_i+a_j\\ a_i<0,a_j \geq 0 &\Rightarrow \max(|a_i-a_j|,|a_i+a_j|) = (-a_i)+a_j\\ a_i\geq 0,a_j<0 &\Rightarrow \max(|a_i-a_j|,|a_i+a_j|) = a_i+(-a_j)\\ a_i\geq 0,a_j \geq 0 &\Rightarrow \max(|a_i-a_j|,|a_i+a_j|) = (-a_i)+(-a_j) \end{aligned} \]

    综上 \(\max(|a_i-a_j|,|a_i+a_j|) = |a_i|+|a_j|\)

    所以

    \[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n} \max(|a_i-a_j|,|a_i+a_j|) &= \sum_{i=1}^{n}\sum_{j=1}^{n} (|a_i|+|a_j|)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{n} |a_i| + \sum_{i=1}^{n}\sum_{j=1}^{n} |a_j|\\ &=2n\sum_{i=1}^{n} |a_i| \end{aligned} \]

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(1)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    bool solve() {
        int n;
        cin >> n;
        ll ans = 0;
        for (int i = 1;i <= n;i++) {
            int x;
            cin >> x;
            ans += abs(x);
        }
        ans *= 2 * n;
        cout << ans << '\n';
        return true;
    }
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int t = 1;
        cin >> t;
        while (t--) {
            if (!solve()) cout << -1 << '\n';
        }
        return 0;
    }
    

    K

    题解

    知识点:图论建模,枚举。

    题目可以转化为 \(n\) 个点 \(m\) 条边的一张无向图。 \(q\) 次询问,每次选出 \(k\) 个点,求这些点构成的最大子图的边数。

    直接枚举的最坏复杂度是 \(O(m\sum k)\) ,显然不可行,问题出在有些点的边可能很多。

    此时我们利用平衡思想。因为边的方向不重要,所以可以给边定向,减少某些点的边数。我们考虑一条边的两个点 \(x,y\) 的度数 \(d_x,d_y\) ,当其满足 \(d_x \leq d_y\) 时,建 \(x \to y\) 的边;否则,建 \(y \to x\) 的边。这种操作能将边数平衡到 \(O(\sqrt m)\) 的复杂度。

    证明:

    \(x\) 的出边个数为 \(cnt_x\) ,则有 \(cnt_x ^2 \leq cnt_x d_x\leq \sum d_y \leq 2m\) ,因此可以证明 \(cnt_x \leq \sqrt{2m}\)

    时间复杂度 \(O(\sqrt m \sum k)\)

    空间复杂度 \(O(n+m)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    struct Graph {
        struct edge {
            int v, nxt;
        };
        int idx;
        vector<int> h;
        vector<edge> e;
    
        Graph(int n, int m):idx(0), h(n + 1), e(m + 1) {}
        void init(int n) {
            idx = 0;
            h.assign(n + 1, 0);
        }
    
        void add(int u, int v) {
            e[++idx] = edge{ v,h[u] };
            h[u] = idx;
        }
    };
    const int N = 2e5 + 7, M = 2e5 + 7;
    Graph g(N, M);
    
    int feat[N];
    bool vis[N];
    int deg[N];
    
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int n, m, q;
        cin >> n >> m >> q;
        vector<pair<int, int>> edge(m + 1);
        for (int i = 1;i <= m;i++) {
            int u, v;
            cin >> u >> v;
            edge[i] = { u,v };
            deg[u]++;
            deg[v]++;
        }
        for (int i = 1;i <= m;i++) {
            auto [u, v] = edge[i];
            if (deg[u] < deg[v]) g.add(u, v);
            else g.add(v, u);
        }
        while (q--) {
            int k;
            cin >> k;
            for (int i = 1;i <= k;i++) cin >> feat[i], vis[feat[i]] = 1;
            int ans = 0;
            for (int i = 1;i <= k;i++) {
                for (int j = g.h[feat[i]];j;j = g.e[j].nxt) {
                    int v = g.e[j].v;
                    if (!vis[v]) continue;
                    ans++;
                }
            }
            cout << ans << '\n';
            for (int i = 1;i <= k;i++) vis[feat[i]] = 0;
        }
        return 0;
    }
    

    L

    题解

    知识点:数论,枚举。

    考虑先将 \(a_i\cdot a_j \bmod p\)\(a_k \bmod p\) 的值的个数统计到 \(cnta\)\(cntb\) 中。

    随后 \(\displaystyle ans_x = \sum_{(i+j) \mod p = x} cnta_i \cdot cntb_j\) ,但此时我们没考虑 \(i = k\)\(j = k\) 的情况,我们只要单独把 \((a_i\cdot a_j + a_i) \bmod p\) 的答案减去 \(2\) 即可,代表减掉 \((i,j,i),(j,i,i)\) 两组。

    时间复杂度 \(O(n^2 + p^2)\)

    空间复杂度 \(O(n+p)\)

    代码

    #include <bits/stdc++.h>
    using ll = long long;
    using namespace std;
    
    int a[5007];
    int cnta[5007], cntb[5007];
    ll ans[5007];
    int main() {
        std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int n, p;
        cin >> n >> p;
        for (int i = 1;i <= n;i++) cin >> a[i];
        for (int i = 1;i <= n;i++) cnta[a[i] % p]++;
    
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                if (i != j) cntb[1LL * a[i] * a[j] % p]++;
    
        for (int i = 0;i < p;i++)
            for (int j = 0;j < p;j++)
                ans[(i + j) % p] += 1LL * cnta[i] * cntb[j];
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= n;j++)
                if (i != j) ans[(1LL * a[i] * a[j] + a[i]) % p] -= 2;
        for (int i = 0;i < p;i++) cout << ans[i] << " \n"[i == p - 1];
        return 0;
    }
    
    Image

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册