邓老师数
时间限制：1 sec
空间限制：256 MB
问题描述
众所周知，大于 1 的自然数中，除了 1 与其本身外不再有其他因数的数称作质数（素数）。
对于大于 1 的不是质数的自然数，我们又称作合数。
参加了邓老师算法训练营的小 Z 突发奇想，定义了新的数：所有合数中，除了 1 与其本身外，其他因数均为质数的数，称作邓老师数。
现在，小 Z 给定两个数 n,k，其中 k 的取值为 0 或 1。如果 k=0，小 Z 希望你告诉他所有不超过 n 的质数；如果 k=1，小 Z 希望你告诉他所有不超过 n 的邓老师数。
输入格式
一行两个用空格隔开的整数 n,k，意义见题目描述。
输出格式
对于每个找到的质数或邓老师数，输出一行一个整数表示这个你找到的数。
请升序输出所有答案。
样例输入
9 1
样例输出
4
6
9
样例解释
4 除去 1 与其本身外的因子有 2，均为质数，因此 4 是邓老师数。
6 除去 1 与其本身外的因子有 2,3，均为质数，因此 6 是邓老师数。
9 除去 1 与其本身外的因子有 3，均为质数，因此 9 是邓老师数。
8 除去 1 与其本身外的因子有 2,4，由于 4 不是质数，因此 8 不是邓老师数。
数据范围
本题共设置 8 个测试点，测试点编号从 1 至 8。
对于前 4 个测试点，保证 n<=1,000。
对于编号为偶数的测试点，保证 k=0；对于编号为奇数的测试点，保证 k=1。
对于所有的 8 个测试点，保证 n<=2*10^5。
提示
[对于求质数的问题，可以直接用Eratosthenes筛法求解。]
[对于求邓老师数的问题，考虑Eratosthenes筛法中“筛去”合数的逻辑，是否可以对其略作修改，使之支持筛出“非邓老师数”呢？]
代码实现
from typing import List
def get_answer(n: int, k: int) -> List[int]:
is_prime = [True] * (n + 1)
is_deng = [True] * (n + 1)
ans = []
for i in range(2, n + 1):
if is_prime[i]:
is_deng[i] = False
if (k == 0 and is_prime[i]) or (k == 1 and is_deng[i]):
ans.append(i)
for j in range(i * 2, n + 1, i):
is_prime[j] = False
if not is_prime[j // i]:
is_deng[j] = False
return ans
def main():
n, k = map(int, input().split())
ans = get_answer(n, k)
for num in ans:
print(num)
if __name__ == "__main__":
main()子序列
描述
给定一个字符串，求出该字符串有多少不同的子序列。
子序列：字符串中按顺序抽出一些字符得到的串。比如字符串abcd里，ab、ac、ad、abc、acd都是子序列。
输入
输入一个字符串。
输出
输出不同的子序列的个数除以23333得到的余数。
样例1输入
ababc
样例1输出
23
样例1解释
有这些子序列：
a，b，c，aa，ab，ac，ba，bb，bc，aba，abb，abc，aab，aac，bab，bac，bbc，abab，abac，abbc，aabc，babc，ababc
样例2
请查看下发文件内的sample2_input.txt和sample2_output.txt。
限制
对于50%的数据，字符串长度不超过15；
对于100%的数据，字符串长度不超过500000。
字符串为26个小写字母组成。
时间：2 sec
空间：512 MB
代码实现
def get_answer(s: str) -> int:
n = len(s)
mo = 23333
f = [0] * (n + 1)
p = [0] * (n + 1)
last = [-1] * 26
for i in range(n):
a = ord(s[i]) - ord('a')
p[i + 1] = last[a]
last[a] = i + 1
for i in range(1, n + 1):
if p[i] == -1:
f[i] = (2 * f[i - 1] + 1) % mo
else:
f[i] = (2 * f[i - 1] - f[p[i] - 1] + mo) % mo
return f[n]
def main():
s = input().strip()
result = get_answer(s)
print(result)
if __name__ == "__main__":
main()前缀
描述
给定n个字符串，再询问m次，每个询问给出一个字符串，求出这个字符串是n个字符串里，多少个串的前缀。
前缀：从头开始的一段连续子串。比如字符串ab是字符串abcd的前缀，也是字符串ab（自身）的前缀，但不是bab的前缀。
输入
第一行包含两个正整数n,m。
接下来n行，每行表示一个字符串，表示给定的n个字符串中的一个。
再接下来m行，每行一个字符串，表示询问的字符串。
输出
输出m行，每行表示询问的答案。
样例1输入
5 4
ab
abc
ab
ba
bb
a
b
ab
abc
样例1输出
3
2
3
1
样例1解释
字符串a是ab、abc、ab的前缀；
字符串b是ba、bb的前缀；
字符串ab是ab、abc、ab的前缀；
字符串abc是abc的前缀。
样例2
请查看下发文件内的sample2_input.txt和sample2_output.txt。
限制
对于50%的数据，n,m ≤ 500；
对于100%的数据，n,m ≤ 5000。
字符串为26个小写字母组成，且单个长度不超过500，n个字符串的长度之和不超过1000000。
时间：10 sec
空间：512 MB
提示
[trie树基本题。]
代码实现
class TrieNode:
def __init__(self):
self.prefix_latter_words = 0
self.children = [None] * 26
class Trie:
def __init__(self):
self.root = TrieNode()
@staticmethod
def index(c: str) -> int:
return ord(c) % 26
def insert(self, word: str):
cur = self.root
for c in word:
idx = self.index(c)
if not cur.children[idx]:
cur.children[idx] = TrieNode()
cur = cur.children[idx]
cur.prefix_latter_words += 1
def count_prefix(self, prefix: str) -> int:
cur = self.root
for c in prefix:
idx = self.index(c)
if not cur.children[idx]:
return 0
cur = cur.children[idx]
return cur.prefix_latter_words
def main():
t = Trie()
n, m = map(int, input().split())
for _ in range(n):
word = input().strip()
t.insert(word)
for _ in range(m):
prefix = input().strip()
print(t.count_prefix(prefix))
if __name__ == "__main__":
main()