月度归档: 2020年4月

16 篇文章

[NOI Online]子序列问题
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/noiolsequence/前言由于 NOI Online 还未评测,民间数据尚未出炉,因此本题解可能有错误…… 待测评后若有误可能会撤下/修改。当然笔者是不想有误的Update:在修改了没开 long…
[Luogu]P5588 小猪佩奇爬树
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp5588/题意题目传送门题目给的描述足够清晰,照搬过来:解法由特殊到一般,逐步分析。对每个颜色进行讨论。颜色未出现颜色的值域为 $[1,n]$,一共 $n$ 个点,只要有点的颜色重复,就会有颜色未在…
[Luogu]P3174 [HAOI2009]毛毛虫
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp3174/题意题目传送门定义毛毛虫:在树上选一条链,链上每个点所连接的点都被包括在毛毛虫上。定义毛毛虫的大小:毛毛虫包含的节点数。求一棵树上最大的毛毛虫的大小。解法使用动态规划的方法。定义状态类比树…
[U53204]树上背包的优化
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/backpack-on-tree-optimize/加入本文为笔者年少无知时所作,大体内容应该问题不大,但可能夸大了运用指针带来的优化效果。请各位读者批判地阅读吧……正文例题链接本文旨在介绍树上背包的优…
[Luogu]P1991 无线通讯网
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp1991/题意题目传送门给出若干点,定义距离小于 $D$ 的点可以归于一个集合,可以强行将 $S$ 个点归于一个集合,求所有点在同一个集合时 $D$ 的最小值。解法主流的题解都是使用最小生成树的解法…
[数论笔记]1.整除
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/numbertheory1/前言笔者最近开始学习 OI 需要的数论…… 本系列为学习笔记。参考教材:《信息学奥赛之数学一本通》 (林厚雄)整除定义整除,设 $a$ 为非零整数, $b$ 为整数, $q$…
[Codeforces]Educational Codeforces Round 85 赛后总结
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/cfedu85/前言好久没有打比赛了,周五考完文化课之后看到有深夜场,想了想就打了。 最后只做出来4题,排名一千左右。在此写一个总结,如有必要也会发布单题题解。咕咕咕A. Level Statistic…
[Luogu]P3694 邦邦的大合唱战队
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp3694/题意题目传送门$N$ 个人,分别属于 $M$ 个组,要求同组的人站在一起。 每个人可以出队,出队后留出空位,出队后的人可以在任意空位归队。求最少出队人数。解法看到 $M$ 的数据范围极小,…
[Luogu]P5858 Golden Sword
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp5858/题意题目传送门有 $n$ 种原料,锅中可以同时存在 $w$ 种原料,每次放入前可以取出 $s$ 种原料。放入第 $i$ 种原料,贡献为 $a_i \times 当前锅中原料种数$,且种数包…
[Luogu]P4933 大师
Before the Beginning转载请将本段放在文章开头显眼处,如有二次创作请标明。原文链接:https://www.codein.icu/lp4933/题意题目传送门简单地说,题意就是:求选出的数列是等差数列的方案数。特别地,单个数和两个数也算作等差数列。解法求方案数常用方法,动态规划。 设计状态,很容易想到公差肯定是状态中的一值,而结尾…