分类 OI 下的文章

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

SSL-OI 夏日合宿 2020.08.20 A 组比赛中,选手们在 T1 题上遭遇滑铁卢,T2 题考查了线段树优化建边和传递闭包等知识点,T3 题则是一道字符串题。

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

本文主要介绍了数论中的一些基本概念和算法,包括素数判定、因数个数、线性筛、最小素因数、欧拉函数、欧拉函数线性筛等。同时,文章还给出了每个算法的复杂度分析和证明。