2024牛客寒假算法基础集训营1

A DFS 搜索

所谓 DFS 搜索，就是给定一个字符串s，问能否找到s 的一个子序列，使得该子序列的值为 DFS 或 dfs。

请你分别判断字符串s 中是否含有 DFS 子序列与 dfs 子序列。

void solve() {
    int n;
    std::cin >> n;
     
    std::string s;
    std::cin >> s;
     
    for (auto t : {"DFS", "dfs"}) {
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (k < 3 && s[i] == t[k]) {
                k++;
            }
        }
        std::cout << (k == 3) << " ";
    }
    std::cout << "\n";
}

B 关鸡

给出着火点的坐标，最少还需要添加多少个着火点才能使得🐔逃不出去。

Solution

模拟

用 set<pair<int, int>> 来存坐标( .count({x,y}) 可以判断是否含有那个点的坐标)

(2,0) 需要特判，其他坐标

$1 \oplus 3 = 2, 2 \oplus 3 = 1$

void solve()
{
    int n;
    cin >> n;
    set<pair<int, int>> p;
    int left1 = 0, left2 = 0, right1 = 0, right2 = 0;

    for (int i = 1; i <= n; i++)
    {
        int r, c;
        cin >> r >> c;
        if (c <= 0)
            left1 = 1;
        if (c >= 0)
            right1 = 1;
        p.emplace(r, c);
    }
    for (auto [r, c] : p)
    {
        if (!c)
            continue;
        if (p.count({r ^ 3, c}) || p.count({r ^ 3, c + (c > 0 ? -1 : 1)}))
        {
            if (c > 0)
                right2 = 1;
            else
                left2 = 1;
        }
    }
    int ans = 4 - left1 - left2 - right1 - right2;
    if (!right2 && !left2)
        ans = min(ans, (int)(3 - p.count({2, 0}) - p.count({1, -1}) - p.count({1, 1})));

    cout << ans << '\n';
}

C 按闹分配

给出 $Q$ 组询问，即当工作人员的容忍限度为 $M$ 时，鸡最早能在哪个时刻办完事。

Solution

当鸡插队的时候，会增加 $S_{c} - S_{min} = 后面还有的人数 \times t c \leq M$

#define int long long
void solve()
{
    int n, q, tc;
    cin >> n >> q >> tc;
    vector<int> t(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    sort(t.begin() + 1, t.begin() + 1 + n);
    for (int i = 2; i <= n; i++)
        t[i] = t[i] + t[i - 1];

    while (q--)
    {
        int ans = 0, m;
        cin >> m;
        // for (int i = n; i >= 0; i--)//暴力
        //     if ((n - i) * tc <= m)
        //         ans = t[i] + tc;
        int low = 0,high = n;

        while (low <= high)
        {
            int mid = low + (high - low) / 2;

            if ((n - mid) * tc <= m)
            {
                ans = t[mid] + tc;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }

        cout << ans << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
     
    int n, Q, tc;
    std::cin >> n >> Q >> tc;
     
    std::vector<int> t(n);
    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> t[i];
    }
    std::sort(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + t[i];
    }
     
    while (Q--) {
        i64 M;
        std::cin >> M;
         
        i64 c = std::min(1LL * n, M / tc);
        i64 ans = s[n - c] + tc;
        std::cout << ans << "\n";
    }
     
    return 0;
}

D 数组成精

E 本题又主要考察了贪心

钓鱼题

在一场鸡比赛中，有 $n$ 只鸡参加，每只鸡截至目前已经积了 $a_{i}$ 分。接下来还有 $m$ 场比赛要进行，每场比赛的对阵双方是编号为 $u_{i}$ 和 $v_{i}$ 的鸡。积分规则是：胜方加三分，败方不得分，若战平则双方各得一分。

请你计算在最好的情况下，我们的一号选手（炸鸡）能够排到第几名。

注意若有多鸡并列，则排名取并列的排名，且不影响随后的排名（例如两只鸡并列第二名，则都视为第二名，排名其后的下一只鸡视为第四名）。

输入描述:
输入第一行包括一个整数 $T$ $(1 \leq T \leq 100)$ ，表示样例组数。

对于每组样例：

第一行输入两个整数 $n$ , $m$ $(2 \leq n \leq 10, 1 \leq m \leq 10)$ ，表示参与鸡的数量和比赛场数。

第二行输入 $n$ 个整数 $a_{i}$ $(0 \leq a_{i} \leq 100)$ ，表示每只鸡当前已经有的积分。

接下来的 $m$ 行，每行有两个正整数 $u_{i}$ , $v_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i})$ ，表示每场比赛的对阵双方。

输出描述:
对每组样例，输出一个整数表示一号选手最好的情况下能够排到第几名。

Solution

DFS

我开始做了半天贪心感觉不可行，但是数据范围及其小，于是想到爆搜。

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

void dfs(int cur, vector<int> &a, vector<int> &rank, vector<pair<int, int>> &matches, int &bestRank)
{
    if (cur == matches.size())
    {
        int zhaJiScore = a[1]; 
        int curRank = 1;       
        for (int i = 2; i < a.size(); i++)
        {
            if (a[i] > zhaJiScore)
            {
                curRank++; 
            }
        }
        bestRank = min(bestRank, curRank);
        return;
    }

    // 模拟比赛
    int x = matches[cur].first;
    int y = matches[cur].second;
    int xScore = a[x];
    int yScore = a[y];
    a[x] += 3;
    dfs(cur + 1, a, rank, matches, bestRank);
    a[x] = xScore; 
    a[y] += 3;    
    dfs(cur + 1, a, rank, matches, bestRank);
    a[y] = yScore; 
    a[x]++;
    a[y]++;
    dfs(cur + 1, a, rank, matches, bestRank);
    a[x] = xScore;
    a[y] = yScore;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        vector<pair<int, int>> matches(m);
        for (int i = 0; i < m; i++)
        {
            cin >> matches[i].first >> matches[i].second;
        }

        vector<int> rank(n + 1, 1);
        int bestRank = INT_MAX; 
        dfs(0, a, rank, matches, bestRank);
        cout << bestRank << endl;
    }
}

void solve() {
    int n, m;
    std::cin >> n >> m;
     
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
     
    std::vector<int> u(m), v(m);
    for (int i = 0; i < m; i++) {
        std::cin >> u[i] >> v[i];
        u[i]--, v[i]--;
    }
    int ans = n;
    auto dfs = [&](auto self, int i) -> void {
        if (i == m) {
            int res = 1;
            for (int j = 0; j < n; j++) {
                res += (a[j] > a[0]);
            }
            ans = std::min(ans, res);
            return;
        }
        for (auto [x, y] : {std::make_pair(3, 0), {0, 3}, {1, 1}}) {
            a[u[i]] += x;
            a[v[i]] += y;
            self(self, i + 1);
            a[u[i]] -= x;
            a[v[i]] -= y;
        }
    };
    dfs(dfs, 0);
    std::cout << ans << "\n";
}

F 鸡数题

G why 买外卖

鸡很饿，鸡要吃外卖，今天点份炸鸡外卖！

鸡使用的外卖程序有若干个满减优惠，第 i 个优惠可以表示为"满 $a [i]$ 元减 $b [i]$ 元"，多个满减优惠可以叠加。

满减的具体结算流程是：假设鸡购买的食物原价共为 $x$ 元，则所有满足 $x \geq a [i]$ 的满减优惠都可以一起同时被使用，优惠后价格记为 $y$ ，则鸡只要支付 $y$ 元就可以了（若 $y \leq 0$ 则不需要支付）。

现在，鸡的手机里一共只有 $m$ 元钱，鸡想知道，他所购买的食物原价 $x$ 最多为多少。

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> c(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> c[i].first >> c[i].second;
    sort(c.begin() + 1, c.begin() + 1 + n);
    for (int i = 2; i <= n; i++)
        c[i].second = c[i].second + c[i - 1].second;

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int pay = c[i].first - c[i].second;
        if (pay <= m)
            ans = max(ans, m + c[i].second);
    }
    if(!ans)
        ans = m;
    cout << ans << '\n';
}

H 01 背包，但是 bit

I It's bertrand paradox. Again!

J 又鸟之亦心

K 牛镇公务员考试

L 要有光

梯形的面积 $\to a n s = 3 \times w \times c$

我理解错误了题目的意思，原来地面是那面白墙 $\dots$

void solve()
{
    int c, d, h, w;
    cin >> c >> d >> h >> w;
    cout << 3 * w * c <<'\n';
}

M 牛客老粉才知道的秘密

对于 $n$ 道题的一场比赛，显示的六道题目中最左侧的题目一共有几种可能取值。

$n = 14 :$

void solve()
{
    int n;
    cin >> n;
    if (n % 6 == 0)
        cout << n / 6 << '\n';
    else
        cout << (n / 6) * 2 << '\n';
}