自动搬运

查看原文

来自洛谷，原作者为

	Swordmaker 式波·明日香·兰格雷

搬运于2025-08-24 23:15:27，当前版本为作者最后更新于2025-05-05 18:28:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12419 【MX-X12-T2】「ALFR Round 5」Dream of Sky

思路

如果两者长度不同，则可以构造出长度等于 $l$ 的长度且全为 $1$ 的序列，答案为 $1$。

否则，贪心寻找 $l$ 和 $r$ 第一个不一样的位置。

由于要求找最小的权值，所以我们尽量构造出一长串数字相等的结构。

将较小的数字在不一样的位置后面的数字全换成 $1$，而较大的则换成 $0$。

将两个新的数字和原来两个旧的数字进行比较，找最优解。

不要忘记特判 $l$ 和 $r$ 相等的情况。

code

#include<bits/stdc++.h>
#define int long long 
#define l1 l_1
#define l2 l_2
namespace AyanamiRei
{
	inline int read()
	{
		int x=0,f=1;
		char c=getchar();
		while(c>'9'||c<'0')
		{
			if(c=='-') f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
		{
			x=(x<<3)+(x<<1)+(c-'0');
			c=getchar();
		}
		return x*f;
	}
}
namespace SoryuAsukaLangley
{
	inline void write(int x)
	{
		if(x<0) putchar('-'),x=-x;
		if(x>9) write(x/10);
		putchar(x%10+'0');
		return;
	}
}
using namespace std;
using namespace AyanamiRei;
using namespace SoryuAsukaLangley;
int t,l1,l2;
string a,b;
inline void solve()
{
	if(l1!=l2)
	{
		write(1);
		putchar('\n');
		return;
	}
	int pos=0,ans1=1,ans2=1,ans3=1,ans4=1;
	for(int i=1;i<l1;i++)
	{
		if(a[i]!=a[i+1]) ans3++;
	}
	for(int i=1;i<l2;i++)
	{
		if(b[i]!=b[i+1]) ans4++;
	}
	for(int i=1;i<=l2;i++)
	{
		if(a[i]!=b[i])
		{
			pos=i;
			break; 
		}
	}
	if(!pos)
	{
		write(min(ans3,ans4));
		putchar('\n');
		return;
	}
	for(int i=pos+1;i<=l2;i++)
	{
		a[i]='1',b[i]='0';
	}
	for(int i=1;i<=pos;i++)
	{
		if(a[i]!=a[i+1]) ans1++;
	}
	for(int i=1;i<=pos;i++)
	{
		if(b[i]!=b[i+1]) ans2++;
	}
	int ans=min({ans1,ans2,ans3,ans4});
	write(ans);
	putchar('\n');
	return;
}
signed main()
{
	t=read();
	while(t--)
	{
		cin>>a>>b;
		l1=a.length(),l2=b.length();
		a=" "+a,b=" "+b;
		solve();
	}
	return 0;
}