[LC周赛赛后发布会]WeeklyContest361

可悲！我还以为长周末大家都会出去玩，然后我能偷偷地打周赛，乘机偷排名，卷死他们，没想到又是平平无奇（3道）的一周。


第四题LZ真是没什么思路。


第三题有点波折，LZ一开始狂用数组，都是O(10^9) space，什么前缀数组，一大堆，然后space超了。一点点优化，再用数组做modulo的count，也就是int[modulo]，这个space是10^9一级，然后memory又超了。有什么关系嘛！人家速度还是很快啊！！！让人家多用点memory有什么关系嘛！！！搞的我一头雾水。然后跑去搞第四题了，第四题也是搞了一会儿没想法，再回过头来优化第三题，最后也算是搞成map，过了。可是提交了太多次了，中间还跑去搞了最后也没搞出来的第四题，浪费太多时间了。


最后搞下来也算2000-，大概7%，真是，长周末想偷排名都偷不了，一群人就知道刷题，也不出去玩。


不知道能不能再向2100（谷歌的门槛）进一步，也不知道什么时候再开人头，不过这样hard一直做不来也不是办法。


我去看看答案。

🐶一多半人到不了2100……

人生的意义在于能不能把hard做出来，做不出来人生是毫无意义的。

amocaki 发表于 2023-9-2 21:41
accepted了。先吧数组转化成01数组表达是否满足%modulo==k. 然后用一个map来储存符合条件的cumsum的个数。 ...

我才发现原来是modoluo的空间超了，555555，我一开始也是把数组转换成01数组，我还以为是这步超了，改了半天。

第三题比较容易想到是prefix sum+map。属于比较套路化。第二题搞了半天Backtracking/dfs 一直memory exceed才发现双循环就可以

EthanLee 发表于 2023-9-2 21:25
🐶一多半人到不了2100……

很多不打比赛的和看不上lc周赛的，但是人人都能2100+是肯定的，因为他们会做hard。

amocaki 发表于 2023-9-2 21:21
第三题比较容易想到是prefix sum+map。属于比较套路化。第二题搞了半天Backtracking/dfs 一直memory exceed ...

你第三题超空间了吗？要优化到O(10^5)才行。一半题目不计较空间。

怪怪，第四题要跳表lca，失敬失敬，确实没想到还能这样，我考虑过lca不过只能想到线性的，还有跳表lca真是有点tricky

amocaki 发表于 2023-9-2 21:21
第三题比较容易想到是prefix sum+map。属于比较套路化。第二题搞了半天Backtracking/dfs 一直memory exceed ...

我第二题没用dfs，就是搜尾部两个字符

irgebtdd 发表于 2023-09-02 21:33:51
你第三题超空间了吗？要优化到O(10^5)才行。一半题目不计较空间。

accepted了。先吧数组转化成01数组表达是否满足%modulo==k. 然后用一个map来储存符合条件的cumsum的个数。key=cumsum%modulo. 这样应该不会有memory问题。总之和其他prefixsum题目一个做法

modulo 是10^9 是个大坑，一般都是数组比较长。

倒回去看看如果第一时间解决（不要去看第四题）说不定能进1000.