品牌型网站制作价格,网站建设与制作设计公司,黑色网站模版,定制柜需要多少钱okk#xff0c;大伙#xff0c;这一期我们就把C组的题目刷完。 本期题目#xff1a;砍柴#xff0c;回文字符串 文章目录 砍柴题目思路分析举个栗子思路总结 代码 回文字符串题目思路分析代码 感谢大伙观看#xff0c;别忘了三连支持一下大家也可以关注一下我的其它专栏大伙这一期我们就把C组的题目刷完。 本期题目砍柴回文字符串 文章目录 砍柴题目思路分析举个栗子思路总结 代码 回文字符串题目思路分析代码 感谢大伙观看别忘了三连支持一下大家也可以关注一下我的其它专栏同样精彩喔~下期见咯~ 砍柴
题目
题目链接砍柴 本题所包含的算法博弈论 质数筛法 动态规划
思路分析
首先我们先理解一下题意每个人都能砍下长度为质数的距离当长度只剩 1 或 0 的时候这个人失败。
这里就是一个经典的博弈论的问题每个人都会去选择最优解那么对于每一个数都是有一个 必胜态 或者 必败态。
那什么时候是必败态呢
以题目中小蓝先手为例 就是当 小蓝砍下任意长度后对方都处于必胜态则这就是必败态。
反之当有一种情况能够让对方进入必败态那这就是必胜态。
举个栗子 这个数是 1 或者 0必败态。 这个数是 2 砍下 2 对方处于必败态故为必胜态。 这个数是 3 砍下 2 或 3 对方处于必败态故为必胜态。 这个数是 4 砍下 3 对方处于必败态故为必胜态。 这个数是 5 砍下 5 对方处于必败态故为必胜态。 678 都是必胜态。 这个数是 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[ip] 1for xi in x:print(dp[xi])回文字符串
题目
题目链接回文字符串
思路分析
这题就比较简单了它就是一个判断回文字符串的题目就是增加了一个特殊情况的判断。
我们来分析一下 —— 首先按照题目所说能在字符串开头增加指定字符。 我们能够将字符串分成 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)感谢大伙观看别忘了三连支持一下
大家也可以关注一下我的其它专栏同样精彩喔~
下期见咯~
