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

Swordmaker · 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;
}