题目大意

一个正整数是波浪数，当且仅当这个正整数中的任意相邻两位数码拥有不同的奇偶性。

现在，给出一个正整数 $N$，请计算与 $N$ 数值最接近的波浪数。答案可能只有一个，也可能会有两个。

思路

构造+大模拟

我们首先可以发现，所有的可能性无非只有 $\text{奇偶奇偶奇}\cdots$ 或者 $\text{偶奇偶奇偶}\cdots$ 两种情况。那么都分别尝试构造即可。每一组情况均有往小靠和往大靠两种情况。我们去分类讨论。

之后我们发现，如果一个数之前已经增大/减少了，那么就要往反方向走，因为如果持续增大/减少的话数就会越来越极端。还有一些小细节，比如增大的数现在是奇数结果碰到了 $9$，或者减少的数要求偶数现在是 $0$。但是好像老师没卡。

之后我们就得出了四个数，那么按照之间的距离写一个排序即可。但是减法要写高精度。字符串反转看错函数了与+'0'写成-'0'了调了半个小时，警钟长鸣。

之后我们判断前两个数与 $n$ 的差是否相等，如果是的话就输出两个数，否则输出一个数。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;
const ll MAXN = 1000 + 5;
string n, ans[5];
char a1[MAXN], a2[MAXN];
char c[MAXN];
ll s[MAXN];

void a() {
    ll sz = 0;
    for (int k = 0; k <= 1; ++k) {
        ll K = k;
        memset(a1, 0, sizeof(a1));
        memset(a2, 0, sizeof(a2));
        bool small = false, big = false, big_small = false, small_big = false;
        for (int i = 0; i < n.size(); ++i) {
            if (K) {
                //要求奇数
                if ((n[i] - '0') % 2 == 0) {
                    if (big_small) {
                        a1[i] = '1';
                    } else if (small) {
                        a1[i] = '9';
                    } else {
                        if (n[i] == '0') {
                            big_small = true;
                            a1[i] = '1';
                        } else {
                            small = true;
                            a1[i] = n[i] - 1;
                        }
                    }
                    if (small_big) {
                        a2[i] = '8';
                    } else if (big) {
                        a2[i] = '1';
                    } else {
                        if (n[i] == '9') {
                            a2[i] = '8';
                        } else {
                            big = true;
                            a2[i] = n[i] + 1;
                        }
                    }
                } else {
                    if (big_small) {
                        a1[i] = '1';
                    }
                    if (small) {
                        a1[i] = '9';
                    } else {
                        a1[i] = n[i];
                    }
                    if (small_big) {
                        a2[i] = '8';
                    } else if (big) {
                        a2[i] = '1';
                    } else {
                        a2[i] = n[i];
                    }
                }
            } else {
                if ((n[i] - '0') % 2 == 0) {
                    if (big_small) {
                        a1[i] = '1';
                    }
                    if (small) {
                        a1[i] = '8';
                    } else {
                        a1[i] = n[i];
                    }
                    if (big) {
                        a2[i] = '0';
                    } else {
                        a2[i] = n[i];
                    }
                } else {
                    if (big_small) {
                        a1[i] = '1';
                    }
                    if (small) {
                        a1[i] = '8';
                    } else {
                        small = true;
                        a1[i] = n[i] - 1;
                    }
                    if (small_big) {
                        a2[i] = '8';
                    } else if (big) {
                        a2[i] = '0';
                    } else {
                        if (n[i] == '9') {
                            small_big = true;
                            a2[i] = '8';
                        } else {
                            big = true;
                            a2[i] = n[i] + 1;
                        }
                    }
                }
            }
            K = (K + 1) % 2;
        }
        ans[++sz] = a1;
        ans[++sz] = a2;
    }
}

string sub(string a, string b) {
    memset(c, '\0', sizeof(c));
    if (a.size() < b.size()) {
        swap(a, b);
    } else if (a < b && a.size() == b.size()) {
        swap(a, b);
    }
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    for (int i = 0; i < b.size(); ++i) {
        s[i] = a[i] - b[i];
    }
    for (int i = b.size(); i < a.size(); ++i) {
        s[i] = a[i] - '0';
    }
    for (int i = 0; i < a.size(); ++i) {
        if (s[i] < 0) {
            s[i] += 10;
            s[i + 1]--;
        }
    }
    for (int i = 0; i < a.size(); ++i) {
        c[i] = s[i] + '0';
    }
    string S = c;
    reverse(S.begin(), S.end());
    return S;
}

bool cmp(string a, string b) {
    return sub(a, n) < sub(b, n);
}

bool e(string a, string b) {
    return sub(a, n) == sub(b, n);
}

int main() {
    cin >> n;
    a();
    sort(ans + 1, ans + 5, cmp);
    if (e(ans[1], ans[2]) && ans[1] != ans[2]) {
        cout << ans[1] << " " << ans[2] << endl;
    } else {
        cout << ans[1] << endl;
    }
    return 0;
}
复制代码

总结

像这种要求构造出一个符合条件的数可以多手搓几组例子看一看规律。如果不要求输出符合条件的数而是输出某个值，比如本题波浪数与 $n$ 的差就要多考虑一下 dp 了。但是本题一看就知道要求构造。

还是以不变应万变的思路。本题不变的东西是波浪数每一位的奇偶性。变的就是 $n$ 的每一位的奇偶性。那么考虑拼搭即可。