P12887 题解

题目思路

我们知道，小蓝和朋友答案相同时肯定是正确的，所以剩下不相同的数值就是 N 减去相同的数值。而在正确的数量中，还有一部分未被判定正确与否，所以这里可以用到容斥原理的思想。未判定的量中，只有不同的字符数减去 M 的差才是小蓝还可以判对的数量。所以我们按照这个思路模拟即可。

代码实现

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
int maxn=-1e9,sum,a;
int main(){
    ll n,m;
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    string w,q;
    cin>>w>>q;
    for(int i=0;i<w.size();i++){
        if(q[i]==w[i]) a++;
    }
    int b=n-a,same=min(a*1ll,m),ans=2*same+b-m;
    cout<<ans;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        scanner.nextLine(); // consume the remaining newline

        String w = scanner.nextLine();
        String q = scanner.nextLine();

        int a = 0;
        for (int i = 0; i < w.length(); i++) {
            if (q.charAt(i) == w.charAt(i)) {
                a++;
            }
        }

        long b = n - a;
        long same = Math.min(a, m);
        long ans = 2 * same + b - m;

        System.out.println(ans);
    }
}

算法分析

本题的核心思路是利用容斥原理的思想解决问题。具体步骤如下：

1. 计算小蓝和朋友答案相同的数量 a
2. 计算答案不同的数量 b = n - a
3. 确定可以正确判定的相同答案数量 same = min(a, m)
4. 最终答案为 2*same + b - m

这个算法的时间复杂度为 O(n)，空间复杂度为 O(1)，非常高效。

总结

这道题考察了对问题的抽象能力和容斥原理的应用。通过分析题目中的条件，我们可以将问题转化为简单的数学计算，从而得到高效的解决方案。

祝各位通过本题！