首页 > 其他分享 >国庆题目

国庆题目

时间:2024-10-04 19:22:03浏览次数:7  
标签:题目 该组 单元格 矩阵 国庆 答案 到达 我们

Maximize the Largest Component (Hard Version)

  • 题意:

给定一个 \(n\times m\) 的网格,由“.”和“#”字符组成。

如果从该组中的任何单元格开始,通过仅移动到该组中共享一个共同边的另一个单元格,就可以到达该组中的任何其他单元格,则一组“#”单元格形成一个连通分量。其大小为该组中的单元格数量。

在一次操作中,选择任意行 \(r\) 和任意列 \(c\),然后将行 \(r\)和列 \(c\) 中的每个单元格设置为 "#"。

问在最多执行一次操作后,可以实现的“#”个单元格的最大连通分量的最大可能大小。

ps:保证所有测试用例中的 $ n \cdot m $ 的总和不超过 $ 10^6 $。

  • 思路:

我们考虑到执行操作不会使答案更劣,所以我们一定会执行这次操作。

考虑到 \(n\times m\leq 10^6\),那么我们可以暴力枚举选择哪行哪列。

考虑到如果在枚举内部统计答案不好做,哥们考虑预处理答案,那么可以单点算贡献。

我们看下一个点会在选哪行哪列时产生贡献。

显然如果该点在原本的图上最左边可到达 \(l1\),最右可到达 \(r1\),最上可到达 \(l2\),最下 \(r2\) 的话,那么哥们会发现,只要我们选的行在 \([l2-1,r2+1]\) 的区间内或所选的列在 \([l1-1,r1+1]\) 的区间内,都可以产生贡献。

那么我们将我们的选择也抽象成一个矩阵,第 \(i\) 行 \(j\) 列记录的就是我们选第 \(i\) 行第 \(j\) 列的答案。

然后就变成一个套路的矩阵中一块的加减法,直接弄一个矩阵差分即可转为 \(O(1)\) 处理,最后再转回来即可,记得特殊处理你选的那行和那列的答案。

时间复杂度 \(O(nm)\)。

标签:题目,该组,单元格,矩阵,国庆,答案,到达,我们
From: https://www.cnblogs.com/Nefertariqwq/p/18447149

相关文章

  • 【训练记录】2024年莆田市高中信息学奥赛国庆集训CSP-S提高组(第四天场外)
    训练情况rk#1\(100+100+100+100=400\)赛后反思因为满分AK了,就不需要反思了A题显然我们想要选的最多,我们优先选\(a_i\)小的,所以我们对\(a_i\)从小到大排序,再求一个前缀和,再使用二分即可#include<bits/stdc++.h>#defineintlonglongusingnamespaces......
  • 【牛客训练记录】2024牛客国庆集训派对day3
    赛后反思还是只开出来一题TATH题构造一个01矩阵,想要横竖斜三个数都不同,好像方法有很多,我们考虑交错着放010101011010101001010101上面这种长度为\(1\)的01显然不行,因为斜着也算,所以我们考虑构造长度为\(2\)的01,例如00111100这样001100111100110000110011110......
  • 国庆 CF 做题记录
    CF2002F2考虑F1,当\(n=m\)时,我们默认\(l\gef\)。此时我们可以发现一个比较正确的策略:先从\((0,0)\)跳到满足\(p\)是质数的\((p,0)\)处,然后再跳到满足\(q\)是小于\(p\)的质数的\((p,q)\)处,然后再暴力BFS。不会证明,可以达标找出这样的结论。当\(n>m\)时,注......
  • 国庆快乐!附ssh实战
     小伙伴们,有一段时间没更新了,目前在中科院软件所实习,在这里我祝大家国庆快乐! 今天这一期带来ssh命令的实战教程,ssh在工作当中遇到的非常多,因为总是需要登服务器,而且玩法也有不少,这是我常用的几个玩法。1、Windows直接连接虚拟机启动的Linux。sshuser@IPV42、从Linux反向......
  • VUE前后端分离毕业设计题目项目有哪些,VUE程序开发常见毕业论文设计推荐
               目录0为什么选择Vue.js1Vue.js的主要特点2前后端分离毕业设计项目推荐3后端推荐4总结0为什么选择Vue.js        使用Vue.js开发计算机毕业设计是一个很好的选择,因为它不仅具有现代前端框架的所有优点,还能让你专注于构建高性......
  • 【牛客训练记录】2024牛客国庆集训派对day2
    赛后反思只开出来两题,好像水平就这样了TATI题给定一个排列,对于每项可以选择+1或者不加,求逆序对对数最小我们可以思考一下什么情况下可以减少最后答案的逆序对,对于\([4,3]\)或者\([2,1]\)这种情况,将第二个元素+1才能对答案的减少做出贡献,所以只要判断某一位的后面是否有那......
  • 欢乐国庆:SciChart 8.5 for WPF Crack
    WPFChartPerformanceSciChart’slegendaryWPFChartperformanceisenabledbyourproprietary,in-house,C++crossplatform3Dgraphicsengine,VisualXccelerator.TheengineisentirelyhardwareacceleratedtargettingDirectXonWindowsplatform.Youw......
  • 【训练记录】2024年莆田市高中信息学奥赛国庆集训CSP-S提高组(第二天场外)
    训练情况rk#4\(100+100+100+70=370\)赛后反思没什么很严重的失误,只是国庆早八起不来,打到后面时间不够做第四题了QAQ,下次一定早起TATA题开场怎么是CFDiv4原题,显然因为\(a,b,c,d\)互不相同,最后切出来的结果只有三块或四块,三块的情况是两线没有交叉,四块的情况......
  • 【牛客训练记录】2024牛客国庆集训派对day1
    https://ac.nowcoder.com/acm/contest/90188#question赛后反思好像没有,全场只做出来一题QAQJ题想在图上找到同色三角形,我们枚举至少是\(O(n^3)\)的,所以我们考虑容斥定理(?),去找异色三角形,因为只要保证一条边上两点颜色不一样,另找一点随便都可以,所以我们只要统计白色的点数,......
  • 豆包MarsCode国庆献礼,轻松开发开发一款电子贺卡制作工具
    大家好,我是晓凡。作为一名搬了很多年砖的码农,深知求职和编程路上的各种辛酸与艰辛。你是否也曾在面试前夜,疯狂刷题却完全记不住,收效甚微?是否也曾在深夜凌晨一个人对着电脑屏幕,苦苦思索一个bug的解决方案?是否看着前人留下的屎山代码而无从下手,最后也只能留下只要屎山不倒,就继续......