NOIP2024T1

cengzh · 2024-12-01 13:38:54 · 题解

纪念第一道场切蓝题

第一眼读这题一直在想，这个限制的意义在哪？

想通这一点就好写了：因为无限次交换两个相邻字符就等于可以任意组合字符的排列顺序，所以为了给你提高难度加上了限制。这是可以手推的。

那么这样的话，我们发现每个 t 中的 0 相当于将 s 分了若干个部分,这几个部分中的字符可以随意排列。

有了这个结论，我们考虑如何让匹配字符更多。

现在不考虑限制的情况，即假设两段字符串可以任意排列。

容易想到贪心法，我们尽可能将相同的字符排在一起，那么答案就是两段字符 0 个数的最小值和 1 个数的最小值之和。

有了限制怎么办捏？

根据结论，我们就会发现只是在上面那种情况的基础上多加了几段字符串！于是一个很自然的思路就出来了：我们尽可能让两段区间能够匹配相同字符，不能匹配了就换下一个区间继续匹配，文字解释或许不直观，看代码吧，注释很详细：

# include <stdio.h>

int main (void)
{
    int T;
    scanf ("%d",&T);    

    while(T)
    {
        char s1[100005];
        char s2[100005];
        char t1[100005];
        char t2[100005];
        int mch1[2];//第一个串的0/1的个数
        int mch2[2];//第二个串的0/1的个数
        mch1[0] = mch1[1] = mch2[0] = mch2[1] = 0;//初始化！考场因为这个调了1h
        int n;
        int ans=0;
        scanf ("%d",&n);

        scanf ("%s",s1);
        scanf ("%s",s2);
        scanf ("%s",t1);
        scanf ("%s",t2);

        int i=0,j=0;//限制（t中的0）的位置
        int k=0;//已经确定的位置，即现在关注到第几个字符

        while (k < n)
        {
            while (i < n && t1[i] == '1')//i是第一个串的
            {
                mch1[s1[i]-'0']++;//计数
                i++;
            }
            while (j < n && t2[j] == '1')//j是第二个串的
            {
                mch2[s2[j]-'0']++;//计数
                j++;
            }

            while (k < i && k < j) // 在限制之前字符可以任意排列，考虑这个情况
            {
                if (mch2[1] > 0 && mch1[1] > 0)//都有1，匹配1
                {
                    mch1[1]--;
                    mch2[1]--;
                    ans++;          
                }
                else if (mch2[0] > 0 && mch1[0] > 0)//都有0，匹配0
                {
                    mch1[0]--;
                    mch2[0]--;
                    ans++;
                }
                k++;// 已经确定的位置过掉
            }

            if (k == n)//这里也是一个坑，不过看样例很容易调,s1[n]和s2[n]是相同的，在下面会多计一个数
            {
                break;
            }
            //这里要匹配一下不能交换的位置
            if (i == j) //如果两个都不能交换
            {
                if (s1[i] == s2[j])//那么仅在它们相同时产生贡献
                {
                    ans++;
                }
                mch1[0] = mch1[1] = mch2[0] = mch2[1] = 0;//换下一个区间了，之前一个区间的字符不能交换到这里来，清零重置
                i++;
                j++;
            }
            else if (i > j)//i!=j相当于某个区间还可以匹配下一个区间的字符,这里是j被限制
            {
                if (mch1[s2[j]-'0'] > 0)//如果这个不能交换的位置上的字符在第一个串上还有，就匹配它
                {
                    mch1[s2[j]-'0']--;
                    ans++;
                }
                mch2[0] = mch2[1] = 0;//清零重置
                j++;
            }
            else if (i < j)
            {
                if (mch2[s1[i]-'0'] > 0)//同理
                {
                    mch2[s1[i]-'0']--;
                    ans++;
                }
                mch1[0] = mch1[1] = 0;
                i++;
            }
            k++; // 又确认了一个位置
        }

        printf ("%d\n",ans);
        T--;
    }

}