讨论/题目交流/🏆 第 157 场力扣周赛/
🏆 第 157 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

玩筹码
最长定差子序列
黄金矿工
统计元音字母序列的数目

展开讨论

先占坑,详细题解稍晚来:

  • 玩筹码
    题目意思转化一下就是奇数位可以无代价到奇数位,偶数位可以无代价到偶数位,但是奇数位和偶数位到达代价是 1 ,于是统计奇数位和偶数位的筹码数,将少的挪到多的位置就可以了。

  • 最长定差子序列
    遍历数组,每访问到一个数看看前面有没有可以和他构成等差数列的数,同时维护前面的等差数列最长长度。可以用 dict 来保持以每个数结尾的最长等差数列长度,总体时间复杂度为 O(n)O(n)

  • 黄金矿工
    有两种做法,第一种是无脑搜索,注意维护棋盘状态就可以了,这题时限较宽松可过。第二种做法是用状态压缩DP,dp[x,y,s]dp[x,y,s],表示当前在 (x,y)(x,y) 点,状态为 ss 是否可达,状态 ss 是一个 2525 位的二进制数,每一位表示当前格子的黄金是否已经被拿走。这样时间复杂度为 O(n2n)O(n*2^n) ,其中 nn 为黄金点数量。

  • 统计元音字母序列的数目
    其实是一道很简单的题目,不要被hard吓到了。dp[i,0 4]dp[i,0~4] 表示当前在第i位,最后一个字母是 aua-u (对应 040-4 )的可行序列总数,然后按照题目给的限制进行 dp[i+1]dp[i+1] 的转移就可以了。时间复杂度 O(n5)=O(n)O(n*5)=O(n)
    PS: 这道题 nn 可以给到 101810^{18},还存在更好的解法。

5
展开全部 14 讨论