tiktok卷王MLE OA, 直接气急败坏关掉窗口。

这个第三题if neither of these two sticks has enough available memory；不是两块内存都没有空间了，才会发生OOM吗？为啥Output还要求返回可用空间

Zbeeee 发表于 2020-12-28 19:31
这个第三题if neither of these two sticks has enough available memory；不是两块内存都没有空间了，才会 ...

我的理解是到最后还是有可用空间的，只是无法装下第i秒需要的i bytes

rsents 发表于 2020-11-23 17:17
第二题应该可以DP来做，我们用f(i, j)表示已经用了i次swing，打掉了怪物j点血的*概率* ...

太强了但是看不懂。。。

虽然但是。。真的觉得楼主的语气太好笑了😂对不起楼主我笑了

第二题能不能直接求出期望 E 然后就是  E*K/N ?   E = M/2

我的评价是：好睡！

第四题：

1. # Follow up of LC 1153. String transforms into another string
   
2. # return min number of transformation
   
3. def MinNumSteps(str1, str2):
   
4.     '''
   
5.     build the graph of transformation
   
6.    
   
7.     several facts of the graph:
   
8.     + three types of connected component
   
9.         1) a long chain
   
10.         2) a chain with with cycle at the end
    
11.         3) a cycle
    
12.     + only can enter a cycle, cannot go out
    
13.     + one connected componnet only one cycle
    
14.    
    
15.     to transform a cycle:
    
16.     + if type 3), then number of transformation
    
17.       = cycle length + 1 (additional one is to
    
18.       break the cycle)
    
19.     + if type 2), = cycle length
    
20.       example: abcd -> bcaa
    
21.       graph: d -> a -> b -> c -> a
    
22.       break cycle by change c to d first
    
23.     '''
    
24.    
    
25.     if str1 == str2: return 0
    
26.    
    
27.     # build graph and check feasibility
    
28.     mapping = {}
    
29.     indegree = {}
    
30.     unique_char_in_str2 = set()
    
31.     for char1, char2 in zip(str1, str2):
    
32.         unique_char_in_str2.add(str2)
    
33.         if char1 != char2:
    
34.             if char1 in mapping and mapping[char1] != char2:
    
35.                 return -1
    
36.             mapping[char1] = char2
    
37.             indegree[char2] = indegree.get(char2, 0) + 1
    
38.     if len(unique_char_in_str2) == 26:
    
39.         return -1
    
40.    
    
41.     def dfs(char):
    
42.         start = char
    
43.         total_length = 0
    
44.         while char in visited and visited[char] == 0:
    
45.             if char in mapping:
    
46.                 total_length += 1
    
47.             visited[char] = 1
    
48.             char = mapping.get(char, None)
    
49.             
    
50.         if char in visited and visited[char] == 1:
    
51.             # cycle found
    
52.             cycle_length = 0
    
53.             # if there is a char with indegree > 1
    
54.             # we can always change the char in the
    
55.             # cycle to one of the other char that
    
56.             # point to that char
    
57.             # example: abcd -> bcaa
    
58.             # graph: d -> a -> b -> c -> a
    
59.             # a has indegree=2, we can change
    
60.             # c to d first; by doing this, we can
    
61.             # break the cycle without any extra steps
    
62.             has_outside_nodes = False
    
63.             while visited[char] == 1:
    
64.                 if indegree[char] > 1:
    
65.                     has_outside_nodes = True
    
66.                 visited[char] = 2
    
67.                 cycle_length += 1
    
68.                 char = mapping[char]
    
69.             if has_outside_nodes:
    
70.                 total_length = cycle_length
    
71.             total_length = cycle_length + 1
    
72.         
    
73.         # go thru the chain again and mark all as visited
    
74.         char = start
    
75.         while char in visited and visited[char] == 1:
    
76.             visited[char] = 2
    
77.             char = mapping.get(char, None)
    
78.         return total_length
    
79.    
    
80.     # now graph is ready and we know we can transform
    
81.     num_steps = 0
    
82.     visited = {char: 0 for char in mapping}
    
83.    
    
84.     for char in mapping:
    
85.         if visited[char] == 0:
    
86.             num_steps += dfs(char)
    
87.    
    
88.     return num_steps

复制代码

beijianzhizun 发表于 2020-11-23 11:49
第二题不就是拿K次攻击的能赢的组合除以所有k次攻击的可能造成的看血量来算。
我写了个方程：

感觉会tle, 需要记录下遍历过的状态，以免duplicated child questions

感谢楼主分享！~！