首页 > 其他分享 >ABC351D_MagicalCookies

ABC351D_MagicalCookies

时间:2023-08-20 11:12:26浏览次数:60  
标签:颜色 饼干 MagicalCookies 复杂度 sigma HW Theta ABC351D

Magical Cookies

根据问题的描述,如果在判断同一行或同一列的所有饼干是否具有相同颜色时,选择了时间复杂度为 \(\Theta(H)\) 或 \(\Theta(W)\) 的方法,那么在每次操作 1 或操作 2 中,时间复杂度将变为 \(\Theta(HW)\),因此在最坏情况下,整个计算的时间复杂度将为 \(\Theta(HW(H+W))\),可能会导致超时。

为了加快速度,我们可以利用颜色种类较少的特点。假设可能的颜色种类为 \(\sigma\) 种,对于本问题而言,\(\sigma = 26\)。我们可以在处理每一行时,同时记录颜色为 ab、...、z 的饼干的数量,以便在 \(O(\sigma)\) 的时间复杂度内判断同一行或同一列的饼干是否具有相同颜色。因此,我们可以在 \(O(\sigma (H+W)^2)\) 的时间复杂度内完成颜色判断部分。对于标记和移除饼干,由于每个饼干只需要进行一次操作,所以时间复杂度为 \(O(HW)\),因此总体的时间复杂度为 \(O(\sigma (H+W)^2)\)。

若直接暴力,会发现 TLE

正解可以在找到字母时 break,没有答案是终止程序,使得效率提升三倍。

TLE

AC

标签:颜色,饼干,MagicalCookies,复杂度,sigma,HW,Theta,ABC351D
From: https://www.cnblogs.com/wscqwq/p/17643733.html

相关文章