当前位置: 首页 > news >正文

part 10

  • T1
  • 读题十分恶心,大概是有一个 \(n \cdot m\) 的网格图,统计最多的从 \((1,1)\)\((n,n)\) 的路径数每一步往右或往下走,还有若干个障碍,路径要满足,按包含障碍的集合大小升序排序之后,使得各个路径拥有的障碍数不同,且第 \(i\) 条路径有的障碍,第 \(i+1\) 条路径必须有
  • 如果 \((x+1,y)\)\((x,y+1)\) 都是障碍则 \((x,y)\)\((x+1,y+1)\) 都不能走了干脆将它设成障碍
  • 我们则是要求障碍相邻的连通块数即可
  • T2
    • 首先考虑 \(m=1\) 那很简单了,我们直接建立 \(trie\) 树然后求 lca 即可
    • 然后考虑 minmax 容斥
    • $ \max(a, b, c) = a + b + c - \min(a,b) - \min(b, c) - \min(a, c) + \min(a, b, c)$
    • 问题转换为求 \(\min\)
    • 令现在仍有 \(t\) 个字符串
    • 则我们可以考虑把 \(t\) 个字符串最短的长度设为 \(len\) ,每个字符串都取前 \(len\) 个字符,从第一个字符开始一个一个字符加入。
      • 即加入序列为 \(s_{i,1,1},s_{i,2,1}, …… s_{i,t,1},s_{i,1,2},s_{i,2,2}, …… s_{i,t,2} …… s_{i,1,len},s_{i,2,len}, …… s_{i,t,len}\)
      • 按照这个序列构建 trie 树
    • 所以我们此时可以发现 \(i\)\(j\)\(\min_lcp\) 即为它们的 \(\frac{dep_lca}{m}\)
http://www.hskmm.com/?act=detail&tid=20920

相关文章:

  • Nordic发布用于nRF54L系列的nRF Connect SDK裸机选项
  • 微软SSO集成中的顺序用户ID身份验证绕过漏洞剖析
  • content和text方法的区别
  • shell脚本动态域名解析阿里云
  • 聪明的wyk
  • Windows下进程和账户权限
  • Spring Gateway动态路由实现方案 - 详解
  • Nordic 高性能无线SoC nRF54LM20A,专为低功耗蓝牙与Matter设计
  • 调用setState 之后发生了什么?
  • element plus 配置主题色
  • Python教程:解决pip安装包时报错:error: externally-managed-environment This environment is externally managed
  • 哲学家进餐问题
  • 16.1 总体主成分分析
  • 黄金分割比
  • 借助Aspose.Email,使用 Python 读取 Outlook MSG 文件
  • 痞子衡嵌入式:恩智浦i.MX RT1xxx系列MCU启动那些事(11.B)- FlexSPI NOR连接方式大全(RT1180)
  • 文件同步工具深度测评(2025版):同步盘夺冠
  • Oracle故障处理:数据库启动时遇到ORA-01578错误
  • 【ACM出版|连续三届EI检索】第四届人工智能与智能信息处理国际学术会议(AIIIP 2025)
  • 【2025-09-28】平凡家庭
  • 实用指南:梦回童年,将JSNES 游戏模拟器移植到 HarmonyOS 移植指南
  • 单键触控感应芯片 电容是触控IC VKD233HS -永嘉微VINKA 原厂
  • 微算法科技(NASDAQ: MLGO)研发基于 DPoS 框架的 DL-DPoS(深度链接委托权益证明)机制,增强区块链的共识算法
  • JMM内存模型
  • 读者-写者问题
  • 实现邮件发送
  • AGC073C 赛后补题记录
  • LuatOS赋能Air780EPM:FTP通信开发教程正式上线!
  • DM40万用表为何全网爆火?!它有哪些与众不同?DM40万用表比肩千元级表,让您轻松实现专业级测量自由!
  • 树形dp [POI 2013] LUK-Triumphal arch