题解 | #2024牛客寒假算法基础训练营1#

DFS搜索

https://ac.nowcoder.com/acm/contest/67741/A

A-DFS搜索

思路：

  • 遍历字符S, 按顺序分别寻找 "DFS" , "dfs"。

以下是代码部分

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

string s;

int main()
{
    int t, n;
    ios::sync_with_stdio(false);
    cin >> t;
    while(t --)
    {
        cin >> n >> s;
        for(auto tem : {"DFS", "dfs"})
        {
            int kk = 0;
            for(int i = 0; i < n; i ++)
                if(kk < 3 && s[i] == tem[kk])
                    kk ++;
            cout << (kk == 3) << " ";
        }
        cout << '\n';
    }

    return 0;
}

B-关鸡

题目描述：

在一条宽为 长为 ＋ 的管道中，有一只鸡和若干着火点，鸡可以上下左右移动一格、不能出管道上下边界、不能进入着火地点。

鸡初始在 处，现在给出若干个着火点的坐标，请求出为了不让鸡逃出管道（即到达管道最左端或最右端），最少需要添加多少个着火点。

思路：

  • 易得最多只需要添加三个着火点
  • 想要关住鸡有两种关法：
    • 第一种：左边两个着火点，右边两个着火点。共需添加四个
    • 第二种：鸡的初始坐标的下面一个着火点，左右个一个着火点。共需添加三个
  1. 对坐标以横坐标的大小标准排序。
  2. 判断着火点的相邻个数
  3. 对比两种添加着火点的方法（选取最优的）。

以下是代码部分, 参考代码来源Scarlett_come_here

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

const int N = 1e5 + 10;

//存储已存在的着火点坐标
struct Coordinate {
  //r代表纵坐标，c代表横坐标
    int r, c;
}s[N];
//根据横坐标大小从小到大排序
bool cmp(Coordinate A, Coordinate B) {return A.c < B.c;}

void solve()
{
    int maxn = 3, n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> s[i].r >> s[i].c;
    sort(s + 1, s + n + 1, cmp);//排序
    int flag_0 = 2, flag_1 = 2;
    for(int i = 1; i < n; i ++)
    {
        auto [r1, c1] = s[i];
        auto [r2, c2] = s[i + 1];
        if(c1 == c2)//如果横坐标相等
        {
          //如果是左边的路被封锁，则左边的无需添加着火点。
            if(c1 < 0) flag_0 = 0;
          //如果是右边的路被封锁，则右边的无需添加着火点。
            if(c2 > 0) flag_1 = 0;
        }
        if(c1 + 1 == c2)
            if(r1 != r2)//如果相邻
            {
              //如果是左边的路被封锁，则左边的无需添加着火点。
                if(c1 < 0) flag_0 = 0;
              //如果是右边的路被封锁，则右边的无需添加着火点。
                else flag_1 = 0;
            }
    }
    for(int i = 1; i <= n; i ++)
    {
        auto[r1, c1] = s[i];
      //如果为鸡的初始坐标下面
        if(r1 == 2 && c1 == 0) maxn --;
      //如果为鸡的初始坐标右边
        if(r1 == 1 && c1 == 1) maxn --;
      //如果为鸡的初始坐标左边
        if(r1 == 1 && c1 == -1) maxn --;
      //如果左边没有被封锁，且有一个着火点
        if(flag_0 > 0 && c1 <= 0)
            flag_0 = 1;
      //如果右边没有被封锁，且有一个着火点
        if(flag_1 > 0 && c1 >= 0)
            flag_1 = 1;
    }
  //两种关住鸡的方法的所需最小数量的对比，选小的
    cout << min(maxn, flag_0 + flag_1) << '\n';
}

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin >> t;
    while(t --)
        solve();

    return 0;
}

C-按闹分配

思路：

  • 这题的难点其实是定位很急的鸡插队的位置
  • 另一种就是比较基础的前缀和知识了。
  • 易得，鸡插队的时间必须在一个人和另一个人之间才能做到等待时间最小
  • 且插队后，想要满足 实际就是满足

以下是代码部分，用（快速查询定位，时间消耗更高）

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

typedef long long ll;
const int N = 1e5 + 10;
ll t[N];
ll r, l, m;
//快速查询
void finds(ll n, ll t_c, ll M)
{
    r = n, l = 0;
    m = ((r + l) >> 1);
    while(l < r - 2)
    {
      //中间位置
        m = ((l + r) >> 1);
      //如果插队队太前面了，不合法了
        if((n - m) * t_c > M)
            l = m;//左端移到中间位置
      //如果插队太后面了
        else if((n - m) * t_c <= M)
            r = m;//右端移到中间位置
    }
}

int main()
{
    ll q, n, t_c, M;
    ios::sync_with_stdio(false);
    cin >> n >> q >> t_c;
    for(int i = 1; i <= n; i ++) cin >> t[i];
    sort(t + 1, t + n + 1);
  //前缀和
    for(int i = 1; i <= n; i ++)
        t[i] = t[i] + t[i - 1];
    while(q --)
    {
        cin >> M;
        finds(n, t_c, M);
        for(ll i = l; i <= r; i ++)
            if((n - i) * t_c <= M)
            {
                cout << t[i] + t_c << endl;
                break;
            }
    }

    return 0;
}

以下是代码部分——（通过计算查询位置）参考来源——jiangly

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

typedef long long ll;

int main()
{
    int n, Q, tc;
    ios::sync_with_stdio(false);
    cin >> n >> Q >> tc;
    vector<ll> t(n + 1);
    for(int i = 1; i <= n; i ++)
        cin >> t[i];
    sort(t.begin(), t.end());
    for(int i = 1; i <= n; i ++)
        t[i] += t[i - 1];
    while(Q --)
    {
        ll M;
        cin >> M;
      //（n - pos）* tc <= M
        ll c = min((ll)n, M / tc);//防止越界
        ll ans = t[n - c] + tc;
        cout << ans << '\n';
    }

    return 0;
}

D-数组成鸡

以下是代码部分，参考代码来源于出题人写的题解

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

typedef long long ll;
constexpr int Inf = 1e9, N = 2e5 + 10;
ll a[N];
int n;
set<int> s;

//检查是否超过了 1e9
bool check(ll x)
{
    ll res = 1;
    for(int i = 1; i <= n; i ++)
    {
        res *= a[i] + x;
        if(llabs(res) > Inf) return false;
    }
    s.emplace(res);
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int q, M; cin >> n >> q;
    ll l, r;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    //必定可以输出0， 先放入0
    s.emplace(0);
  //降低接下来的判断时间
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] == a[i - 1]) continue;
        for(l = -a[i] - 1; check(l); l --);
        for(r = -a[i] + 1; check(r); r ++);
    }
    while(q --)
    {
        cin >> M;
        cout << (s.count(M) ? "Yes\n" : "No\n");
    }

    return 0;
}

E-本题又主要考察了贪心

思路：

  • 其实是dfs做法(深度优先搜索) -也可以用状压
    • 以代表对局情况
    • 总共有 种， 枚举每一种情况

以下是代码部分（状压），代码参考来源——Scarlett_come_here

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

const int N = 15;
//a[]为原积分， now[]为比完赛后的现积分
int a[N], now[N];
int u[N], v[N];
int pw3[N];

void solve()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= m; i ++) cin >> u[i] >> v[i];
    int maxn = n;
    for(int i = 0; i < pw3[m]; i ++)
    {
      //存入到现积分中
        for(int j = 1; j <= n; j ++) now[j] = a[j];
        int p = i;//p 代表第几种情况
        for(int j = 1; j <= m; j ++)
        {
            if (p % 3 == 0)
                now[u[j]] += 3;
            else if(p % 3 == 1)
                now[v[j]] += 3;
            else
                now[u[j]] ++, now[v[j]] ++;
            p /= 3;
        }
        int id = 1;
        for(int j = 2; j <= n; j ++)
            if (now[j] > now[1]) id ++;
        maxn = min(maxn, id);
    }
    cout << maxn << '\n';
}

//预处理
void init()
{
  //pw3代表在总共有i场比赛时有多少种状态
    pw3[0] = 1;
    for(int i = 1; i <= 10; i ++)
        pw3[i] = pw3[i - 1] * 3;
}

int main()
{
    init();
    ios::sync_with_stdio(false);
    int t;cin >> t;
    while(t --) solve();

    return 0;
}

F-鸡数题

思路：

  • 第二类stirling
  • alt

以下是代码部分

#include "bits/stdc++.h"

using namespace std;
const int mod = 1e9 + 7, N = 1e5 + 10;
typedef long long ll;

ll c[N], invc[N];

ll power(ll base, ll pow) {
    ll res = 1;
    while (pow)
    {
        if(pow & 1)
            res = base * res % mod;
        pow >>= 1;
        base = base * base % mod;
    }

    return res;
}

ll inv(ll x) {return power(x,  mod - 2);}

void init()
{
    //求阶乘
    c[0] = 1;
    for (int i = 1; i < N; i++) c[i] = c[i - 1] * i % mod;
    //求最大阶乘的逆元
    invc[N - 1] = inv(c[N - 1]);
    //求每一个的逆元
    for (int i = N - 2; i >= 0; i--) invc[i] = invc[i + 1] * (i + 1) % mod;
}

//求组合数
ll C(int n, int m)
{
    if (m < 0 || m > n || n < 0) return 0;
    return c[n] * invc[m] % mod * invc[n - m] % mod;
}

int main() {
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    init();//预处理

    ll ans = 0;
    //第二类stirling数
    for (int k = 0; k <= m; k++) {
        if (k % 2 == 0)
            ans = (ans + C(m, k) * power(m - k, n) % mod) % mod;
        else
            ans = (ans - C(m, k) * power(m - k, n) % mod + mod) % mod;
    }
    cout << ans * invc[m] % mod << '\n';

    return 0;
}

G-why买外卖

思路：

  • 贪心，从大到小排列
  • 用后缀和储存

以下是代码部分

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

typedef long long ll;
const int N = 1e5 + 10;
//存储减免券
typedef struct Mjian{
    int a;
    ll b;
}Mjian;

Mjian ab[N];
//从大到小按照a的大小排列
bool cmp1(Mjian x, Mjian y) {return x.a > y.a;}
//判断是否可以购买 
bool judge(int n, int m)
{
    for(int i = 1; i <= n; i ++)
        if(ab[i].a - ab[i].b <= m)
        {
          //如果可以购买直接输出
            cout << ab[i].b + m << endl;
            return true;
        }
  //全都不行，则直接输出m
    return false;
}

int main()
{
    int t, n, m;
    cin >> t;
    while(t --)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i ++)
            cin >> ab[i].a >> ab[i].b;
        sort(ab + 1, ab + n + 1, cmp1);
      //后缀和
        for(int i = n - 1; i >= 1; i --)
            ab[i].b = ab[i].b + ab[i + 1].b;
        if(!judge(n, m))
            cout << m << endl;
    }

    return 0;
}

H-01背包，但是bit

思路：牛客竞赛官方题解

alt

具体实现步骤见代码部分，代码参考与——另一篇题解， Kidding_Ma

  • 附注释
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> v(n), w(n);
    //输入物品的价值及重量
    for (int i = 0; i < n; i++)
        cin >> v[i] >> w[i];
    //lambda写法，相当于自定义了一个函数
    auto get = [&](int x) {
        ll res = 0;
        for (int i = 0; i < n; i++) {
            if ((x & w[i]) == w[i])
                res += v[i];
        }
        return res;
    };
    //先求出取的1为m的最大的1的情况时， 可取的最大价值
    ll ans = get(m);
  //此方法跳过了初始时最低位的1，初始时最低位的1后面并不能装任何东西
  //同时也排除了取的1为最高位为1的情况
    //           i是否为真    （i & -i）取到 i 最低位的 1
    for (int i = m; i; i -= (i & -i))//i - (i & -i)做到把取到1的这一位强制变为0
        ans = max(ans, get(i - 1));// i-1 做到后面的全变为 1
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}

I-It's bertrand paradox. Again!

思路：

  • 方法一，模拟出两种画圆的方法

    • 取特征值来判断是哪种

  • 方法二，通过数据概率，找到特征值， 比较在区域的概率——Kidding_Ma的题解

    • 第一种圆的圆心在范围内均匀分布
    • 第二种圆的圆心分布更靠近中心

  • 已知， 取的差值即可（不能过小）

以下是方法二的代码部分

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

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i ++)
    {
        int x, y, r;
        cin >> x >> y >> r;
        if(abs(x) <= 9 && abs(y) <= 9)
            ans ++;
    }
    if(abs(ans * (199 * 199) - 19 * 19 * n) <= 18000000)
        cout << "bit-noob\n";
    else
        cout << "buaa-noob\n";

    return 0;
}

J-又鸟之亦心

思路：

  • 二分查找最大距离的最小值
  • 其中判断的时候用s存储被派去的分部的位置
  • 如果s当中有元素存在，也就是在d的距离下,有合法位置
  • 如果s为空，就代表没有合法位置使得d距离成立

以下是代码部分，代码参考来源——jiangly 

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

typedef long long ll;
constexpr int N = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, x, y;
    //输入
    cin >> n >> x >> y;
    vector<int> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];

    //检查m的距离是否合法
    auto check = [&](int d)
    {
      //记录其中一人的位置
        int lst = y;
        set<int> s;
      //把其中一个人的位置存入
        if(abs(x - y) <= d)
            s.insert(x);
      //遍历需要出差的地方
        for(auto tem : a)
        {
          //集合s非空 并且 距离合法，存入集合内
            if (!s.empty() && abs(tem - lst) <= d)
                s.insert(lst);
          //集合s非空 并且 距离不合法 删除不合法的值
            while (!s.empty() && *s.begin() < tem - d)
                s.erase(*s.begin());
          //集合非空 并且 距离不合法 删除不合法的值
            while (!s.empty() && *s.rbegin() > tem + d)
                s.erase(*s.rbegin());
          //更新位置
            lst = tem;
        }
        return !s.empty();
    };

    int lo = 0, hi = 1e9;
    while(lo < hi)
    {
        int m = (lo + hi) / 2;
        if(check(m))
            hi = m;
        else
            lo = m + 1;
    }
    cout << lo << '\n';

    return 0;
}

K- 牛镇公务员考试

思路：

  • 图论，置换环

以下是代码部分， 代码参考来源——Kidding_Ma的题解

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

using ll = long long;
constexpr int mod = 998244353;

int main() {
    ios::sync_with_stdio(false);
    ll ans = 1;
    int n; cin >> n;
    //第i题指向第ai题
    vector<int> a(n);
    //记录这一题的选项
    vector<string> s(n);
    //标记是否已经处理过
    vector<bool> vis(n);
    //输入，为使下标统一， a[i] --
    for (int i = 0; i < n; i++)
        cin >> a[i] >> s[i], a[i]--;

    for (int i = 0; i < n; i++)
    {
        //每题都串联起来

        int j = i;
        //存储题目之间的串联关系
        vector<int> c;
        //当第j题没有被串联时
        for (; !vis[j]; j = a[j])
            //串联，并存入c中
            vis[j] = true, c.push_back(j);
        //找到 j
        auto it = find(c.begin(), c.end(), j);
        //如果j被找到也就是，如果c[j]成功存入
        if (it != c.end())
        {
            //避免重复处理
            //删掉c[0]到it之前的数据,也就是删掉连在环上的链
            c.erase(c.begin(), it);
            // res 统计这个环的答案种类数
            int res = 0;
            //暴力枚举有几种情况
            for (char st = 'A'; st < 'F'; st ++)
            {
                //如果cur能折法回来和原来相同的选项，则合法
                char cur = st;
                for (auto x : c)
                    cur = s[x][cur - 'A'];
                res += (cur == st);
            }
            ans = ans * res % mod;
        }
    }
    cout << ans << '\n';

    return 0;
}

L-要有光

思路：

  • 当光源放到地上的时候阴影面积最大
  • 后用梯形面积公式求阴影面积即可

以下是代码部分

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

int main()
{
    int t, c, d, h, w;
    cin >> t;
    while(t --)
    {
        cin >> c >> d >> h >> w;
        printf("%.6lf\n", 3.0 * w * c);
    }

    return 0;
}

M-牛客老粉才知道的秘密

思路：

  • 找规律发现和6有关

以下是代码部分

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

int main()
{
   int t, n;
   cin >> t;
   while(t --)
   {
       cin >> n;
       int sum = n / 6;
       sum += (n % 6 != 0) * sum;
       cout << sum << endl;
   }

    return 0;
}
全部评论

相关推荐

头像 会员标识 头像
程序员小白条
05-06 15:43
门头沟学院 计算机类
腾讯测试开发二面
腾讯测试开发二面&nbsp;总体时间大多在&nbsp;30&nbsp;分钟左右，无算法。&nbsp;1）实习时间询问&nbsp;2）实习经历介绍&nbsp;3）简历项目介绍&nbsp;4）开源项目介绍&nbsp;项目介绍主要是：为什么做这个项目？需求分析？技术选型？业务流程？后续优化？扩展点？&nbsp;面试官主要感兴趣的就是在于业务流程，优化点，AIGC&nbsp;这几个点。&nbsp;5）共享屏幕，看开源项目和简历项目，因为已经上线了，直接看就完事了...面试官问&nbsp;UI&nbsp;有没有设计过，我说没有，面试官说看着还行.jpg&nbsp;6）性能优化，慢查询&nbsp;SQL，缓存（本地，中间件，网关）集群....&nbsp;7）多线程学习&nbsp;8）垃圾回收介绍，很宽泛的问题，想讲什么都可以讲一些。&nbsp;9）反问面试轮次，业务，面试表现和建议...
软件开发2024笔面经
点赞 评论 收藏
转发
头像 会员标识 头像
炫光
昨天 17:18
中国移动信息技术公司_软件开发(准入职员工)
国/央企的一些信息差
#校招过来人的经验分享#&nbsp;#国企#&nbsp;#央企#（1）实习是有用的不要觉得国企央企不看实习，过去可能真的不看，现在国企央企卷的飞起，如果大家学历差不多，实习经历还是挺大的加分项（2）同档次国企薪资差距不会太大大部分顶级央企/国企，如果是技术岗，给硕士开的总包，基本都是25万左右，本科生18万左右，大差不差，不会太高也不会太低（3）总包和到手的相差巨大如果去的是国/央企，承诺总包25w，很大概率其中5w是福利（不一定可以折现），然后年终奖占1/3，大概6-7w，平时的工资占2/3，大概一个月1w出头，这其中往往还包括浮动的绩效，扣掉五险一金，一个月到手7k上下都是很正常的（4）工资高的国企/央企，往...
点赞 评论 收藏
转发
7 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
559708次浏览 9429人参与
# 简历中的项目经历要怎么写 #
406072次浏览 6783人参与
# 如何写一份好简历 #
238849次浏览 3678人参与
# 我的成功项目解析 #
76927次浏览 2275人参与
# 海康威视求职进展汇总 #
84769次浏览 1044人参与
# 你已经投递多少份简历了 #
272259次浏览 4174人参与
# 我的失利项目复盘 #
198441次浏览 4380人参与
# 我的上岸简历长这样 #
150384次浏览 3016人参与
# 你的简历改到第几版了 #
284324次浏览 4352人参与
# 浅聊一下我实习的辛苦费 #
75708次浏览 705人参与
# 你觉得比亚迪今年还有春招吗？ #
40859次浏览 292人参与
# 现在还是0offer，延毕还是备考 #
341695次浏览 4396人参与
# 我想象的工作vs实际工作 #
83746次浏览 1446人参与
# 比亚迪求职进展汇总 #
152119次浏览 1158人参与
# 春招你拿到offer了吗 #
342559次浏览 5119人参与
# 租房前辈的忠告 #
25630次浏览 1896人参与
# 双非本科求职如何逆袭 #
189964次浏览 2794人参与
# 我发现了面试通关密码 #
304646次浏览 5849人参与
# 远程面试的尴尬瞬间 #
2912次浏览 69人参与
# 晒一晒我的offer #
3083692次浏览 51961人参与
牛客网
牛客企业服务