题解：P14603 [NWRRC 2025] Defense Distance

Bobi2014 · 2025-11-27 22:53:50 · 题解

这是一道可癌且毒瘤的构造题。

思路

根据莱文斯坦距离的性质，a、b、c 肯定满足三角形不等式，如果不满足那么就无解了，我们可以设定三个值，分别是 x、y、z 他们分别表示每个不同块，x 表示对 a 和 b 有贡献的块，也就是 s \ne t、t = u，那么 y、z 以此类推。

那么我们就可以列出三个二元一次方程：

• x + y = a
• x + z = b
• y + z = c

根据初中数学知识，得：

• x = \frac{a + b - c}{2}
• y = \frac{a + c - b}{2}
• z = \frac{b + c - a}{2}

但是如果 a + b + c 是奇数，那就做不了了，但是我们可以用转化的思想，让三个字符串的第一个字符不相同，然后三个数都减一，这样就转化成偶数的做法了。

注意要特判 0 0 0 的情况。

时间复杂度是线性的。

Code

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    if(a == 0 and b == 0 and c == 0){
        cout << "Yes\na\na\na";
        return 0;
    }
    if(a + b < c or a + c < b or b + c < a){
        cout << "No";
        return 0;
    }
    cout << "Yes\n";
    string s,u,v;
    if((a + b + c) % 2 == 1){
        s += 'a';
        u += 'b';
        v += 'c';
        a --;
        b --;
        c --;
        if(a == 0 and b == 0 and c == 0){
            cout << s << "\n" << u << "\n" << v;
            return 0;
        }
    }
    int x = (a + b - c) / 2;
    int y = (a + c - b) / 2;
    int z = (b + c - a) / 2;
    s += string(x,'a');
    u += string(x,'b');
    v += string(x,'b');
    s += string(y,'a');
    u += string(y,'b');
    v += string(y,'a');
    s += string(z,'a');
    u += string(z,'a');
    v += string(z,'b');
    cout << s << "\n" << u << "\n" << v;
    return 0;
}