今日校赛在数据和题面上存在太多问题，给诸位道歉！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());
    }
}

题解 | #最小半径#

A 最小半径

参考代码

C/C++

Java

B H老师的竞赛宣讲

参考代码

C/C++

Java

C 李渊的准备

参考代码

C/C++

Java

D 猫狗站队

参考代码

C/C++

Java

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

参考代码

C/C++

Java