牛客模考题

BraumAce2024年9月1日约 2463 字大约 8 分钟

牛客模考题

VC1 牛牛吃草

描述

现在有一排 $n$ 块草地，第 $i$ 块草地上有 $w_i$ 斤草，以及一个数字 $a_i$ 。当牛牛在第 $i$ 块草地上时，他可以吃掉这个草地上所有的草，并且向右走到另一块草地。但是牛牛有强迫症，他向右走的距离必须是 $a_i$ 的整数倍。例如：当牛牛在第 $3$ 块草地，并且 $a_3 = 2$ 时，他下一步就只能前往第 $5,7,9,\dots,$ 块草地。

牛牛可以从任意一块草地开始不断的吃草并移动到下一个草地，并且可以在任意一块草地结束它的吃草之旅。

现在请问，牛牛在一次吃草之旅中，最多可以吃掉多少斤草？

输入描述：

第一行一个整数 $n(1 \leq n \leq 10^3)$

接下来一行 $n$ 个整数表示 $w_i(1 \leq w_i \leq 100)$

最后一行 $n$ 个整数表示 $a_i (1 \leq a_i \leq 10)$

输出描述：

一个整数，表示答案。

示例

输入：5
      3 5 20 7 5
      1 2 5 1 3
输出：23
说明：从第1块草地走到第3块，总草数为3+20=23

题解

简单的线性DP，可以理解为背包问题：每块草地，满足条件就吃，不满足就吃不了。

状态转移方程：f[i] 表示到达第 $i$ 块草地能吃的最大值，第 $i$ 块能吃的量 = 前面任意一块能到达 $i$ 位置的量 + 第 $i$ 块的量，即：

f[i] = max(f[前1块能到达草地的最大值], f[i - 1] + w[i])

#include <iostream>
#include <cmath>
using namespace std;
const int N = 1010;

int n;
int w[N], a[N];
int f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> w[i];
        f[i] = w[i];
    }
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++){
        for (int j = 1; j < i; j++){
            if ((i - j) % a[j] == 0){
                f[i] = max(f[i], f[j] + w[i]);
            }
        }
    }

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

    cout << res << endl;

    return 0;
}

现在有一个 $n×m$ 的棋盘，每一个格子中有一个数字，其中第 $i$ 行第 $j$ 列的格子中的数字为 $a_{i,j}$ ，并且这个格子的权重为 $b_{i,j}$ ，当你在一个格子时，你可以选择一个与他相临的格子到达，但是那个格子上面的数字 $x$ 不能小于当前所在格子的数字与权值之和（两个格子相临当且仅当他们有一条公共的边）。例如：当前所在格子上面的数字为 $3$ ，权重为 $5$ ，则你下一步能够到达的格子上面的数字至少为 $8$ 。

现在给你 $q$ 次询问，每次询问给定一个格子 $(x,y)$ ，要求你回答：从任意一个格子出发，最后到达这个格子的方案有多少种。两种方案不同，当且仅当这两种方案经过的格子序列不同。

输入描述：

第一行两个整数 $n,m(1≤n,m≤1000)$

接下来 $n$ 行每行 $m$ 个整数，表示 $a_{i,j}(1≤a_i,j≤10^5)$

接下来 $n$ 行每行 $m$ 个整数，表示 $b_{i,j}(1≤b_i,j≤10^3)$

接下来一行一个整数 $q(1≤q≤10^5)$

之后 $q$ 行每行两个整数 $x,y(1≤x≤n,1≤y≤m)$

输出描述：

输出包含 $q$ 行，每行一个整数表示对应询问的答案。由于答案可能很大，你只需要输出它对 $100007$ 取模的值即可。

示例

输入：3 3
      1 2 3
      4 5 6
      7 8 9
      1 1 1
      1 1 1
      1 1 1
      3
      1 2
      2 2
      3 3
输出：2
      5
      19
说明：对于第一个询问，合法路径共有[(1,1),(1,2)],[(2,2)]两条
      对于第二个询问，合法路径共有[(1,1),(1,2),(2,2)],[(1,1),(2,1),(2,2)],[(1,2),(2,2)],[(2,1),(2,2)],[(2,2)]五条。

题解

DFS 的倒序遍历，以给定的 $(x, y)$ 为起点，查找符合条件的格子即可。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1010;
const int mod = 100007;

int n, m;
int a[N][N], b[N][N];
int q;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int st[N][N];

int dfs(int x, int y) {
    if (st[x][y])
        return st[x][y];

    st[x][y] = 1;
    int cnt = 0;
    for (int i = 0; i < 4; i++){
        int xx = x + dx[i], yy = y + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m &&
            a[xx][yy] + b[xx][yy] <= a[x][y]){
            st[x][y] += dfs(xx, yy);
        }
    }

    st[x][y] %= mod;
    return st[x][y];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++)
            cin >> b[i][j];
    }

    cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        cout << dfs(x, y) << endl;
    }

    return 0;    
}

VC28 染色

描述

给你一个长度为 $n$ 的数组 $\{a_n\}$ ，以及 $q$ 次操作。每次操作给定两个数 $x,y$ 表示将原数组中所有的 $x$ 变为 $y$ 。请问 $q$ 次操作后数组变成了什么样子？

输入描述：

第一行一个整数 $n(1 \leq n \leq 2*10^5)$

接下来一行 $n$ 个整数 $a_i(1 \leq a_i \leq n)$

第三行一个整数 $q(1 \leq q \leq 2*10^5)$

接下来 $q$ 行每行两个整数 $x,y(1 \leq x,y \leq n)$

输出描述：

一行 $n$ 个整数，表示答案。

示例

输入：5
      1 2 3 4 5
      4
      1 4
      2 3
      3 5
      5 1
输出：4 1 1 4 1

题解

涉及到链表的操作，本质上是一种并查集的思想。

list::splice

list::splice 实现 list 拼接的功能。将原 list 的内容部分或全部元素删除，拼插入到目的 list。

函数有以下三种声明：

一：void splice ( iterator position, list<T,Allocator>& x );
二：void splice ( iterator position, list<T,Allocator>& x, iterator it );
三：void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );

解释：

position 是要操作的 list 对象的迭代器
list&x 被剪的对象

对于一：会在 position 后把 list&x 所有的元素到剪接到要操作的 list 对象
对于二：只会把 it 的值剪接到要操作的 list 对象中
对于三：把 first 到 last 剪接到要操作的 list 对象中

#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;
const int N = 2e5 + 10;

int n;
int a[N];
int q;

int main() {
    cin >> n;
    unordered_map<int, list<int>> cnt;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]].push_back(i);
    }

    cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;

        if (x == y) continue;
        // 归并
        cnt[y].splice(cnt[y].end(), cnt[x]);
    }

    for (auto [x, idx] : cnt){
        for (auto i : idx){
            a[i] = x;  // 更新操作
        }
    }

    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';

    return 0;
}

VC35 正则匹配

描述

给你 $n$ 个字符串 $a_1,a_2,a_3,\dots,a_n$ ，现在有 $q$ 次询问，每次询问给你一个字符串 $t$ ，请你计算出他是原来 $n$ 个字符串中多少字符串的前缀。

输入描述：

第一行一个整数 $n(1 \leq n \leq 1000)$

接下来 $n$ 行每行一个仅包含小写字母的字符串表示 $a_i(|a_i|\leq 100)$

之后一个整数 $q(1 \leq q \leq 1000)$

接下来 $q$ 行每行一个仅包含小写字母的字符串 $t(|t| \leq 100)$

输出描述：

对于每次询问，输出一个整数表示答案。

示例

输入：3
      abaab
      aabab
      abbbb
      3
      ab
      abb
      a
输出：2
      1
      3

题解

字典树解法。

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6 + 10;

int n, q;
vector<vector<int>> nodes;
vector<int> end_idx;
int id = 0;

// 构建字典树，遍历添加字符串
void build_tree(string& s) {
    int node_id = 0;
    for (auto c : s){
        int idx = c - 'a';
        if (nodes[node_id][idx] == 0){
            id++;
            nodes[node_id][idx] = id;
        }
        node_id = nodes[node_id][idx];
    }

    end_idx[node_id]++;
}

int dfs(int id) {
    if (id == 0)
        return 0;
    
    int sum = end_idx[id];
    for (int i = 0; i < 26; i++){
        sum += dfs(nodes[id][i]);
    }

    return sum;
}

// 获取叶子节点的个数
int count(string& t) {
    int node_id = 0;
    for (auto c : t){
        int idx = c - 'a';
        node_id = nodes[node_id][idx];
        if (node_id == 0)
            return 0;
    }

    return dfs(node_id);
}

int main() {
    cin >> n;
    nodes = vector<vector<int>>(N, vector<int>(26, 0));
    end_idx = vector<int>(N, 0);

    for (int i = 1; i <= n; i++){
        string s;
        cin >> s;
        build_tree(s);
    }

    cin >> q;
    while (q--){
        string t;
        cin >> t;
        cout << count(t) << endl;
    }

    return 0;
}

VC40 购物

描述

有 $n$ 个人， $m$ 个队列，第 $i$ 个人在 $a_i$ 时到达，需要 $s_i$ 时间购买商品。
第 $i$ 个人到达后会选择当前等待时间最少的队伍，如果有多个队伍则会选择编号最小的队伍。
请求出 $n$ 个人需要多长时间购买完成。
保证到达时间互不相同。

输入描述：

第一行两个整数 $n,m$ $(n,m \le 10^5)$
随后 $n$ 行每行两个整数， $a_i$ 和 $s_i$ $(a_i,s_i \le 10^9)$

输出描述：

输出 $n$ 个人需要多长时间购买完成。

示例

题解

线段树。

使用线段树维护每个队列的等待时间即可。

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e6 + 10;

int n, m;
pair<ll, ll> nums[N];
vector<ll> seg(N), seg2(N);  // 两个线段树
ll ret(0);

void pushup(int node) {
    if (seg[node << 1] <= seg[node << 1 | 1]) {
        seg[node] = seg[node << 1];
        seg2[node] = seg2[node << 1];
    } else {
        seg[node] = seg[node << 1 | 1];
        seg2[node] = seg2[node << 1 | 1];
    }
}

void build(int l, int r, int node) {
    if (l == r) {
        seg[node] = 0;
        seg2[node] = l;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, node << 1);  // 左孩子
    build(mid + 1, r, node << 1 | 1);  // 右孩子!
    pushup(node);
}

void update(int l, int r, int pos, int node, ll ai, ll c) {
    if (l == r) {
        seg[node] = max(seg[node], ai) + c;
        ret = max(ret, seg[node]);
        return ;
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        update(l, mid, pos, node << 1, ai, c);
    } else {
        update(mid + 1, r, pos, node << 1 | 1, ai, c);
    }
    pushup(node);

}

int main() {
    cin >> n >> m;

    build(1, m, 1);

    vector<ll> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i];
        nums[i] = make_pair(a[i], s[i]);
    }

    sort(nums + 1, nums + n + 1);

    for (int i = 1; i <= n; i++) {
        int pos = seg2[1];
        update(1, m, pos, 1, nums[i].first, nums[i].second);
    }

    cout << ret << endl;

    return 0;
}