閑暇時，福爾摩斯和華生玩一個游戲：

在N張卡片上寫有N個整數。兩人輪流拿走一張卡片。要求下一個人拿的數字一定是前一個人拿的數字的約數或倍數。例如，某次福爾摩斯拿走的卡片上寫著數字“6”，則接下來華生可以拿的數字包括：

1，2，3, 6，12，18，24 …

當輪到某一方拿卡片時，沒有滿足要求的卡片可選，則該方為輸方。

請你利用計算機的優勢計算一下，在已知所有卡片上的數字和可選哪些數字的條件下，怎樣選擇才能保證必勝！

當選多個數字都可以必勝時，輸出其中最小的數字。如果無論如何都會輸，則輸出-1。

輸入數據為2行。第一行是若干空格分開的整數（每個整數介于1~100間），表示當前剩余的所有卡片。
第二行也是若干空格分開的整數，表示可以選的數字。當然，第二行的數字必須完全包含在第一行的數字中。

程序則輸出必勝的招法！！

例如：
用戶輸入：
2 3 6
3 6
則程序應該輸出：
3

再如：
用戶輸入：
1 2 2 3 3 4 5
3 4 5
則程序應該輸出：
4

博弈論

先分析下必勝態和必敗態，如果我拿了一張牌，并且沒有其他的約數或倍數可拿，顯然這是我的必勝態。如果在這之前，對方也拿了一張牌，顯然對他來說他拿的那張牌就是必敗態，所以這種博弈里，必勝態和必敗態是交替出現的。

但要確定是必敗還是必勝，不抽到最后一張還是不能確定，所以要把所有可能的抽卡情況搜索出來，只有確定抽了這張牌，之后所有的情況都是必敗，我才能確定這張牌是必勝。

Code

def dfs(x):vis[x] = Truefor k in range(len(get[x]) - 1, -1, -1):if not vis[get[x][k]] and dfs(get[x][k]):vis[x] = Falsereturn Falsevis[x] = Falsereturn Trueif __name__ == '__main__':nums1 = list(map(int, input().split()))nums2 = list(map(int, input().split()))length1, length2, get, vis = len(nums1), len(nums2), [[] for _ in range(200)], [False] * 200for i in range(length1):for j in range(i):if nums1[i] % nums1[j] == 0 or nums1[j] % nums1[i] == 0:get[i].append(j)get[j].append(i)for i in range(length2):for j in range(length1):if nums2[i] == nums1[j] and dfs(j):print(nums1[j])breakelse:continuebreakelse:print(-1)

可惜只能拿到60分，暫時沒有什么更好的辦法。

總結

以上是生活随笔為你收集整理的2013\National _C_C++_A\4.约数倍数选卡片的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。