竞赛讨论区 > 牛客小白月赛88 出题人题解
头像
WIDA
编辑于 03-20 21:24
+ 关注

牛客小白月赛88 出题人题解

牛客小白月赛88 出题人题解

出题人：WIDA  。

协调员：tokitsukaze 。

第一轮内测同学：Hamine，_rsy，464zzyx，想打一辈子算法竞赛怎么办，silverbullet23，honey__ 。

第二轮内测同学：xxiu_，djwcb，cstdios，xfy_，yangjl⁣⁣⁣⁣，lz214，wy/，薛定谔的上帝，爱音乐的博博，_锦木千束，you_xiao，这题你已经AC了，Sakura_t，枫系，HQPYH，octal，蔡光，tarjen，-.--.--.-，liangqianxing，jackle 。

希望大家今晚玩的开心~

题目总览与预期

编号 题目 难度 Tag 预期通过率 实际通过率
A 超级闪光牛可乐 *800 构造
B 人列计算机 *900 模拟, 字符串
C 时间管理大师 *1100 模拟, 数据结构
D 我不是大富翁 *1400 动态规划, 数学
E 多重映射 *1600 贪心, 数据结构, 图论
F 现在是消消乐时间 *1700 构造, 数论, 搜索, 模拟, 暴力
G 三点不共线 *1700 几何, 数论, 构造

小结：

就 G 题的题面缺陷道歉，在书写时出现了纰漏，非常抱歉！

本场比赛的 idea 来自于我 2023 年初为实验室大一学弟学妹们出的训练赛，在2023年ICPC南京站前夕就已经投稿了，由于种种原因放出的较迟，但是很高兴最终能在六个月后与大家见面！比赛借鉴了 sua 命题组的题面风格以及 Polygon 对于题面 Markdown 语法的要求，尽可能的做到了规范。题目先后一共进行了八轮修改、三次验题，非常不容易，希望大家能喜欢最终呈现的这一版本题目。

本场总体情况符合预期，唯一的小问题在 F 的通过人数，标程不难实现，但是可能 G 更加易上手导致排行榜歪了。

关于这一题还有一个小插曲，在于原先 F 是在 E 的位置上，范围更宽松、允许 的做法通过，另有一个 hard ver 要求 计算出有多少合法发射位置，由于题数原因合并为一题且与 E 互换了位置（使得这场少了一道经典的数数题）。大家可以思考一下原先的这个 hard ver 该如何实现。

除此之外，本次比赛的 E 非常不幸的与前日进行的 HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342） 中的 C 题撞了 idea ，但是由于解法差异较大，在验题组讨论过后决定不做修改，大家可以看作是那一题的 ProMax 版本。

以上，再次感谢大家参加。

Update1: 彩蛋。

Problem A: 超级闪光牛可乐

*800, 100% (构造)

题解

打卡题，直接输出任意一个食物 次即可。

参考代码

int main() {
    int p;
    char op;
    cin >> p >> p >> op;
    cout << string(1000, op) << "\n";
}

出题思路

构造打卡题，主推一个好玩 狠狠偷吃清楚姐姐的零食 。

另，今天是妇女节，让我们祝清楚洁洁节日快乐！

Problem B: 人列计算机

*900, 85% (模拟, 字符串)

题解

打卡题，寻找适当的函数读入后进行模拟判断。

提供一个码量较小的做法。注意到不同的门电路之间的差别很小，从这些不同之处入手——首先检查第 行第 列的这个字符，知道逻辑门的种类，随后检查第 列的输入数据即可，其余的部分都是没有用的，读入后直接丢弃。

参考代码

int main() {
    vector<string> s(5);
    for (int i = 0; i < 5; i++) {
        getline(cin, s[i]);
    }
    
    char op = s[2][5];
    if (op == '&') {
        cout << (s[1][0] & s[3][0]) - '0' << "\n";
    } else if (op == '=') {
        cout << (s[1][0] | s[3][0]) - '0' << "\n";
    } else {
        cout << !(s[2][0] - '0') << "\n";
    }
}

出题思路

难点是读入函数的选择。本题不同写法的码量差异极大，出题人也想借此拉开各层次选手的过题速度。

如果你耗费了较多时间，建议尝试更短的写法。

Problem C: 时间管理大师

*1100, 60% (数据结构)

题解

打卡题。我们可以将给定的时间从“小时-分钟”的形式转化为“纯分钟”的形式。

具体来说， 即为第 项日程事件的“纯分钟”形式。这样做的好处在于我们可以使用一维数组来储存事件，直接进行时间计算与去重。而要重新转换回“小时-分钟”形式也非常简单，不妨使用 表示第 个闹钟响起的时间，那么小时数即为 整除 、分钟数即为 。这一思想也是哈希思想的体现。

当然，暴力模拟也能通过本题，这里不再赘述。

参考代码

const int P = 24 * 60;

int main() {
    int n;
    cin >> n;
    
    vector<bool> vis(P);
    for (int i = 0; i < n; i++) {
        int h, m;
        cin >> h >> m;
        int bell = h * 60 + m;
        vis[bell - 1] = vis[bell - 3] = vis[bell - 5] = true;
    }
    
    cout << accumulate(vis.begin(), vis.end(), 0) << "\n";
    for (int i = 0; i < P; i++) {
        if (vis[i]) {
            cout << i / 60 << " " << i % 60 << "\n";
        }
    }
}

出题思路

本题题干细节较多，主要考察读题能力；此外还需要对于数组的熟练运用。

同样的，本题不同写法的码量差异极大，如果你耗费了较多时间，建议尝试更短的写法。

Problem D: 我不是大富翁

*1400, 35% (动态规划, 数学)

题解

简单动态规划。使用 表示在第 回合 是否有可能站在 号地块，初始状态为 ，最终只需要判定 是否为 。下方描述转移：对于 可以从上一轮的 地块向左移动 个地块得到、也可以从上一轮的 地块向右移动 个地块得到——即由 和 转移。需要注意的细节是，由于是环形地图，在转移时需要针对 进行取模。时间复杂度 ，空间复杂度 。

另外值得一提的是，本题的空间限制不允许二维 long long 数组通过（希望大家都能摆脱 #define int long long 的坏习惯），你可以选择滚动数组或是使用 bool 、 int 类型数组。

参考代码

int main() {
    int n, m;
    cin >> n >> m;
    
    vector dp(m + 1, vector(n, false));
    dp[0][0] = true;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        x %= n;
        for (int j = 0; j < n; j++) {
            dp[i][j] = dp[i - 1][(j + x) % n] | dp[i - 1][(j - x + n) % n];
        }
    }
    cout << (dp[m][0] ? "YES" : "NO") << "\n";
}

出题思路

比较无聊但是具有教育意义的题目，非常浅的考察了动态规划，希望没学过动态规划和运用不熟练的同学都能够解出来。

Problem E: 多重映射

*1600, 15% (贪心, 数据结构, 图论)

题解

解法一：逆向处理

正难则反！注意到在前面进行的操作会被后面进行的操作所覆盖，不如逆序处理每一个操作。如果学习过并查集或者链表，那么会比较方便的理解本题的处理过程。

我们使用一个数组 father 记录每一个数字最终会变成什么。在初始状态下，由于没有进行过替换操作，所以所有数字的 father 均为它自己。那么，将数字 替换成数字 这一操作就可以用 father[a] = father[b] 这行代码来表示。由于逆序处理，最后 father[a] 数组中储存的就是 ​ 这个数字的最终答案。注意到本题有多组数据，每一次都初始化整个数组必然会导致超时，所以我们可以仅对使用到的数字进行初始化，同时借助哈希表 来动态处理。这一思想也是离散化思想的体现。时间复杂度 ，空间复杂度 。

注意到这与并查集非常相似，但是使用经典的并查集却无法通过本题！原因在于本题的操作需要严格按照时间先后顺序执行（有向），在此附上一组 hack 数据，简单的运用并查集大概率会得到 2 2 2 。

1
3 2
1 3 2
1 2
3 1
解法二：启发式合并

注意到每一次操作都会将更多的数字变得相同（逐渐有序），所以只需要在原先暴力修改的基础上加入一定启发式合并的思想。具体来说，在每次修改的时候，优先修改数量较少的那个数字，再通过 swap 操作复原。这一步最坏时间复杂度 约为 ，空间复杂度 ，可以通过本题。

参考代码

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        int n, m;
        cin >> n >> m;
        vector<int> in(n), l(m), r(m);
        map<int, int> fa;
        for (int i = 0; i < n; i++) {
            cin >> in[i];
        }
        for (int i = 0; i < m; i++) {
            cin >> l[i] >> r[i];
        }
        
        for (int i = m - 1; i >= 0; i--) {
            if (fa.count(r[i])) {
                fa[l[i]] = fa[r[i]];
            } else {
                fa[l[i]] = r[i];
            }
        }
        for (int i = 0; i < n; i++) {
            cout << (fa[in[i]] ? fa[in[i]] : in[i]) << " \n"[i == n - 1];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    vector<vector<int>> dic(1E6 + 1);
    
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        int n, m;
        cin >> n >> m;
        vector<int> in(n), ans;
        for (int i = 0; i < n; i++) {
            cin >> in[i];
            ans.push_back(in[i]);
            dic[in[i]].push_back(i);
        }
        
        for (int i = 0; i < m; i++) {
            int l, r;
            cin >> l >> r;
            if (l == r) continue;
            if (dic[l].size() < dic[r].size()) {
                dic[r].insert(dic[r].end(), dic[l].begin(), dic[l].end());
                dic[l].clear();
            } else {
                dic[l].insert(dic[l].end(), dic[r].begin(), dic[r].end());
                dic[r].clear();
                swap(dic[l], dic[r]);
            }
            ans.push_back(r);
        }
        
        for (auto i : ans) {
            for (auto j : dic[i]) {
                in[j] = i;
            }
            dic[i].clear();
        }
        for (int i = 0; i < n; i++) {
            cout << in[i] << " \n"[i == n - 1];
        }
    }
}

出题思路

带点毒瘤的题目，题目形象易懂、粗看上手难度较低，但是具体书写的时候较易出错（特别是学习过并查集但是不熟悉原理的同学，很容易就会误入歧途）。内测没有人能够只靠一发就 AC 这道题。

Problem F: 现在是消消乐时间

*1700, 5% (构造, 数论, 搜索, 模拟, 暴力)

题解

很容易发现的结论是，从这样的位置发射的小球必定会经过全部方格，从此入手。

解法一：过程优化的暴力搜索

如果从某个点射出的小球无法消除全部方块，那么其经过的所有点也一定不是答案，使用数组记录剪枝。由于每一个点至多被检查四次（四个方向），时间复杂度 ，空间复杂度 ，足以通过本题。需要注意的是，该方法需要开辟较大的空间，使用 vector 有超时风险。

解法二：起点优化的暴力搜索

显然，结束情况只分两种，一种是回到发射点，另一种是射向矩形的四个角。分类讨论，对于第一种情况，我们将结束情况看作是初始情况，那么发射地点可以从四个角中任选；对于第二种情况，路径上的任何一个点都可以作为起点，由于这样的路径一定不经过四个角，所以可以选择相邻四个角的点。

所以，如果存在答案，那么第 行编号为 的竖线处、第 行编号为 的竖线处一定存在一个合法发射地点。故只需要暴力测试这两个位置即可，时间复杂度 ，空间复杂度 ，可以通过本题。

解法三：数论

这一解法其实是对解法二的总结，由三部分构成：

时间复杂度 ，空间复杂度 。证明较难，此处不给出，留待读者自证。

参考代码

const int N = 2E3 + 1;
bool vis[N][N][5];

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

    vector<int> mx = {1, 1, -1, -1};
    vector<int> my = {1, -1, 1, -1};
    vector<string> str = {"UR", "UL", "DR", "DL"};

    auto clac = [&](int x, int y, int k) -> bool {
        int sum = 0;
        while (!vis[x][y][k]) {
            vis[x][y][k] = true;

            int dx = x + mx[k], dy = y + my[k];
            if ((dx < 0) + (n < dx) + (dy < 0) + (m < dy) == 2) break;
            if (dx < 0) {
                k -= 2;
            } else if (n < dx) {
                k += 2;
            } else if (dy < 0) {
                k -= 1;
            } else if (m < dy) {
                k += 1;
            }
            sum += max(x, x + mx[k]) > d;
            x += mx[k], y += my[k];
        }
        return sum == (n - d) * m;
    };

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= 3; k++) {
                if (!clac(i, j, k)) continue;
                cout << "YES\n";
                cout << i << " " << j << "\n";
                cout << str[k] << "\n";
                return 0;
            }
        }
    }
    cout << "NO\n";
}

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

    auto clac = [&](int sx, int sy) -> bool {
        vector vis(n + 1, vector(m + 1, false));
        int x = sx, y = sy;
        int dx = 1, dy = 1, cnt = 0;
        while (cnt++ <= n * m) {
            vis[x][y] = true;
            int bounce = 0;
            if (x + dx < 0 || n < x + dx) {
                dx *= -1;
                bounce++;
            }
            if (y + dy < 0 || m < y + dy) {
                dy *= -1;
                bounce++;
            }
            if (bounce == 2) break;
            x += dx, y += dy;
        }
        
        bool flag = true;
        for (int i = d; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (vis[i][j] + vis[i + 1][j] + vis[i][j + 1] + 
                    vis[i + 1][j + 1] < 2) {
                    flag = false;
                }
            }
        }
        return flag;
    };
    
    if (clac(0, 0)) {
        cout << "YES\n0 0\nUR\n";
    } else if (clac(0, 1)) {
        cout << "YES\n0 1\nUL\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    int n, m, d;
    cin >> n >> m >> d;
    if (d == n || gcd(n, m) == 1) {
        cout << "YES\n";
        cout << 0 << " " << 0 << "\n";
        cout << "UR\n";
    } else if (gcd(n, m) == 2) {
        cout << "YES\n";
        cout << 0 << " " << 1 << "\n";
        cout << "UR\n";
    } else {
        cout << "NO\n";
    }
}

Problem G: 三点不共线

*1700, 5% (几何, 数论, 构造)

题解

解法一：中垂线+三角函数

作线段 的中垂线，垂足为 ，易知这条中垂线上一定存在两个合法的点 （对称分布）。在 中，通过三角函数可以得到 的长度： 。

过 点作 点所在横线的垂线，垂足为 。在 中，通过反三角函数可以得到直线 与 轴的夹角（即为下图中的 ）： 。这样做的目的在于求解出 ，不妨记为 。

过 点作 点所在横线的垂线，垂足为 。在 中，通过三角函数可以得到 点相对于 点的坐标差 ， ： 。

最终，一个合法的 点的坐标即为 。时间复杂度 ，空间复杂度 。

解法二：中垂线+向量

这一解法其实是对解法一的优化。作线段 的中垂线，垂足为 。在 中，通过正弦函数可以得到 的长度： 。

image-20240304204355724

此时，可以通过 旋转求得 。最终，一个合法的 点的坐标即为 。时间复杂度 ，空间复杂度 。

参考代码

const double PI = acos(-1);

double toArc(double x) { // 角度转弧度
    return PI / 180 * x;
}
double dis(double x1, double y1, double x2, double y2) { // 距离公式
    double val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(val);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    
    int Task = 1;
    for (cin >> Task; Task; Task--) {
        double x1, y1, x2, y2, alpha;
        cin >> x1 >> y1 >> x2 >> y2 >> alpha;
        alpha = toArc(alpha / 2);
        
        double k = 0;
        if (x1 != x2) {
            k = (y1 - y2) / (x1 - x2);
        }
        
        double xM = (x1 + x2) / 2;
        double yM = (y1 + y2) / 2;
        double angle = atan(abs(yM - y1) / abs(xM - x1));
        double line = dis(x1, y1, xM, yM);
        line /= tan(alpha);
        
        if (k < 0) {
            cout << xM - line * sin(angle) << " " << yM - line * cos(angle) << "\n";
        } else {
            cout << xM + line * sin(angle) << " " << yM - line * cos(angle) << "\n";
        }
    }
}

const double PI = acos(-1);
const double EPS = 1E-7;

template<class T> struct Point {
    T x, y;
    Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {} // 初始化
    Point &operator+=(Point p) & { return x += p.x, y += p.y, *this; }
    Point &operator-=(Point p) & { return x -= p.x, y -= p.y, *this; }
    Point &operator*=(T t) & { return x *= t, y *= t, *this; }
    Point &operator/=(T t) & { return x /= t, y /= t, *this; }
    friend Point operator+(Point a, Point b) { return a += b; }
    friend Point operator-(Point a, Point b) { return a -= b; }
    friend Point operator*(Point a, T b) { return a *= b; }
    friend Point operator*(T a, Point b) { return b *= a; }
    friend Point operator/(Point a, T b) { return a /= b; }
    friend auto &operator>>(istream &is, Point &p) {
        return is >> p.x >> p.y;
    }
};
double toArc(double x) { // 角度转弧度
    return PI / 180 * x;
}
template<class T> Point<T> rotate(Point<T> p1, Point<T> p2) { // 旋转
    Point<T> vec = p1 - p2;
    return {-vec.y, vec.x};
}
Point<double> standardize(Point<double> vec) { // 转换为单位向量
    return vec / sqrt(vec.x * vec.x + vec.y * vec.y);
}
template<class T> double dis(T x1, T y1, T x2, T y2) { // 距离公式
    double val = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(val);
}
template<class T> double dis(Point<T> a, Point<T> b) {
    return dis(a.x, a.y, b.x, b.y);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);

    int Task = 1;
    for (cin >> Task; Task; Task--) {
        Point<double> A, B;
        double alpha;
        cin >> A >> B >> alpha;

        double deg1 = toArc(alpha / 2);
        double deg2 = PI / 2 - deg1;
        double MC = dis(A, B) / 2 * sin(deg2) / sin(deg1);
        auto vec = standardize(rotate(A, B));
        auto ans = (A + B) / 2 + vec * MC;
        cout << ans.x << " " << ans.y << "\n";
    }
}

出题思路

磨时间题，有多种做法，不熟悉公式的话难度会比较高。

2024最新求职资料大礼包领取
真题
历年笔试真题附答案
58集团23校招产品卷
商汤科技校招算法研究大类A卷
建信金科秋招金融科技-后端开发岗
全部 >
面经
面试常考问题整理
0926腾讯音乐笔试题解
Springboot全套注解解析《看不懂算我输》
管理类双非硕的23秋招记录＆反思
全部 >
内推
员工内推码获取
拼多多春招/实习点击就送啦！！！！！！
【美团】校招社招内推，所有岗位，进度可查，消息必回
携程内推携程内推码
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”