官方题解 | 挑战赛#13

Yuilice

2025-01-06 11:07:18

发布于：浙江

104阅读

0回复

0点赞

   很高兴看到大家在享受(坐牢)本次挑战赛 --- by Yuilice

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目名称	题目难度
T1	CityWalk	入门
T2	集合操作	普及-
T3	乌尔达哈城市分布图	普及-
T4	恰好	普及/提高-
T5	符文锁	普及/提高-
T6	集合操作2	普及/提高-

题解

CityWalk

题目大意

给予一个 $H \times W$ 的二维矩阵，给予两个顶点 $(x_1,y_1)$ 与 $(x_2,y_2)$ ，要求求出两个顶点的曼哈顿距离。

题解思路

本题本质为求曼哈顿距离的问题，在输入矩阵的时候记录两个顶点的坐标，然后计算两个坐标的曼哈顿距离即可。

曼哈顿距离计算公式 = $|x_1 - x_2| + |y_1 - y_2|$

参考代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    int h, w;
    cin >> h >> w; // 输入矩阵的行数和列数

    char grid[h][w]; // 定义二维数组存储矩阵
    int x1 = -1, y1 = -1, x2 = -1, y2 = -1; // 初始化两位旅行家的位置

    // 输入矩阵并找到两位旅行家的位置
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'o') {
                if (x1 == -1) { // 找到第一位旅行家
                    x1 = i;
                    y1 = j;
                } else { // 找到第二位旅行家
                    x2 = i;
                    y2 = j;
                }
            }
        }
    }

    // 计算曼哈顿距离
    int distance = abs(x1 - x2) + abs(y1 - y2);
    cout << distance << endl;
    return 0;
}

集合操作

题目大意

我们需要实现一个集合，支持以下操作：

插入元素：将元素 x 加入集合。
删除元素：从集合中删除 c 个 x，如果 x 的数量不足 c，则删除所有 x。
查询差值：输出集合中最大值与最小值的差。

题解思路

本道题采用multiset解决更为方便。 - oiwiki中对于multiset介绍

选择合适的数据结构:
我们可以选择一种特殊的数据结构multiset来储存元素，该数据结构的各项函数与set的操作几乎一致，并且支持保存重复元素与自动排列，可以最高效的获取最大值与最小值。
操作实现：
- 插入操作：直接将元素插入 multiset。
- 删除操作：使用 multiset 的 erase 方法删除指定数量的元素。
- 查询操作：通过 multiset 的 begin() 和 rbegin() 获取最小值和最大值，计算差值。

时间复杂度:

插入操作: $O(log$ $ n)$
删除操作: $O(log$ $ n + c)$
查询操作: $O(1)$

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    multiset<int> st;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            st.insert(x);
        } else if (t == 2) {
            int x, c;
            cin >> x >> c;
            while (c-- && st.find(x) != st.end()) {
                st.erase(st.find(x));
            }
        } else {
            cout << *st.rbegin() - *st.begin() << endl;
        }
    }
}

乌尔达哈分布图

题目大意

给出 $n$ 个结点, $m$ 条边的无向图，每条边连接两个结点，结点编号从 $1$ 到 $n$ 。

求解每个结点的出度数量与其出边相连的结点的编号，从小到大输出。

题解思路

本道题考查图论储存当中的静态链表-邻接表的应用。

首先，我们可以用邻接表来存储图的结构。对于每个结点 $u$ ，我们可以用一个数组 $a_u$ 来存储它的出边的结点编号。

然后，我们可以遍历每个结点 $u$ ，对它的出边进行排序，然后输出它的出度数量与其出边相连的结点的编号。

时间复杂度为 $O(n\log m)$ ，空间复杂度为 $O(n+m)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> a(n + 1); // 邻接表

    // 输入边
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        a[u - 1].push_back(v);
        a[v - 1].push_back(u);
    }

    // 输出邻接表
    for (int i = 0; i < n; ++i) {
        sort(a[i].begin(), a[i].end()); // 排序邻接列表
        cout << a[i].size(); // 输出邻接节点数量
        for (int j = 0; j < a[i].size(); ++j) { // 使用下标遍历
            cout << ' ' << a[i][j]; // 输出邻接节点
        }
        cout << '\n';
    }

    return 0;
}

恰好

题目大意

给出一个 $N$ ，求解有多少个公差为1的等差数列，使得它们的和为 $N$ 。

题解思路

数列 $[A, A + 1, \dots, B - 1, B]$ 的和为 $\dfrac{(A + B)(B - A + 1)}{2}$ （可理解为将 $[A, A + 1, \dots, B - 1, B]$ 与 $\dfrac{(A + B)(B - A + 1)}{2}$ 相加）。(每个元素加上 $[B, B-1, \dots, A + 1, A]$ 即可理解）。

因此，这个问题等价于求解

$(A + B)(B - A + 1) = 2N \quad (A ≤ B).$

这里， $A + B, B - A + 1$ 都是 $2N$ 的除数，因为它们都是整数。
现在，列举分解成两个正整数的方法，如 $2N=x \times y$ ，并求解

$\begin{cases} A + B = x\\ B - A + 1 = y\\ \end{cases}$

从而求出整数解的个数。
它的解是
$A = (x - y + 1)/2,\ B = (x + y - 1)/2$
如果 $x$ 和 $y$ 的奇偶性不同，它的解就是 $A = (x - y + 1)/2,\ B = (x + y - 1)/2$ ；否则，就没有这样的整数解。

因此，答案就是将 $2N$ 分解成两个不同奇偶性整数的方法数。
由于 $2N$ 的除数可以用 $O(\sqrt N)$ 的时间复杂度枚举出来，所以这个问题总共可以用 $O(\sqrt N)$ 的时间解决。

另外，由于 $2N$ 的质因数至少有一个 $2$ ，所以 $x$ 和 $y$ 中的任何一个（但不是两个）的被除数都是 $2$ 。
因此，答案是（ $M$ 的被除数） ${}\times 2$ ，其中 $M =$ （ $N$ 重复除以 2 直到它不能被 $2$ 分割）。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){ ll N;
    cin >> N;
    while(N % 2 == 0) N /= 2;
    ll sq = sqrt(N), ans = 0;
    for(ll i = 1; i <= sq; i++) if(N % i == 0) ans += 2;
    if(sq * sq == N) ans--;
    cout << ans * 2 << endl;
    return 0;
}

符文锁

题目大意

告知你最多存在 $N$ 个编号为 $1,2,\dots,N$ 的数字，你需要使用这些数字打开宝箱。

宝箱需要使用至少 $M$ 个正确的数字打开(无关先后顺序)，每个数字的状态可以是真或假。

告诉你已经进行过 $M$ 次的开箱的结果与使用的数字，要求你计算一下到底有几种打开宝箱的可能的数字组合方案，并且不与开箱结果冲突。

题解思路

符文的范围为 $N \le 15$ 且测试次数 $M \le 100$ 。因此我们可以得出正确的符文最多有 $2^N$ 种组合。

我们可以对所有的 $2^N$ 组合进行 $M$ 次测试，并计算正确组合的数量。
这里需要进行 $2^N \times M \le 3.3 \times 10^6$ 次测试。即使对一个测试执行 $N$ 次操作，总操作数的边界也是 $5 \times 10^7$ 。

为了对 $2^N$ 个组合进行暴力破解，位枚举。

比如使用循环遍历 $i=0,1,\dots,2^N-1$ 。如果 $2^k$ 中 $i$ 的位置是 $0$ ，我们就假设 $(k+1)$ 项符文是一个假符文；如果是 $1$ ，我们就假设它是一个真符文。这样，我们就可以穷举所有的组合。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_M = 105; 
const int MAX_N = 105;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    int ks[MAX_M]; // 用于存储每个集合的状态
    int r[MAX_M];  // 用于存储状态 o 或 x

    // 初始化数组
    for (int i = 0; i < m; i++) {
        ks[i] = 0; // 初始为 0
        r[i] = 0;  // 默认状态为 0
    }

    // 读入数据
    for (int i = 0; i < m; i++) {
        int c;
        cin >> c;
        for (int j = 0; j < c; j++) {
            int a;
            cin >> a;
            a--; // 将 a 转换为 0 基索引
            ks[i] |= (1 << a); // 更新集合
        }
        
        string s;
        cin >> s;
        if (s == "o") {
            r[i] = 1; // 表示正状态
        } else {
            r[i] = 0; // 表示反状态
        }
    }

    int res = 0;
    // 遍历所有可能的状态
    for (int i = 0; i < (1 << n); i++) {
        bool jud = true; // 初始化判断标志
        for (int j = 0; j < m; j++) {
            int ok = __builtin_popcount(i & ks[j]); // 计算 i 与 ks[j] 的交集中的1的个数
            if (ok >= k && r[j] == 0) {
                jud = false; 
                break; // 状态不满足，岀口
            }
            if (ok < k && r[j] == 1) {
                jud = false; 
                break; // 状态不满足，岀口
            }
        }
        if (jud) {
            res++; // 满足条件的状态计数
        }
    }
    
    cout << res << "\n"; // 输出结果
    return 0;
}

集合操作2

题目大意

给定一个长度为 $A = {A_1,A_2,...,A_N}$ 的序列，需要处理 $q$ 次操作，操作类型分为以下三种：

赋值操作：1 x，将序列 $A$ 中的所有元素赋值为 $x$ 。
添加操作：2 x y，将 $x$ 加到 $A_y$ 上。
查询操作：3 y，输出 $A_y$ 的值。

需要按照操作的顺序依次执行，并输出所有查询操作的结果。

题解思路

该项问题属于区间修改问题，解决问题的方法很多，这里可以采用时间戳解决该项问题，代码量最小，或者你也可以建立对应的树状数组或者线段树长度为 $N$ 的序列进行范围更新和点检索，则解决问题的总时间约为 $O(N+Q\log N)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;

int a[N], xx[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    } 
    int qj = 0, q;
    cin >> q;
    int qtim = 0;

    for (int i = 1; i <= q; ++i) {
        int opt;
        cin >> opt;

        if (opt == 1) {
            int x;
            cin >> x;
            qj = x;
            qtim = i;
        } else if (opt == 2) {
            int x, y;
            cin >> x >> y;
            if (xx[x] < qtim) {
                a[x] = qj;
                xx[x] = qtim;
            }
            a[x] += y;
        } else {
            int x;
            cin >> x;
            if (xx[x] < qtim) {
                a[x] = qj;
                xx[x] = qtim;
            }
            cout << a[x] << '\n';
        }
    }

    return 0;
}

线段树参考代码

#include<bits/stdc++.h>
using namespace std;

const int N = 200005;
const long long INF = 1e14; // 表示未赋值的标记

struct SegmentTree {
    long long value; // 当前节点的值
    long long tag;   // 延迟标记
    int left, right; // 当前节点表示的区间
} tree[N << 2];

int a[N]; // 原始数组
int n, q; // 数组长度和操作次数

// 构建线段树
void build(int p, int l, int r) {
    tree[p].left = l;
    tree[p].right = r;
    tree[p].tag = INF; // 初始化标记为未赋值

    if (l == r) {
        tree[p].value = a[l]; // 叶子节点直接赋值
        return;
    }

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);      // 构建左子树
    build(p << 1 | 1, mid + 1, r); // 构建右子树
    tree[p].value = tree[p << 1].value + tree[p << 1 | 1].value; // 合并左右子树的值
}

// 下推延迟标记
void pushDown(int p) {
    if (tree[p].tag != INF) { // 如果有延迟标记
        tree[p << 1].tag = tree[p].tag; // 下推标记到左子树
        tree[p << 1 | 1].tag = tree[p].tag; // 下推标记到右子树

        // 更新左右子树的值
        tree[p << 1].value = tree[p].tag * (tree[p << 1].right - tree[p << 1].left + 1);
        tree[p << 1 | 1].value = tree[p].tag * (tree[p << 1 | 1].right - tree[p << 1 | 1].left + 1);

        tree[p].tag = INF; // 清除当前节点的标记
    }
}

// 单点更新
void add(int p, int id, long long val) {
    if (tree[p].left == tree[p].right && tree[p].left == id) {
        tree[p].value += val; // 更新叶子节点的值
        return;
    }

    pushDown(p); // 下推标记
    int mid = (tree[p].left + tree[p].right) >> 1;

    if (id <= mid) {
        add(p << 1, id, val); // 更新左子树
    } else {
        add(p << 1 | 1, id, val); // 更新右子树
    }
    tree[p].value = tree[p << 1].value + tree[p << 1 | 1].value; // 合并左右子树的值
}

// 单点查询
long long query(int p, int id) {
    if (tree[p].left == tree[p].right && tree[p].left == id) {
        return tree[p].value; // 返回叶子节点的值
    }
    pushDown(p); // 下推标记
    int mid = (tree[p].left + tree[p].right) >> 1;
    if (id <= mid) {
        return query(p << 1, id); // 查询左子树
    } else {
        return query(p << 1 | 1, id); // 查询右子树
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n); // 构建线段树
    cin >> q;
    long long op, x, y;
    for (int i = 1; i <= q; ++i) {
        cin >> op;
        if (op == 1) { // 全局赋值操作
            cin >> x;
            tree[1].tag = x; // 更新根节点的标记
        } else if (op == 2) { // 单点添加操作
            cin >> x >> y;
            add(1, x, y); // 更新指定位置的值
        } else { // 单点查询操作
            cin >> y;
            cout << query(1, y) << '\n'; // 查询指定位置的值
        }
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

pipilong
反正我的第一想法是定义一个桶数组（肯定得是map），维护两个大小指针。操作1，3都是常数，操作2还得分情况，当删除的数恰好是最大数或者是最小数，而且删除的数量还不小于原数量，就从上往下（从下往上）找，竟然也能过。建议加一个hack数据卡一下此类做法

1周前来自浙江
0
- pipilong
  回复pipilong
  例如
  
  4 1 0 1 1000000000 2 1000000000 2 3
  1周前来自浙江
  0
- pipilong
  回复pipilong
  还有一个小建议，以后出比赛时能否查一下重，本次比赛T5 ABC都有原题，听同学说T4也有原题，不过我还没找到。如果对于这样一个大的影响排位分的挑战赛也有原题的话是否有些不妥呢？姑且不说有人T5直接上**抄题解，就算他自己原先做过该题不抄题解，不也等同于他做5题的时间给其他人做6题。时间一长，排位分的价值也渐渐消失了
  
  1周前来自浙江
  0
- ‮队团加不）ด้้童帅_者仇复
  回复pipilong
  算他见识广（
  
  1周前来自广东
  0
‮队团加不）ด้้童帅_者仇复
multiset不会超时吗？

1周前来自广东
0
- pipilong
  回复‮队团加不）ด้้童帅_者仇复
  冒系针对该题不会
  
  1周前来自浙江
  0
- ‮队团加不）ด้้童帅_者仇复
  回复pipilong
  好像是的
  
  5天前来自广东
  0
- ‮队团加不）ด้้童帅_者仇复
  回复pipilong
  后来推了一下，发现erase的次数不超过 $2\times 10^5$
  
  5天前来自广东
  0