题解 | #最小半径#

最小半径

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

今日校赛在数据和题面上存在太多问题，给诸位道歉！A-E题出题人将自己简易代码发出供大家拷打，F-I等出题人整理之后再另外发出！对于大家心情和参赛体验的破坏，再次表示歉意！剩余题目整理出来后会补充发布。

A 最小半径

读取每个圆的数据，以其中一点为圆心，两点之间连线为半径画出一个圆。这两点都是在X轴上的，所以将这两点的横坐标相减取绝对值就是该圆半径。结果为这n个圆半径最小值。

参考代码

C/C++

#include<bits/stdc++.h>
using namespace std;
int n, res, x1, x2;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    res = INT_MAX;
    for(int i = 1; i <= n; ++i)
    {
        // 读入每组数据,计算最小值
        cin >> x1 >> x2;
        res = min(abs(x1 - x2), res);
    }
    cout << res;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = Integer.MAX_VALUE;
        int x1, x2;
        for(int i = 1; i <= n; ++i) {
            x1 = sc.nextInt();
            x2 = sc.nextInt();
            res = Math.min(res, Math.abs(x1 - x2));
        }
        System.out.println(res);
    }
}

B H老师的竞赛宣讲

模拟 + 排序即可。 提交次数中是包含错误提交和正确提交的。

参考代码

C/C++

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;

class Player
{
public:
    int nums, whole, id, rank;
} players[N];
int n, m;
int cmp1(Player p1, Player p2)
{
    return p1.nums == p2.nums ? p1.whole < p2.whole : p1.nums > p2.nums;
}
int cmp2(Player p1, Player p2)
{
    return p1.id < p2.id;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int i, j;
    for(i = 1; i <= m; ++i)
    {
        players[i].nums = 0, players[i].whole = 0, players[i].id = i;
        for(j = 1; j <= n; ++j)
        {
            int x, y, z;
            cin >> x >> y >> z;
            if(z == 1)
            {
                players[i].nums++;
                players[i].whole += (x - 1) * 20 + y;
            }
        }
    }
    sort(players + 1, players + m + 1, cmp1);
    players[1].rank = 1;
    for(i = 2; i <= m; ++i)
    {
        if(players[i].nums == players[i - 1].nums && players[i].whole == players[i - 1].whole)
        {
            players[i].rank = players[i - 1].rank;
        }
        else
            players[i].rank = i;
    }
    sort(players + 1, players + m + 1, cmp2);
    for(i = 1; i <= m; ++i) cout << players[i].rank << '\n' << players[i].nums << '\n' << players[i].whole << '\n';
}

Java

import java.util.Arrays;
import java.io.*;

public class Main {
    // 快速输出对象
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) {
        Scanner sc = new Scanner();
        int n = sc.nextInt(), m = sc.nextInt();
        student[] students = new student[m];
        for (int i = 0; i < m; i++) {
            students[i] = new student();
            students[i].nums = i+1;
            for (int j = 0; j < n; j++) {
                int x = sc.nextInt(), y = sc.nextInt();
                boolean isValid = sc.nextInt()== 1;
                if (isValid) {
                    students[i].time += (x - 1) * 20 + y;
                    students[i].amount++;
                }
            }
        }
        
        Arrays.sort(students, (i1, i2) -> i1.amount == i2.amount ? i1.time - i2.time : i2.amount-i1.amount);

        students[0].rank = 1;
        for (int i = 1; i < m; i++) {
            if (students[i].amount == students[i - 1].amount&&students[i].time == students[i - 1].time) {
                students[i].rank = students[i - 1].rank;
            } else {
                students[i].rank = i+1;
            }
        }
        Arrays.sort(students, (i1, i2) -> i1.nums - i2.nums);
        for (int i = 0; i < students.length; i++) {
            out.println(students[i].rank + "\n" + students[i].amount + "\n" + students[i].time);
        }
        out.flush();
    }

}

class student {
    int time, amount, nums, rank;// 耗时，数量，序号，排名
}

class Scanner {
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    // 字符串快速读入对象
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public double nextDouble() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return st.nval;
    }

    public float nextFloat() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return (float) st.nval;
    }

    public long nextLong() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return (long) st.nval;
    }

    public String next() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        return st.sval;
    }

    // 按行读入字符串
    public String readLine() {
        String s = null;
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }
}

C 李渊的准备

一个标准RMQ问题。可以用st表或者线段树等方法解决，参考代码给出的是ST表写法。

参考代码

C/C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 3;

int n, t, q ,arr[N][32];

int query(int l, int r)
{
    int k = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(arr[l][k], arr[r - (1 << k) + 1][k]);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> t >> q;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i][0];
    for (int j = 1; j <= (int)(log(n * 1.0) / log(2.0)); ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            arr[i][j] = max(arr[i][j - 1], arr[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        int res = query(l, r);
        string flag = res >= q ? "YES\n" : "NO\n";
        cout << res << " " <<  flag;
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 3;

int n, t, q ,arr[N][32];

int query(int l, int r)
{
    int k = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(arr[l][k], arr[r - (1 << k) + 1][k]);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> t >> q;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i][0];
    for (int j = 1; j <= (int)(log(n * 1.0) / log(2.0)); ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            arr[i][j] = max(arr[i][j - 1], arr[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        int res = query(l, r);
        string flag = res >= q ? "YES\n" : "NO\n";
        cout << res << " " <<  flag;
    }
}

Java

import java.util.Scanner;

public class Main {
    static int n, t, q;
    static int maxLog;
    static int[] logn;
    static int[][] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        t = sc.nextInt();
        q = sc.nextInt();
        arr = new int[n + 5][22];
        logn = new int[n + 5];
        // 预处理log
        logn[1] = 0;
        logn[2] = 1;
        for (int i = 3; i <= n; i++) {
            logn[i] = logn[i / 2] + 1;
        }
        maxLog = logn[n];
        // 读入
        for(int i = 1; i <= n; ++i) arr[i][0] = sc.nextInt();
        // 计算
        for (int j = 1; j <= maxLog; ++j) {
            for(int i = 1; i + (1 << j) - 1 <= n; ++i) {
                arr[i][j] = Math.max(arr[i][j - 1], arr[i + (1 << (j - 1))][j - 1]);
            }
        }
        for(int i = 1; i <= t; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int s = logn[r - l + 1];
            int res = Math.max(arr[l][s], arr[r - (1 << s) + 1][s]);
            if (res >= q) {
                System.out.println(res + " YES");
            } else {
                System.out.println(res + " NO");
            }
        }
    }
}

D 猫狗站队

这题出题思路是状压DP，思路来源是牛客周赛的Round32 F 小红的矩阵修改。比赛前期由于出题人std存在严重错误，给大家带来极其不好的体验。赛时经过提醒已经修改了std和测试样例，并发起了重测。

三种狗分别用0 - 1 - 2 表示，猫用 3 表示，则对于每一列，可能的情况就是四进制的 0000-3333，共 256 种情况。对于其中一列，需要确保每一位的值与相邻的值不重复(可以有相邻的3)。依次列举每一列，在判断当前列合法的情况下再去枚举上一列的状态，判断是否冲突。

最终，将最后一列各种状态的可能情况相加。

数据比较大注意开 long long，此处相邻指的在一个矩阵中上下左右四个方向而不是八个方向。

参考代码

C/C++

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int M = 15, S = 260;

/*
所有状态0000-3333 共4 ^ 4 种->256
*/

int n, m;
ll f[M][S];
int p4[5] = {1, 4, 16, 64, 256};
int b[4] = {};

// 用于检测当前列是否是合法方案
int check(int x)
{
    for(int i = 0; i < n; ++i)
    {
        b[i] = x % 4;
        x /= 4;
    }
    for(int i = 1; i < n; ++i)
    {
        // 如果有猫,肯定方案合法
        if(b[i] == 3) continue;
        // 如果有两个一样的狗,就不合法
        if(b[i] == b[i - 1]) return 0;
    }
    return 1;
}

int check(int x, int y)
{
    for(int i = 0; i < n; ++i)
    {
        int x_1 = x % 4, y_1 = y % 4;
        x /= 4;
        y /= 4;
        if(x_1 == 3 || y_1 == 3) continue;
        if(x_1 == y_1) return 0;
    }
    return 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int i, j, k;
    // 初始化第一列
    for (i = 0; i < p4[n]; ++i)
    {
        if (check(i))
        {
            f[0][i] = 1;
        }
    }
    // 枚举后面每一列
    for(i = 1; i < m; ++i)
    {
        // 枚举该列状态
        for(j = 0; j < p4[n]; ++j)
        {
            // 在当前列合法,再去检查与前面一列是否冲突
            if(check(j))
            {
                for(k = 0; k < p4[n]; ++k)
                {
                    if(check(k, j))
                    {
                        f[i][j] += f[i - 1][k];
                    }
                }
            }
        }
    }
    ll res = 0;
    for(i = 0; i < p4[n]; ++i)
    {
        res += f[m - 1][i];
    }
    cout << res;
}

Java

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static int n, m;
    static BigInteger[][] f;
    static int[] b;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int[] p4 = new int[]{1, 4, 16, 64, 256};
        int S = p4[n];
        f = new BigInteger[m][S];
        b = new int[4];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < S; ++j) {
                f[i][j] = new BigInteger("0");
            }
        }
        // 初始化第一列
        for (int i = 0; i < S; ++i) {
            if (check(i)) {
                f[0][i] = BigInteger.ONE;
            }
        }
        // 枚举后面每一列
        for (int i = 1; i < m; ++i) {
            // 枚举该列状态
            for (int j = 0; j < S; ++j) {
                // 在当前列合法,再去检查与前面一列是否冲突
                if (check(j)) {
                    for (int k = 0; k < S; ++k) {
                        if (check(k, j)) {
                            f[i][j] = f[i][j].add(f[i - 1][k]);
                        }
                    }
                }
            }
        }
        BigInteger res = BigInteger.ZERO;
        for (int i = 0; i < S; ++i) {
            res = res.add(f[m - 1][i]);
        }
        System.out.println(res);
    }
    // 用于检测当前列是否是合法方案
    static boolean check(int x) {
        for (int i = 0; i < n; ++i) {
            b[i] = x % 4;
            x /= 4;
        }
        for (int i = 1; i < n; ++i) {
            // 如果有猫,肯定方案合法
            if (b[i] == 3) continue;
            // 如果有两个一样的狗,就不合法
            if (b[i] == b[i - 1]) return false;
        }
        return true;
    }

    static boolean check(int x, int y) {
        for (int i = 0; i < n; ++i) {
            int x_1 = x % 4, y_1 = y % 4;
            x /= 4;
            y /= 4;
            if (x_1 == 3 || y_1 == 3) continue;
            if (x_1 == y_1) return false;
        }
        return true;
    }
}

E 李渊称帝，踏入神之领域

出题人思路是一个BFS题，前期题面描述上很不清楚。此题参考的是百度之星2023初赛第二场——夏日漫步。

在题目中，李渊在台阶上可以向上或向下移动。但是对于能量波动一样的能量阵，他只能穿梭到上方(编号大的台阶)最近的一个能量阵。

通过以上信息，可以建立一个简单的有向图，而后使用BFS搜索最快到达第n级台阶的情况。

参考代码

C/C++

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, arr[N], vis[N], dis[N];
vector<int> edge[N];
map<int, int> mp;
queue<int> qu;

int bfs()
{
    while (!qu.empty())
    {
        int now = qu.front();
        qu.pop();
        for (auto y : edge[now])
        {
            if (y == n)
                return dis[now] + 1;
            if (vis[y])
                continue;
            qu.push(y), vis[y] = 1, dis[y] = dis[now] + 1;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        if (i != n)
        {
            edge[i].push_back(i + 1);
            edge[i + 1].push_back(i);
        }
        if (mp.count(arr[i]))
            edge[mp[arr[i]]].push_back(i); // 能量值波动一样的
        mp[arr[i]] = i;
    }
    qu.push(1), vis[1] = 1, dis[1] = 0;
    cout << bfs();
}

Java

import java.util.*;

public class Main {
    static final int N = 200005;
    static int n;
    static int[] arr = new int[N];
    static int[] vis = new int[N];
    static int[] dis = new int[N];
    static ArrayList<Integer>[] edge = new ArrayList[N];
    static Map<Integer, Integer> mp = new HashMap<>();
    static Queue<Integer> qu = new LinkedList<>();

    static int bfs() {
        while (!qu.isEmpty()) {
            int now = qu.poll();
            for (int y : edge[now]) {
                if (y == n)
                    return dis[now] + 1;
                if (vis[y] == 1)
                    continue;
                qu.add(y);
                vis[y] = 1;
                dis[y] = dis[now] + 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; ++i) {
            edge[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; ++i) {
            arr[i] = sc.nextInt();
            if (i != n) {
                edge[i].add(i + 1);
                edge[i + 1].add(i);
            }
            if (mp.containsKey(arr[i])) {
                edge[mp.get(arr[i])].add(i);
            }
            mp.put(arr[i], i);
        }
        qu.add(1);
        vis[1] = 1;
        dis[1] = 0;
        System.out.println(bfs());
    }
}
全部评论
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=68020356&scrollToDetail=1 请教请教：我这个为啥过不去呢？
点赞 回复 分享
发布于 03-14 11:50 河北
所以B题里面 提交次数 是有0或者负数么
点赞 回复 分享
发布于 03-14 12:54 陕西
坐等后续
点赞 回复 分享
发布于 03-14 18:40 浙江
F题数据好像有点问题,题目打分是1-10分,但数据里打分有0分。
点赞 回复 分享
发布于 03-14 19:42 江苏
B题H老师的竞赛宣讲好容易超时，
点赞 回复 分享
发布于 03-19 20:38 新疆

相关推荐

头像
11-10 15:58
东北大学 Java
美团一面挂
当时脑抽投了个数开
过关斩将结果败给排序：《卓越表现》
投递美团等公司10个岗位 > 你都收到了哪些公司的感谢信？
点赞 评论 收藏
分享
11-11 08:37
门头沟学院 Java
虾皮Shopee后端复活面凉经
之前也发过一个凉经，然后换了base重新笔试以后又约面了，但是因为网传是kpi面，再加我也没抱多大希望，就面着玩儿了。一、依旧闲聊+自我介绍开局二、问简历上的项目（5min）三、八股拷打（大概25min）从在浏览器输入url到浏览器获取并展示页面的过程有哪些环节TCP三次握手四次挥手为什么要等待两个MSL流量控制和拥塞控制Linux的用户态和内核态的区别？为什么要这样划分？同步/异步/阻塞/非阻塞IOIO多路复用说一下这几种是同步还是异步？读取一次文件再通过socket发送到网络总共经过了几次拷贝？零拷贝，展开说说。SQL里having和where数据库索引为什么采用B+树而不是B树也不是哈希...
查看18道真题和解析
点赞 评论 收藏
分享
10-20 14:11
中国地质大学（武汉） 产品经理
点赞 评论 收藏
分享
11-11 19:35
门头沟学院 安全工程师
对方撤回了一个笔试
世界是个巨大的草台班子
shtdbb_：还不错，没有让你做了笔试再挂你
点赞 评论 收藏
分享
头像
11-11 19:04
华中科技大学 嵌入式软件工程师
嵌入式学习路线
写在前面，从研一才开始学习C、C++，研一基本就在乱七八糟学，没有章法，基本算是走了一年弯路，然后到研二才开始认真的准备linux学习。所以下面的推荐路线就是我把踩过的弯路掰直以后的推荐学习路线，基本需要一年左右的时间。当然一下的推荐路线极具个人色彩，可以按照自己的情况来更改！分成下面几个阶段：基础阶段（3个月）C&nbsp;C++&nbsp;stm32(简略学学就行linux系统编程(韦东山速过刷一些算法题多读书！中期阶段（4个月）uboot移植linux各种简单驱动多读书！提高阶段（6个月）linux内核各种子系统的细节网卡驱动相机驱动用一些项目做依托，同时还能复习前面的知识多读书！复盘总结（一个月）总结语言...
嵌入式学习路线
点赞 评论 收藏
分享
4 收藏 评论
分享

全站热榜

正在热议
# 晒一晒我的offer #
9510426次浏览 103812人参与
# 数据人offer决赛圈怎么选 #
106793次浏览 1392人参与
# 签约/解约注意事项 #
301718次浏览 1886人参与
# 互联网没坑了，还能去哪里？ #
1091189次浏览 12659人参与
# 我的实习求职记录 #
5941690次浏览 82713人参与
# 机械制造面试点评 #
32995次浏览 269人参与
# 你的秋招第一场笔试是哪家 #
38442次浏览 533人参与
# 机械制造公司评价 #
81675次浏览 257人参与
# AI了，我在打一种很新的工 #
18969次浏览 424人参与
# 大疆求职进展汇总 #
394242次浏览 2832人参与
# 数据人的面试交流地 #
425135次浏览 7714人参与
# 许愿池 #
202510次浏览 2485人参与
# 非技术er求职现状 #
20515次浏览 186人参与
# 那些拿到大厂offer的简历长啥样 #
105858次浏览 2054人参与
# 入职第一天，你准备什么时候下班 #
20536次浏览 133人参与
# 你/你领导的口头禅是什么？ #
3466次浏览 31人参与
# 深信服求职进展汇总 #
127371次浏览 1385人参与
# 你想留在一线还是回老家？ #
7512次浏览 156人参与
# 还记得你第一次面试吗？ #
17304次浏览 221人参与
# 通信硬件公司评价 #
80713次浏览 356人参与
牛客网
牛客企业服务