题解：P14603 [NWRRC 2025] Defense Distance

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

思路

根据莱文斯坦距离的性质，

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

CPP

#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;
}

题解：P14603 [NWRRC 2025] Defense Distance

文章操作

思路

Code

相关推荐

评论

题解：P14603 [NWRRC 2025] Defense Distance