分类 OI 下的文章

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

在SSL-OI夏日合宿中,参与者们面对了三道题目。T1是关于分火腿的问题,要求将火腿切成大小相等的份数,求最小切几刀,解法是输出$m-(n,m)$,其中$(n,m)$表示$n$和$m$的最大公约数。T2是关于工资分配的问题,要求将数组分成最多$m$块,求各块和的最大值最小,解法是二分答案并贪心遍历数组。T3是关于选择$k$个数使其$gcd$最大的问题,解法是记录每个值出现的次数,然后从大到小枚举答案,统计倍数出现次数的和,若大于等于$k$则为答案。整体而言,题目难度适中,参与者们在中午前就完成了所有题目的修改。下午计划修改昨天的题目,并关注NOI网络同步赛的情况。

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

这篇文章主要记录了作者在 SSL-OI 夏日合宿中的经历,包括购买键盘和键帽、打部分分的情况以及对一些题目的题解和总结。

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