題目大意：

有兩個人輪流說單詞，已經(jīng)說過的單詞不能再說。給出兩人掌握的不同的單詞，兩人可能掌握相同的單詞，但是這個單詞也只能說一邊。問在兩人都是最優(yōu)策略下先手是否必勝.

題解:

我們發(fā)現(xiàn)最優(yōu)策略一定是先說兩人都掌握的單詞。
所以我們求出所有同時被掌握的單詞
然后根據(jù)這種單詞的奇偶性來判斷即可.

求的時候?qū)懥藗€Trie...
不過好像直接暴力也可以..

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; inline void read(int &x){x=0;char ch;bool flag = false;while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x; } inline int cat_max(const int &a,const int &b){return a>b ? a:b;} inline int cat_min(const int &a,const int &b){return a<b ? a:b;} const int maxn = 1024; char s[512]; int nodecnt = 0; int ch[maxn*256][28]; bool flag[maxn*256]; int root = 0; void insert(char *s){int n = strlen(s+1);int nw = root;for(int i=1;i<=n;++i){if(ch[nw][s[i] - 'a'] == 0) ch[nw][s[i] - 'a'] = ++nodecnt;nw = ch[nw][s[i] - 'a'];}flag[nw] = true; } bool find(char *s){int n = strlen(s+1);int nw = root;for(int i=1;i<=n;++i){if(ch[nw][s[i] - 'a'] == 0) return false;nw = ch[nw][s[i] - 'a'];}return flag[nw]; } int main(){int n,m;read(n);read(m);for(int i=1;i<=n;++i){scanf("%s",s+1);insert(s);}int com = 0;for(int i=1;i<=m;++i){scanf("%s",s+1);if(find(s)) ++com;}n -= com;m -= com;if(com&1){if(n >= m) puts("YES");else puts("NO");}else{if(n > m) puts("YES");else puts("NO");}getchar();getchar();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Skyminer/p/6358057.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 755B. PolandBall and Game 贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。