【2017 Multi-University Training Contest - Team 2】Is Derek lying?

【Link】:

【Description】



两个人都做了完全一样的n道选择题,每道题都只有’A’,’B’,’C’

三个选项,,每道题答对的话得1分,答错不得分也不扣分,告诉你两个人全部n道题各自选的是什么,问你第一个人得X分,第二个人得Y分可不可能?

【Solution】



我们可以倒着想这个问题;

第一个人答对一题,就让X减去1

第二个人答对一题,就让Y减去1

只要能让X和Y都变成0,那就可以了,因为剩余的题目,不管两个人答案

是什么,都可以让他们俩都错.

设xt,bxt是两人所有的题答案相同和不相同的题目个数;

则想让X和Y快速都变成0,最快的方法就是,答案相同的地方都对.

但不能变成负数;

则设temp = min(x,y);

x-=min(temp,xt) y-= min(temp,xt);

如果x和y还是不都为0;

(这个时候答案相同的题目已经不能用了,因为对只能同时对)

(或者,干脆就是答案相同的题目不够用了)

则需要用答案不相同的题目来填了;

这个时候,就只能一个一个的减了,不可能x和y同时减;

(因为一个人对了,另外一个人就错了)

则这个时候,需要看看bxt是否大于等于剩余的x+y;

这样才够x和y都变成0;

如果不够的话,就Impossible

够的话,就Possible(其他题目,就直接算他们俩都错)



【NumberOf WA】



0



【Reviw】



不难



【Code】

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T,n,x,y;

char s1[(int)8e4+10],s2[(int) 8e4+10];

main(){

    scanf("%lld",&T);

    while (T--){

        scanf("%lld%lld%lld",&n,&x,&y);

        scanf("%s",s1+1);

        scanf("%s",s2+1);

        int xt = 0,bxt = 0;

        for (int i = 1;i <= n;i++)

            if (s1[i]!=s2[i])

                bxt++;

            else

                xt++;

        int temp = min(x,y);

        x-=min(temp,xt),y-=min(temp,xt);

        bxt-=x,bxt-=y;

        if (bxt<0){

            puts("Lying");

        }

        else

            puts("Not lying");

    }

    return 0;

}