[题解] 多国语言（2021牛客OI赛前集训营）

题目描述

不同的国家和地区，使用着不同的语言。
在不同的语言中，形容猫的叫声的拟声词也有所不同，比如中文中是“喵 (miao)”，
英文中是“meow”，日文中是“にゃー(nyaa)”。

牛牛想知道，不同国家和地区的猫，是不是真的存在不同的交流方式。
为了验证这个事情，他将m种语言编号为1,2, . . . , m。然后他随机的找来了一只猫，
并对着猫发出 n 次猫叫声，其中第i 次猫叫声是第 ai (1 ≤ ai ≤ m)种语言中猫叫
的拟声词。
每次发出猫叫声后，他会记录猫是否对其回应。如果猫在第i次回应了牛牛，牛牛
则记录bi = 1，否则记录bi = 0。

如果猫只对某种语言的叫声做出回应，并对该种语言的每次叫声都做出回应，那
么牛牛就判断，不同国家和地区的猫确实存在不同的交流方式，并且认为这只猫
来自该种语言的国家。此时输出该种语言的编号。
否则，如果猫对≥ 2种语言的叫声做出了回应，或者对1种语言做出过回应，但没
有对每次该语言的叫声做出回应，那么牛牛认为猫真可爱，并且给它一条小鱼干。
此时输出^v^。
当然也有可能，猫根本就不回应牛牛的任意一次叫声，这时牛牛将会很沮丧。此
时输出 >-<。

思路

记录叫的次数和分别回应的次数， cnt 统计几次叫满（都回应了），k 统计几次至少回应了一次，对比即可。

Code

讲解都在注释里：

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int n,m,T,cnt,a[N],b[N],v[N],num[N];
int main(){
    scanf("%d",&T);
    while(T--){
        memset(num,0,sizeof(num));
        memset(v,0,sizeof(v));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            ++num[a[i]];//num[a[i]]：该语言牛牛叫了多少次
        }
        for(int i=1;i<=n;++i){
            scanf("%d",&b[i]);
            if(b[i]==1) ++v[a[i]];//v[a[i]]：被回应的次数
        }
        int dire=0,k=0,cnt=0;
        for(int i=1;i<=m;++i)
            if(v[i]>0&&num[i]>0){
                ++k;//该种语言至少被回应了一次
                if(num[i]==v[i]) ++cnt,dire=i;//对该种语言每次都做出了回应
            }
        if(k>=2) printf("^v^\n");//猫对≥2种语言的叫声做出了回应
        else if(k==0) printf(">-<\n");//猫根本就不回应牛牛的任意一次叫声
        else {//对1种语言做出过回应
            if(cnt>0) printf("%d\n",dire);//对该种语言的每次叫声都做出回应
            else printf("^v^\n");//没有对每次该语言的叫声做出回应
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

再来一个没有注释的版本：

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+5;
int n,m,T,cnt,a[N],b[N],v[N],num[N];
int main(){
    scanf("%d",&T);
    while(T--){
        memset(num,0,sizeof(num));
        memset(v,0,sizeof(v));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            ++num[a[i]];
        }
        for(int i=1;i<=n;++i){
            scanf("%d",&b[i]);
            if(b[i]==1) ++v[a[i]];
        }
        int dire=0,k=0,cnt=0;
        for(int i=1;i<=m;++i)
            if(v[i]>0&&num[i]>0){
                ++k;
                if(num[i]==v[i]) ++cnt,dire=i;
            }
        if(k>=2) printf("^v^\n");
        else if(k==0) printf(">-<\n");
        else {
            if(cnt>0) printf("%d\n",dire);
            else printf("^v^\n");
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

AD

$$\text{Lvshu OJ }\text{，大量高质量题目等着你，点击这里马上注册。}$$

$$\text{Lvshu OS}\text{，崭新的系统，点击这里，马上查看详情}$$