分类 OI 下的文章

摘要: 文章讨论了LOJ #6089小Y的背包计数问题,该问题要求计算将大小为$n$的背包装满的方案数,其中物品数量也为$n$,每个物品的重量和数量均为其编号。解法采用了根号分治策略:对于重量大于$\sqrt{N}$的物品,视为无数量限制,使用数的划分(可重方式)求解;对于重量小于$\sqrt{N}$的物品,使用多重背包求解,复杂度为$O(N\sqrt{N})$。前置知识包括多重背包的单调队列优化和数的划分DP。

摘要: 本文是 SSL-OI 夏日合宿 2020.08.22 A 组的题解,包括一道思维题的题解和故事。思维题可以用暴力求解,也可以通过桶和后缀和优化。

摘要: 作者参加了 SSL-OI 夏日合宿,做了一套原题并口胡了题解,包括 T1 KC 看星、T2 KC 的瓷器和 T3 开心小屋。其中 T1 是搜索或枚举四个点判断两条直线的关系,T2 是分组背包,T3 是搜索和剪枝。

摘要: 文章讨论了SSL-OI夏日合宿2020.08.17 A组的三道题目。T1题要求根据边权求点权,解法涉及基环树和环上的k元一次方程组求解。T2题要求将数组分为两个上升子序列,使差值最小,解法涉及二分图染色和DP。T3题涉及序列操作,支持修改和查询,解法提出了树剖和树套树两种方法。文章还提到了出题人胡睿和博客更新情况。

摘要: 文章讨论了POI2018中的水箱问题(luoguP5952),该问题要求计算一个$n*m$方格水箱中,水位高度不超过$H$的情况下,有多少种不同的水位分布。文章提出了一种基于最小生成树的解决方案,通过从小到大枚举墙的高度,合并水域并计算答案。算法使用并查集来维护水域的合并,并通过优先队列来处理墙的合并顺序。最终,程序输出水位分布的总数,该数对$10^9+7$取模。文章还提到了一些实现细节,如数组大小和优化技巧。