牛客练习赛111题解

好像没写过整个比赛的题解，都是写的散题的题解，今天写写试试，主要是因为今天牛客打的不错。

A

题意

已知 $AA$ ，求最小的正整数 $BB$ ，使得 $A+BA+B$ 产生进位

思路

如果想让 $BB$ 最小，则让 $AA$ 的最低不为 $00$ 位产生进位就好了。设最后一位为 $xx$ ，则有 $(10-x\mathrm{m}\mathrm{o}\mathrm{d}10)\times 10^{\mathrm{后}\mathrm{缀}\mathrm{零}\mathrm{个}\mathrm{数}}(10-x\backslash mod10)\backslash times10^\{后缀零个数\}$ 就可以产生进位。

代码

void solve()
{
	int n;
	cin >> n;
	int res = 1;
	while (n)
	{
		if (n % 10)
		{
			cout << res * (10 - n % 10) << "\n";
			return;
		}
		res *= 10;
		n /= 10;
	}
}

B

题意

对于两个字符串 $S_1,S_{2}S\_1,S\_2$ ，问，能否恰好用一次交换，交换 $S_{1}S\_1$ 中两个不同位置，使得 $S_1=S_{2}S\_1=S\_2$

思路

当看到恰好的时候，我们就应该思考，是不是有坑。

首先，很明显，一次交换能够达成的必要条件是，$S_{1}S\_1$ 是 $S_{2}S\_2$ 的一个排列，也就是说，$S_{1}S\_1$ 可以通过 $S_{2}S\_2$ 重新排列字符得到。

然后，考虑更简单一点的情况，如果 $S_1=S_{2}S\_1=S\_2$ ，那么就一定可以做到了吗？很明显，我们必须要做一次交换，而如果 $S_{1}S\_1$ 中没有相同的字符，那么我们就会将原来的相等给变为不相等了；否则，就一定可以完成。

最后，再检查，$S_{1}S\_1$ 中有几个位置和 $S_{2}S\_2$ 不相等，如果恰好有两个位置不相等，那么交换这两个位置即可。

代码

void solve()
{
	int n;
	cin >> n;
	string s1, s2;
	cin >> s1 >> s2;
	string t1 = s1, t2 = s2;
	sort(t1.begin(), t1.end());
	sort(t2.begin(), t2.end());
	if (t1 != t2)
	{
		cout << "NO\n";
		return;
	}
	map<char, int> cnt;
	int f = 0;
	for (char c : s1)
	{
		if (cnt[c])f = 1;
		cnt[c]++;
	}
	if (s1 == s2)
	{
		if (f)cout << "YES\n";
		else cout << "NO\n";
		return;
	}
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		res += s1[i] != s2[i];
	}
	if (res == 2)cout << "YES\n";
	else cout << "NO\n";
}

C

题意

给定正整数 $m,xm,x$ ，求 $yy$ 的个数，使得，对于任意的正整数 $kk$ ，都满足

思路

直接找到最大的 $kk$ ，记为 $k_{mid}k\_\{mid\}$ ，使得 $kx\le mkx\backslash leq\; m$ ，则 $k_{mid}=\lfloor {\displaystyle \frac{m}{x}}\rfloor k\_\{mid\}=\backslash lfloor\backslash cfrac\{m\}\{x\}\backslash rfloor$ 。则我们应该有以下等式

整理可得

则区间长应该是 $\lfloor {\displaystyle \frac{m}{k_{mid}}}\rfloor -\lfloor {\displaystyle \frac{m}{k_{mid}+1}}\rfloor \backslash lfloor\backslash cfrac\{m\}\{k\_\{mid\}\}\backslash rfloor-\backslash lfloor\backslash cfrac\{m\}\{k\_\{mid\}+1\}\backslash rfloor$

代码

void solve()
{
	int m, x;
	cin >> m >> x;
	int mid = m / x;
	int ans1 = m / (mid + 1);
	int ans2 = m / mid;
	cout << ans2 - ans1 << "\n";
}

D

题意

有两个人在 $xx$ 轴上，一个从 $00$ 出发，一个从 $nn$ 出发，相向而行，左边的人一步是 $aa$ ，右边的人一步是 $bb$ 。现在，右边的人可以走任意步，左边的人想在自己走 $[L,R][L,R]$ 步的情况下和右边的人相遇

思路

先不考虑走多少步的情况，则可以发现，这个题就是一个二元一次方程的模板题，有

无论限制如何，这个方程首先得有解。记 $g=gcd(a,b)g\; =\; gcd(a,b)$ ，则必须有 $g\mathrm{\mid }ng|n$ 。

不妨记 $xx$ 的一个特解为 $x^{\mathrm{\prime }}x\text{'}$ ，则有通解为 $x=x^{\mathrm{\prime }}+{\displaystyle \frac{b}{g}}tx=x\text{'}+\backslash cfrac\{b\}\{g\}t$ ，其中 $tt$ 为任意整数。

现在回来思考步数的限制，所谓步数，就是 $xx$ 。也就是说，我们需要找到一个 $tt$ ，使得

可以发现，这道题的复杂度，对于一个 testcase ，我们至少要用 $O(logn)O(logn)$ 的算法才能通过。实际上就算不看复杂度的提示，一样很容易想到，使用二分来解决这个问题，因为可以注意到 $x=x^{\mathrm{\prime }}+{\displaystyle \frac{b}{g}}tx=x\text{'}+\backslash cfrac\{b\}\{g\}t$ 是一个单调递增的函数。

void solve()
{
	int a, b, n, L, R;
	cin >> a >> b >> n >> L >> R;
	int x, y;
	int g = exgcd(a, b, x, y);
	if (n % g)
	{
		cout << "NO\n";
		return;
	}
	x *= n / g;
	int l = -1e9, r = 1e9;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (x + b / g * mid >= L)r = mid;
		else l = mid + 1;
	}
	int ansl = l;
	l = -1e9, r = 1e9;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (x + b / g * mid <= R)l = mid;
		else r = mid - 1;
	}
	int ansr = r;
	if (x + b / g * ansr < L || x + b / g * ansl > R)cout << "NO\n";
	else cout << "YES\n";
}