2022-08-21 星环科技-C++开发笔试

 1、

 

 思路：拓扑排序，不解释了

---

2、

 

思路：

本来以为他是一个图论问题，找最大环。

但其实对于这种情况，他是要输出0的，而不是9，所以他不是一个图论问题，他带有顺序性，这种可以用dp来维护。

abc
efa
cde

dp[i][j]，代表i王朝并且以j字符结尾的最大长度。

对于每一个串假设是abc，那么要更新，并且遍历，伪代码如下：

# 先更新自身
dp[a][c]=max(dp[a][c], 3) 
 
# 再更新其他节点
for i in range:
    dp[i][c] = max(dp[i][c], dp[i][a] + len("abc"))

注意更新的时候必须第一维的所有节点都要更新，因为都算是有用状态！！！别只更新dp[c][c]了。

最后遍历：

for i in range("abcde...xyz"):
    ans = max(ans, dp[i][i])

ans就是答案

---

3、

 

思路：模拟题