题解【Lucky Conversion】

【题意翻译】

定义幸运数字为只含有“幸运字符”（(4) 和 (7)）的正整数。如 (4)，(7)，(744) 是，而 (5)，(17)，(467) 不是。

现有两个等长的字符串 (a)，(b)，只含“幸运字符”，对 (a) 进行下面两个操作中的任意一种：

1）将任意一个 (a) 中的字符从 (4) 变 (7)，或者从 (7) 变 (4)；

2）将 (a) 中任意两个字符位置互换。

求能使 (a) 变成 (b) 的最小操作次数。

【样例输入输出】

【输入 #1】

47
74

【输出 #1】

【输入 #2】

774
744

【输出 #2】

【输入 #3】

777
444

【输出 #3】

【数据规模与约定】

(a.size,b.size leq 10^5)

这题的结论还是比较好推的。

读入两个串 (a,b)。

设 (num4) 表示 (a) 串和 (b) 串不同，且 (a) 串为 (4) 的数量；
设 (num7) 表示 (a) 串和 (b) 串不同，且 (a) 串为 (7) 的数量。

提出一个结论：最小的转换次数是 (max(num4,num7))。

证明如下：

当 (a) 串和 (b) 串第 (i) 位相同时，这个位上字符不需要更改或交换，所以这个位对答案是没有影响的。

如果不考虑交换操作的话，操作次数应该就是 (num4+num7)。

又因为交换是没有限制的，所以 (a) 串中，一个不对应的 (4) 必定可以和一个不对应的 (7) 交换，使得这两个相互对应。

也就是说，现在一个不对应的 (4) 和一个不对应的 (7) 可以配对，只相当于一次操作次数，所以操作次数也就是
(num4+num7-min(num4,num7)=max(num4,num7))

经过一波伪证证明后，我们就可以愉快地使用结论了，代码也就呼之欲出了，如下：

#include<bits/stdc++.h>
#define rint register int
using namespace std;
char a[100010],b[100010];
int num7,num4;
int main(){
    scanf("%s%s",a+1,b+1);
    int len=strlen(a+1);
    for(rint i=1;i<=len;++i){
        if(a[i]!=b[i]&&a[i]=='4') num4++;
        if(a[i]!=b[i]&&a[i]=='7') num7++;
    }
    printf("%d",max(num4,num7));
    return 0;
}

完了awa

题解 【Lucky Conversion】