题解：P15086 [UOI 2025 II Stage] A+B=C

· · 题解

前言

下文均采用 C++23 的标准。

洛谷题目

思路

一眼看去没思路，第二眼看去发现暴力不会 TLE，选择直接暴力枚举。

解法

记 s_i 表示数字 i 需要的火柴棒数量，0\sim9 表示 [0,9]\cap\Z。

我们考虑枚举 a 通过火柴棒移动得到新的数字 a'，然后计算 b'=c-a'，如果 s_{a'}+s_{b'}=s_a+s_b，则我们就找到了解。注意需要判断 b' 是否处在 0\sim9。

时间复杂度分析

枚举只需枚举 0\sim9，共 10 次，显然不会超时。

代码

#define ups(i,st,nd) for(int i=(st);i<(nd);++i)

int seg[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int a, b, c, s;

signed main() {
    ios::sync_with_stdio(false), ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); clock_t timr_start = clock();

    read(a, b, c), s = seg[a] + seg[b];

    ups(x, 0, 10) {
        int y = c - x;
        if (y < 0 || y > 9) continue;
        if (seg[x] + seg[y] == s) {
            write("Yes");
            return 0;
        }
    }

    write("No");

    cerr << "time use " << (clock() - timr_start) << "ms.";
    return 0;
}

评价

难度大概在红和橙的过度，可以给刚学枚举的同学练习。