OI

OI

AcWing 160 匹配统计 – 题解与思路重现

160. 匹配统计 – AcWing题库 又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了 解一 字符串Hash结合二分 $\mathrm{O}(n+m)$预处理出两个...

More
  • 2021年12月13日
OI

模板 – 支持单点修改与删除操作的二叉堆

昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。 具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$...

More
  • 2021年12月12日
OI

模板 – 基数排序

基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数，可以在$\mathrm{O}(kn + \sum\limits_{i=1}^{k}w_i)$的线性时间内完成...

More
  • 2021年12月8日
OI

三道排列组合好题

或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。 AtCoder ABC226 F – Score of Permutations 题意参见原题面。 很自然地想到，对...

More
  • 2021年11月14日
OI

牛客网 货物分组 – 题解

是的，又是一道考试时想出正解没有打出来的题目 货物分组 – 牛客网 根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为...

More
  • 2021年10月22日
OI

CF201D Brand New Problem 简略题解

Problem D – Codeforces Round #127 (Div. 1) 多模式串匹配，是不是又是AC自动机啊？ 显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模...

More
  • 2021年10月12日

分类