CF455B A Lot of Games

題意：

Andrew,Fedor和Alex是三個(gè)善于創(chuàng)造的人。現(xiàn)在，他們發(fā)明了一種字符串雙人游戲。

給出n個(gè)非空字符串。在游戲中，兩位玩家一起建造一個(gè)單詞。開(kāi)始時(shí)，單詞是一個(gè)空字符串。兩位玩家輪流操作。一位玩家在他的回合中，必須在單詞的后面添加一個(gè)字母，使得添加后的單詞是n個(gè)字符串中至少一個(gè)的前綴。當(dāng)一位玩家不能操作時(shí)，他就輸?shù)袅擞螒颉?/p>

Andrew和Alex決定玩k次。上一局的負(fù)者是下一局的先手。他們決定，在最后一局中獲勝的人獲得整場(chǎng)游戲的勝利。Andrew和Alex已經(jīng)開(kāi)始玩了，Fedor想知道，如果他們兩個(gè)足夠聰明，誰(shuí)會(huì)勝利。

題解：

本題獨(dú)特在玩k輪，而只有最后一輪的勝利才算勝利，且前輪輸者會(huì)成為本輪先手。也就是說(shuō)，對(duì)于兩個(gè)玩家，前面贏不一定是好事，也就是他們?yōu)榱俗詈髣倮锌赡茉谇懊孑?#xff0c;這需要我們分類(lèi)討論。
如果先手只有必勝策略，沒(méi)有必?cái)〔呗?#xff0c;那說(shuō)明兩個(gè)選手都會(huì)輪流贏，最后一局誰(shuí)獲勝取決于輪次的奇偶性
如果先手有必勝策略，也有必?cái)〔呗?#xff0c;那么先手可以一直輸，這樣一直是先手，然后在最后一輪贏
如果先手沒(méi)有必勝策略，只有必?cái)〔呗?#xff0c;那么一定是后手贏，因?yàn)楹笫衷诿恳痪种卸际莿僬?br /> 現(xiàn)在我們就是找先手是否有必勝和必?cái)〔呗?#xff0c;因?yàn)轭}目規(guī)則是每次加的單詞為字符串中一個(gè)前綴，我們把所有字符串都放在trie樹(shù)上，如果到葉子節(jié)點(diǎn)，就無(wú)法再加單詞，此時(shí)就結(jié)束比賽了。現(xiàn)在我們就要看根節(jié)點(diǎn)有什么策略
我們?cè)俳Y(jié)合DAG上的博弈論性質(zhì)：若后面的點(diǎn)存在必?cái)〔呗?#xff0c;則當(dāng)前點(diǎn)為必勝策略。
而對(duì)于必?cái)〉那闆r，我們要知道先手是可以故意選擇必?cái)〉?#xff0c;因此求先手能否必?cái)r(shí)，只要后面的點(diǎn)存在必勝策略，當(dāng)前點(diǎn)就可以為必?cái)↑c(diǎn)，否則為必勝點(diǎn)。這一點(diǎn)與DAG圖上博弈論稍有不同

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); #define Memory() printf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0); using namespace std; bool Handsome; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=6e5+9; struct node{int ch[30];int num;bool haveson; }tr[maxn]; int win[maxn]; int lose[maxn]; int now=0; void insert(){string s;cin>>s;int u=0;for(int i=0;i<s.length();i++){tr[u].haveson=1;if(tr[u].ch[s[i]-'a']==0){tr[u].ch[s[i]-'a']=++now;u=now;}else{u=tr[u].ch[s[i]-'a'];}} } bool dfs1(int u){//只要后面存在必?cái)?#xff0c;當(dāng)前就是必勝 if(tr[u].haveson==0){return win[u]=0;}for(int i=0;i<26;i++){if(tr[u].ch[i]&&dfs1(tr[u].ch[i])==0)//后面出現(xiàn)一個(gè)必?cái)?return win[u]=1;} // 后面全是必勝 return win[u]=0; } bool dfs2(int u){//后面全是必勝，當(dāng)前就是必?cái)?if(tr[u].haveson==0){return lose[u]=1;}for(int i=0;i<26;i++){if(tr[u].ch[i]&&dfs2(tr[u].ch[i])==0)//后面有必勝 return lose[u]=1;//當(dāng)前就是必?cái)?} //后面全是必?cái)?#xff0c;當(dāng)前就是必勝 return lose[u]=0; } bool Most; int main() { // rd_test();int n,k;cin>>n>>k;for(int i=1;i<=n;i++){insert();}dfs1(0);dfs2(0);if(win[0]){if(lose[0]){puts("First");}else {if(k&1)puts("First");else puts("Second");}}else {puts("Second");}//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF455B A Lot of Games的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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