天天看點

hdu 6324. Grab The Tree

題意:

一棵樹,n個點,n-1條邊。每個點的點權為a[i]。Q先拿任意數量個頂點,前提是拿的頂點中任意兩個不相鄰。T拿Q剩下的頂點。

再最優政策下他們把拿到的點的異或和誰大?如果Q大輸出Q  T大輸出T 平局輸出D

思路:

類似博弈吧。答案隻有Q和D。

随便拿總有一大一小或兩個相等,每次Q拿兩個選擇中最大的 或者相等的就行,

那麼就是先找相等的情況了。當時想的是所有點異或和為0那必定是平局,剩下就是Q赢

賽後又想 異或和為0就必定平局嘛?啊啊啊我不知道怎麼解釋了

ACM