okk，大伙，這一期我們就把C組的題目刷完。
本期題目：砍柴，回文字符串

砍柴

題目

題目鏈接：砍柴

本題所包含的算法：博弈論 + 質數篩法 + 動態規劃

思路分析

首先，我們先理解一下題意，每個人都能砍下長度為質數的距離，當長度只剩 1 或 0 的時候，這個人失敗。

這里就是一個經典的博弈論的問題，每個人都會去選擇最優解，那么對于每一個數都是有一個 必勝態 或者 必敗態。

那什么時候是必敗態呢？

（以題目中，小藍先手為例）
就是當 小藍砍下任意長度后，對方都處于必勝態，則這就是必敗態。

反之，當有一種情況能夠讓對方進入必敗態，那這就是必勝態。

舉個栗子

這個數是 1 或者 0，必敗態。
這個數是 2 ，砍下 2 對方處于必敗態，故為必勝態。
這個數是 3 ，砍下 2 或 3 對方處于必敗態，故為必勝態。
這個數是 4 ，砍下 3 對方處于必敗態，故為必勝態。
這個數是 5 ，砍下 5 對方處于必敗態，故為必勝態。
6，7，8 都是必勝態。
這個數是 9 ，能砍的數只有 2， 3， 5， 7 ，但無論選哪個數，對方都處于必勝態，故為必敗態。
……
以此類推

思路總結

首先，它要砍質數，所以我們可以先預處理出所有的質數。
然后，再預處理出 1e5 以內所有數的狀態。
最后，再讀取題目的所有數，一一對應即可。
OK，就是這樣，來看代碼吧。

代碼

def prime(n):z = []for i in range(2, n + 1):for j in range(2, int(pow(i, 0.5)) + 1):if i % j == 0:breakelse:z.append(i)# 所有數據范圍內的質數return zt = int(input())
x = [int(input()) for _ in range(t)]
n = max(x) + 1dp = [0] * n
prime_numbers = prime(n)for i in range(n):if dp[i] == 0:for p in prime_numbers:if i + p >= n:breakdp[i+p] = 1for xi in x:print(dp[xi])

回文字符串

題目

題目鏈接：回文字符串

思路分析

這題就比較簡單了，它就是一個判斷回文字符串的題目，就是增加了一個特殊情況的判斷。

我們來分析一下 ——
首先，按照題目所說，能在字符串開頭增加指定字符。
我們能夠將字符串分成 3 類 ：

1. 左邊的指定字符串比右邊多
2. 右邊比左邊多
3. 整個字符串都是指定字符

左邊多，那這個肯定就不是了。
右邊多，那它就有可能是。
整個都是指定字符串，那肯定是。

所以，我們主要需要判斷的就是右邊多的情況，我們的判斷是從去掉兩側
指定字符串之后開始計算，從中間往兩側去判斷。

分析到這里，我們來看看代碼吧。

代碼

n = int(input())
for _ in range(n):s = ' ' + input() # 讓下標從 1 開始for l in range(1, len(s)):if not (s[l] == 'l' or s[l] == 'q' or s[l] == 'b'):breakr = len(s)for i in range(1, len(s)):if not (s[r - i] == 'l' or s[r - i] == 'q' or s[r - i] == 'b'):r -= ibreakif r == len(s): # 整個字符串都是指定字符print('Yes')continueif (r - l + 1) % 2 != 0: # 找去掉兩側指定字符串后的中間位置l = r = (r + l) // 2else:l = (r + l) // 2r = l + 1while l > 0: # 判斷是否回文if s[l] != s[r]:print('No')breakl -= 1r += 1else:print('Yes')

感謝大伙觀看，別忘了三連支持一下

大家也可以關注一下我的其它專欄，同樣精彩喔~

下期見咯~