一分钟拿下前缀和
来提每日一题
2024-11-28 17:34:27
2024我的兴趣支点 创作灵感 程序员 每天59秒拿下每日一题 北美求职 近期找工作现状 互联网大厂 宝宝辅食 大学生 期末考试
国区每日一题今日思路：
前缀和。记d[i]为从0到i位置所有瓷砖与其相邻颜色不同的个数，若k块瓷砖颜色交替，等价于使用一个k-2的滑动窗口，窗口中所有瓷砖符合要求，窗口区间和为k-2，使用前缀和数组在O(1)时间得到区间和。
国际站每日一题今日思路：
图论。初始时0到各个节点i距离dis等于i，每进行一个查询时，引入一条从u到v的路由，记route[v]为可以到达v点的路由，加入路由后将v之后所有节点的距离刷新；每个节点i路由由两部分组成，从i-1转移和从路由标route[i]转移，距离选择最小值；每次查询结果为dis[n-1]。看到这点个赞吧[喝奶茶R]
0
阅读：0
FAF点点点
真服了，题目是unidirectional road, 我看成了undirectional road，难怪看完editorial也觉得不太对呢
依呀依呀哟
今日国区：Python可以负数索引，将环变成普通列表，dp找到那几条最长的颜色相间切片，边dp边求和