Zxt的博客

摘要： 前缀 题解 1. 题意 题目核心要求： 给定一个字符串集合，需要从中选取任意非空子集合，计算该子集合中所有字符串的最长公共前缀长度与子集合元素个数的乘积，最终输出所有可能子集合对应的乘积的最大值。 2. 思路 这是一道典型的字典树应用问题，核心思路与前缀统计类问题一致，字典树的每个节点存储以该节点对 阅读全文

摘要： 字典树学习笔记 1.前言 在处理一些前缀、匹配的问题时，普通的暴力是无法解决的 这个时候，除了hash，我们还有字典树 2.字典树框架 字典树，又称Trie树，一种树形结构 它的操作可以理解为将字符串加入一个集合 字典树需支持两个操作： 插入，将字符串T加入集合中 查询，查询一个字符串S与集合中的字 阅读全文

摘要： [CCC 2023 S4] 最低成本道路 题解 1.题目 有\(n\)个点，\(m\)条边，每条边有长度 \(l\) ，权值 \(c\) ，组成一个原图 你需要构造一个新图，满足以下条件： 仍然有\(n\)个点，且联通。 新图上的边都是原图中的边 对于任意一个点对 \((u,v)\)，满足新图上从 阅读全文

摘要： [POI 2012] HUR-Warehouse Store题解 1.题目 现在有 \(n\) 天。第 \(i\) 天上午会进货 \(a_i\) 件商品，中午的时候会有顾客需要购买\(b_i\)件商品，可以选择满足顾客的要求，或是无视掉他。 如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足 阅读全文

摘要： [CEOI2017] Building Bridges 什么？你不知道李超线段树 1.题目大意 有\(n\)根柱子，每根柱子有个高度\(h_i\)，有若干座桥，一座连接柱子\(i\)和\(j\)的桥建造它需要\((h_i-h_j)^2\)的代价。 要求连接\(1\)到\(n\)的所有柱子。但是用不到 阅读全文