Codeforces 755B:PolandBall and Game(map+思维)

时间:2022-09-26 20:24:11

http://codeforces.com/problemset/problem/755/B

题意:A可以喊出n个字符串,B可以喊出m个字符串,如果一个字符串之前被喊过,那么它再也不能喊了,A先喊,最后没得喊的输。问谁赢。

思路:用map判断A、B中字符串一样的个数,因为A可以先喊,然后B再喊,每个人可以喊的数量要减去cnt / 2(如果是奇数,A可以喊多一个),表示被对方喊了。如果最后n<=m则A输,否则A赢,等于的情况是因为A先喊,B再喊,到最后A会输。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <string>
 7 #include <iostream>
 8 #include <stack>
 9 #include <map>
10 #include <queue>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 #define N 100010
15 #define INF 0x3f3f3f3f
16 string s1[1010];
17 string s2[1010];
18 map<string, int> mp;
19 
20 int main()
21 {
22     int n,m;
23     cin >> n >> m;
24     for(int i = 1; i <= n; i++) cin >> s1[i];
25     for(int i = 1; i <= m; i++) cin >> s2[i];
26     int f = 0;
27     for(int i = 1; i <= n; i++) mp[s1[i]] = 1;
28     for(int i = 1; i <= m; i++) if(mp[s2[i]]) f++;
29     n -= (f / 2); m -= (f - f / 2);
30     if(n > m) puts("YES");
31     else puts("NO");
32     return 0;
33 }