6.2万

21小时前


'''

'''

def get_prime(N):
prime_vals = []
flag = [True] * (N+1)
for val in range(2, N+1):
if flag[val]:
prime_vals.append(val)

for p_val in prime_vals:
if val * p_val > N:
break

flag[val * p_val] = False

if val % p_val == 0:
break

return prime_vals

primes = get_prime(100000)

# 分解质因数函数，返回元组数组[ (质因子1, 次幂1)， (质因子2, 次幂2)， (质因子3, 次幂3) ...... ]
# 质因子的数值升序排列
def devide_prime(val):
ans = []

for i in primes:
if i*i > val:
break

if val % i == 0:
cnt = 0
while val % i == 0:
val //= i
cnt += 1

ans.append((i, cnt))

if val == 1:
break

# 特判最后可能剩下的大于sqrt(val)的最大的质因子
if val != 1:
ans.append((val, 1))

return ans

# 获取所有约数的函数
def get_approximate_numbers(val):
ans = []
primes = devide_prime(val)

def dfs(idx, prev_val):
if prev_val*prev_val > val:
return

if idx >= len(primes):
ans.append(prev_val)
if val // prev_val != prev_val:
ans.append(val // prev_val)

return

base = None
for pow_val in range(primes[idx][1]+1):
if pow_val == 0:
base = 1
else:
base *= primes[idx][0]

dfs(idx+1, prev_val * base)
dfs(0, 1)

return ans

def gcd(a, b):
if a > b:
a, b, = b, a

while a:
a, b = b % a, a
return b

n = int(input())
for _ in range(n):
a0, a1, b0, b1 = map(int, input().split())
app_vals = get_approximate_numbers(b1)

cnt = 0
for app_val in app_vals:
if b0 * app_val == b1 * gcd(app_val, b0):
if gcd(app_val, a0) == a1:
cnt += 1

print(cnt)





# import sys
# sys.stdin = open("data.txt", "r")

'''

'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
def __init__(self, fa):
self.s = ''             # end节点自己本身的单词
self.fail_s = []        # fail指针指向的节点序列的单词列表(如果fail指针指向的节点是一个end节点，此字段保存所有这些单词的列表)
self.next = {}          # 边和子节点映射
self.is_end = False     # 是否是end节点
self.fail = None        # ac自动机的fail指针
self.fa = fa            # 父节点指针
self.id = 0             # 节点的id号

class AcTrie:
def __init__(self):
self.root = AcTrieNode(None)
self.__idx = 1

def append(self, s: str):
cur = self.root
for ch in s:
if ch not in cur.next:
new_node = AcTrieNode(cur)
new_node.id = self.__idx
self.__idx += 1

new_node.s = cur.s + ch
cur.next[ch] = new_node

cur = cur.next[ch]
cur.is_end = True

# 构建ac自动机接口
def build(self, s_list = []):
# 第一步是构建普通的Trie
for s in s_list:
self.append(s)

# 层次遍历构建Fail指针
que = deque()
que.append(self.root)

depth = 0
while len(que) > 0:
node_num = len(que)

for _ in range(node_num):
cur = que.popleft()
if depth == 1:
# 根节点下面的第一层word长度是1，是没有后缀的，fail指针全部指向root
cur.fail = self.root
elif depth != 0:
cur.fail = self.root

# 循环找最长后缀的候选
p = cur.fa.fail
last_ch = cur.s[-1]
while True:
if not p:
break

if last_ch in p.next:
cur.fail = p.next[last_ch]

f = cur.fail
if f.is_end:
# 如果fail指针指向的节点是一个end节点，或者这个节点的fail_s列表不为空，需要添加这些单词到cur节点的fail_s列表中
cur.fail_s.append(f.s)

# fail指针指向的节点中fail_s里面的单词必须全部继承下来，因为这些单词也是后缀的备选
for s in f.fail_s:
cur.fail_s.append(s)

break
else:
p = p.fail

for new_node in cur.next.values():
que.append(new_node)

depth += 1

# 获取节点状态转移的表 [0号点转移表，1号点转移表, ......]
def get_stat_map(self):
ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

def dfs(node: AcTrieNode):
for ch in 'AGCT':
if ch in node.next:
if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = node.next[ch].id

else:
cur = node
while True:
if ch in cur.next:
if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = cur.next[ch].id

break

else:
if cur.fail is not None:
cur = cur.fail
else:
ans[node.id][ch] = cur.id
break

for child in node.next.values():
dfs(child)

dfs(self.root)
return ans

case_id = 1
while True:
n = int(input())
if n == 0:
break

ac_trie = AcTrie()

for _ in range(n):
ac_trie.append(input())

ac_trie.build()
stat_map = ac_trie.get_stat_map()

s = input().strip()
cache = [[None]*(len(s)+1) for _ in range(20*n)]
n = len(s)

# dp(stat, ii)表示Ac自动机状态为stat情况下，继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
def dp(stat, ii):
if ii == n:
return 0

if cache[stat][ii] is not None:
return cache[stat][ii]

ans = 0x7fffffff
for ch in 'AGCT':
if stat_map[stat][ch] is None:
continue

t = 0
if s[ii] != ch:
t += 1

t += dp(stat_map[stat][ch], ii+1)
ans = min(ans, t)

# print(stat, ii, ans, n)
cache[stat][ii] = ans
return ans

ans = dp(ac_trie.root.id, 0)
print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
case_id += 1





# import sys
# sys.stdin = open("data.txt", "r")

'''

'''

from collections import deque
from functools import lru_cache

class AcTrieNode:
def __init__(self, fa):
self.s = ''
self.fail_s = []
self.next = {}
self.is_end = False
self.fail = None
self.fa = fa
self.id = 0

class AcTrie:
def __init__(self):
self.root = AcTrieNode(None)
self.__idx = 1

def append(self, s: str):
cur = self.root
for ch in s:
if ch not in cur.next:
new_node = AcTrieNode(cur)
new_node.id = self.__idx
self.__idx += 1

new_node.s = cur.s + ch
cur.next[ch] = new_node

cur = cur.next[ch]
cur.is_end = True

def build(self, s_list = []):
for s in s_list:
self.append(s)

que = deque()
que.append(self.root)

depth = 0
while len(que) > 0:
node_num = len(que)

for _ in range(node_num):
cur = que.popleft()
if depth == 1:
cur.fail = self.root
elif depth != 0:
cur.fail = self.root

p = cur.fa.fail
last_ch = cur.s[-1]
while True:
if not p:
break

if last_ch in p.next:
cur.fail = p.next[last_ch]

f = cur.fail
if f.is_end:
cur.fail_s.append(f.s)

for s in f.fail_s:
cur.fail_s.append(s)

break
else:
p = p.fail

for new_node in cur.next.values():
que.append(new_node)

depth += 1

# 获取节点状态转移的表 [0号点转移表，1号点转移表, ......]
def get_stat_map(self):
ans = [{'A':None, 'G':None, 'C':None, 'T':None} for _ in range(self.__idx)]

def dfs(node: AcTrieNode):
for ch in 'AGCT':
if ch in node.next:
if node.next[ch].is_end or len(node.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = node.next[ch].id

else:
cur = node
while True:
if ch in cur.next:
if cur.next[ch].is_end or len(cur.next[ch].fail_s) != 0:
# 发生了匹配，下一个字符不可能是ch
ans[node.id][ch] = None
else:
ans[node.id][ch] = cur.next[ch].id

break

else:
if cur.fail is not None:
cur = cur.fail
else:
ans[node.id][ch] = cur.id
break

for child in node.next.values():
dfs(child)

dfs(self.root)
return ans

case_id = 1
while True:
n = int(input())
if n == 0:
break

ac_trie = AcTrie()

for _ in range(n):
ac_trie.append(input())

ac_trie.build()
stat_map = ac_trie.get_stat_map()

s = input().strip()
cache = [[None]*(len(s)+1) for _ in range(20*n)]
n = len(s)

# dp(stat, ii)表示Ac自动机状态为stat情况下，继续构造出一个合法的字符串[ii:n]这一段的最少需要修改的次数
def dp(stat, ii):
if ii == n:
return 0

if cache[stat][ii] is not None:
return cache[stat][ii]

ans = 0x7fffffff
for ch in 'AGCT':
if stat_map[stat][ch] is None:
continue

t = 0
if s[ii] != ch:
t += 1

t += dp(stat_map[stat][ch], ii+1)
ans = min(ans, t)

# print(stat, ii, ans, n)
cache[stat][ii] = ans
return ans

ans = dp(ac_trie.root.id, 0)
print(f'Case {case_id}: {ans if ans != 0x7fffffff else -1}')
case_id += 1





import sys

'''
S(i) 表示开始工作时间小于等于i的雇佣员工的总数

1. S(i) >= S(i-1) (i=1,2,3,4,....23)
2. S(0) >= 0

3. S(i) + S(23) - S(i+16) >= arr[i]

3. S(i) - S(i-8) >= arr[i]

4. S(i) - S(i-1) <= cnt[i], cnt[i]是从i时间开始工作的人的数量

'''

from collections import Counter
from collections import deque

class SPFA:

# start_node 为起始点，edges是边的三元组(节点1， 节点2， 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num

# 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)

# 获取最长路径长度列表[(节点1，长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)

# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0

for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None

else:

updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1

# 进行V次迭代，第V次检查是否是无解情况
iter_times = 0
while iter_times < self.max_node_num:
update_flag = False

# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
continue

if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff

elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w

if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
update_flag = True

if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)

iter_times += 1

if iter_times == self.max_node_num:
if update_flag:
return None

if not update_flag:
break

return [[node, dis[node]] for node in range(1, self.max_node_num+1)]

t = int(input())
for _ in range(t):
arr = list( map(int, input().split()) )
n = int(input())
possible = [0] * 24
for i in range(n):
possible[int(input())] += 1

if sum(possible) == 0:
print(0)
else:
find_ans = False
min_cost = 0x7fffffff
for S23 in range(0, n+1):
# 为了方便计算，所有数值下标都往后移动了一个位置, 超级源点已定义为23, 实际存储时候用24的位置
edges = []

# S(i) >= S(i-1) (i=1,2,3,4,....22)
for i in range(1, 23):
edges.append((i-1+1, i+1, 0))

# S(22) <= S(23)
edges.append((24, 22+1, 0))

# S(i) >= S(i+16) - S23 + arr[i]
for i in range(8):
edges.append((i+16+1, i+1, arr[i]-S23))

# S(i) >= S(i-8) + arr[i]
for i in range(8, 23):
edges.append((i-8+1, i+1, arr[i]))

# S(23) - S(15) >= arr[23], S(15) <= S(23) - arr[23]
edges.append((15+1, 24, -(S23 - arr[23])))

# S(0) <= possible[0]
edges.append((0+1, 24, -possible[0]))

# S(i) - S(i-1) <= possible[i] i = 1, 2, 3..... 22
for i in range(1, 23):
edges.append((i+1, i-1+1, -possible[i]))

# S(23) - S(22) <= possible[23] => S(22) >= S(23) - possible[23]
edges.append((24, 22+1, S23 - possible[23]))

# 虚拟源点向所有点添加边 S(i) >= 0, i = 0, 1, 2, ..... 22
for i in range(23):
edges.append((24, i+1, 0))

algo = SPFA(24, edges, is_directed=True, max_node_num=24)
ans = algo.getMaxPathLen()
if ans is None:
continue

find_ans = True
min_cost = min(min_cost, S23)

if find_ans:
print(min_cost)
else:
print('No Solution')




import sys

'''

'''

from collections import deque

class SPFA:

# start_node 为起始点，edges是边的三元组(节点1， 节点2， 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num

# 获取最短路径长度的列表[(节点1，长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)

# 获取最长路径长度列表[(节点1，长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)

# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0

for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None

else:

updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1

# 进行V次迭代，第V次检查是否是无解情况
iter_times = 0
cnt = [0] * (self.max_node_num + 1)
while iter_times < self.max_node_num:
update_flag = False

# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
continue

if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff

elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w

if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
cnt[b] = cnt[a] + 1
update_flag = True

if cnt[b] >= self.max_node_num:
return None

if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)

iter_times += 1

if iter_times == self.max_node_num:
if update_flag:
return None

if not update_flag:
break

return dis

edges = []
n, m1, m2 = map(int, input().split())
for i in range(m1):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a

# val(b) - val(a) <= w
edges.append((a, b, w))

for i in range(m2):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a

# val(b) - val(a) >= w
edges.append((b, a, -w))

for i in range(2, n+1):
# 后一个要大于等于前一个
# val(i) >= val(i-1)
edges.append((i, i-1, 0))

# 从2开始的每一个点都小于等于一个极大值，这样才能让超级源点对每一个点都是可达的，注意这里不能取0x7fffffff, 这个数值表示的是不可达
edges.append((n+1, i, 0x7ffffffe))

# 超级源点是n+1, 要求1号点固定在0位置
edges.append((1, n+1, 0))
edges.append((n+1, 1, 0))

# print(edges)
algo = SPFA(n+1, edges, is_directed=True, max_node_num=n+1)
ans = algo.getMinPathLen()
if ans is None:
print(-1)
else:
if ans[n] == 0x7ffffffe:
print(-2)
else:
print(ans[n])



cache = [[None]* 1005 for _ in range(1005)]

# dp(i, j)表示用小于等于j的数凑i的所有方案的数量
def dp(i, j):
if i == 0:
return 1

if j == 1:
return 1

if cache[i][j] is not None:
return cache[i][j]

if j > i:
ans = dp(i, i)
else:
ans = dp(i-j, j) + dp(i, j-1)

cache[i][j] = ans % 1000000007
return ans % 1000000007

n = int(input())
print(dp(n, n))





#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int cache[11][11];

char ss[1005][12];
char s[12];

char *s1 = nullptr, *s2 = nullptr;

// dp(i, j)表示将A前i个字符变为B前j个字符的最少变换次数
int dp(int i, int j) {
if (i == -1) {
return j + 1;
}

if (j == -1) {
return i + 1;
}

if (cache[i][j] != -1) {
return cache[i][j];
}

int ans = 0x7fffffff;
ans = min(ans, dp(i, j-1) + 1);     // 最后一次是加字符
ans = min(ans, dp(i-1, j) + 1);     // 最后一次是删字符

// 最后一次是修改字符
if (s1[i] == s2[j]) {
ans = min(ans, dp(i-1, j-1));
} else {
ans = min(ans, dp(i-1, j-1) + 1);
}

cache[i][j] = ans;
return ans;
}

int get_dis(char* ss1, char* ss2) {
memset(cache, -1, sizeof(cache));
s1 = ss1, s2 = ss2;
int ans = dp(strlen(s1)-1, strlen(s2)-1);

return ans;
}

int main(void) {
//freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);
int n, m, limit;

scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", ss[i]);
}

for (int k = 0; k < m; k++) {
scanf("%s %d", s, &limit);

int tot = 0;
for (int i = 0; i < n; i++) {
if (get_dis(ss[i], s) <= limit) {
tot++;
}
}
printf("%d\n", tot);
}

return 0;

}


import sys

# sys.stdin = open("input.txt", "r")

sys.setrecursionlimit(5000000)

n1 = int(input())
s1 = input()
n2 = int(input())
s2 = input()

cache = [[-1] * 1005 for _ in range(1005)]

# 将A前i个字符转换为B前j个字符的最小变换次数
def dp(i, j):
if cache[i][j] != -1:
return cache[i][j]

if i == -1:
# A添加j+1个字符
return j + 1

if j == -1:
# A删掉i+1个字符
return i + 1

ans = 0x7fffffff
ans = min(ans, dp(i, j - 1) + 1)  # 最后一次是添加字符
ans = min(ans, dp(i - 1, j) + 1)  # 最后一次是删除字符

# 最后一次是修改字符
if s1[i] == s2[j]:
ans = min(ans, dp(i - 1, j - 1))
else:
ans = min(ans, 1 + dp(i - 1, j - 1))

cache[i][j] = ans
return ans

print(dp(len(s1) - 1, len(s2) - 1))





# import sys
# sys.stdin = open("input.txt", "r")

N = 100005

# x[len]表示当前已经找到的长度是len的严格上升子序列的最小结尾数值
x = [0x7fffffff] * N

# dp[i]表示以i位置结尾的最长严格上升子序列的长度
dp = [1] * N

n = int(input())
arr = list(map(int, input().split()))

cur_len = 1     # 当前已经找到的最长上升子序列最长长度
ans = 1
x[1] = arr[0]

for i in range(1, n):
l, r = 1, cur_len
while l <= r:
mid = (l + r) // 2
if x[mid] < arr[i]:
dp[i] = mid + 1
l = mid + 1
else:
r = mid - 1

x[dp[i]] = min(x[dp[i]], arr[i])
if dp[i] == cur_len+1:
cur_len += 1

ans = max(ans, dp[i])

print(ans)




import sys
# sys.stdin = open("input.txt", "r")

m, n = map(int, input().split())
g = []

for i in range(m):
g.append(list(map(int, input().split())))

cache = [[-1] * 305 for _ in range(305)]

# dp(i, j) 表示从(i, j)位置触发的所有合法方案中，最多的区域的个数
def dp(i, j):
if cache[i][j] != -1:
return cache[i][j]

ans = 1
for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
if ii >= 0 and ii < m and jj >= 0 and jj < n and g[ii][jj] < g[i][j]:
ans = max(ans, 1 + dp(ii, jj))

cache[i][j] = ans
return ans

ans = 1
for i in range(m):
for j in range(n):
ans = max(ans, dp(i, j))

print(ans)