【火题合集】3.22考试

1.盾盾的打字机

差点以为是阿狸的打字机

然后这就是个弱dp

好像我的做法和一般人不太一样。。好像也麻烦些(然后就打萎了

dp[i][j]表示A中第i个字符匹配到了B的第j个的最小值(此时a[i]==b[j])

mm[i][j]表示使dp[k][j]+i-k(k<=i)最小的k

那么dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+(a[i])!=b[j]),dp[mm[i-1][j-1]][j-1]+i-mm[i-1][j-1]-1+(a[i]!=b[j]))

依次为插入、直接走/修改、往回退了再走/修改

2.社交网络

打表可知,答案为

$$连通块大小之积\times n^{连通块个数-2}$$

特判一下只有一个联通块

证明的话好像要什么树的prufer编码。。不会

3.中位数

骗分都没写

说点什么

您将是第一位评论人!

提醒
wpDiscuz