OI

题解 LGP8918 『MdOI R5』Jump

0 条评论 OI 题解 无标签 hycqwq
终于有大月赛了哈哈哈思路一上来，看着有点像倍增，于是我们就思考：如果要使用倍增，那么我们应该可以在某些时刻不跳。但是题目要求每秒钟都必须跳，于是我们就来寻找有没有办法可以让我们想不跳的操作无效。在多次尝试之后我们发现：$$2^{n - x} = 2^n - \sum\limits_{i = 1}^{x} 2^{n - i}$$其中 $x$ 为正整数且 $0 \le x \le n$。所以这意...

auto 类型与 Lambda 表达式使用笔记

0 条评论 笔记 无标签 hycqwq
本文所有内容均仅能在 C++11 及以上标准中使用。一、前置知识1.1 auto 类型auto 的本义是“自己”。auto 类型可以根据赋值，自己推断应该使用什么类型。这其实是为了方便程序猿不用打一些很长的类型。举个栗子，遍历一个 map，如果不用 auto，代码如下。map<class1, class2> m; for (map<class1, class2>::i...

题解 LGP8584 探索未知

0 条评论 OI 题解 无标签 hycqwq
简化题面问 $n$ 个分数之和，其中有正有负。思路利用“减一个数等于减它的相反数”把减法转换为加法。然后就是通分，相加再约分。具体实现方法通分：两个分数都上下同乘另一个分数的分母，注意要把先乘的分数的分母存起来。相加：分子相加，没得说。约分：分数上下同除分子与分母的最大公因数（即 gcd），注意也要把 gcd 存起来，因为原分数会改变。代码易错点：这个数据范围要开 long long，血与泪...

题解 LGP8537 「Wdoi-2」花如幻想一般

0 条评论 OI 题解 无标签 hycqwq
赛时竟然想了好久，后来开窍了，$O(n)$ 的做法，dalao 勿喷。思路分 $2$ 种情况：翻转 $1$ 次的和没翻转的（如果翻 $2$ 次就没意义了）① 没翻转的每次操作可以给任意一朵花加上或减去任意的美丽程度，所以一朵花只调整一次即可，否则就浪费次数了。也就是说，遍历两个序列时，如果对应值不同，操作总数 $+ 1$。② 翻转 $1$ 次的即翻转后当做没翻转的情况来计算次数，最后再 $+...

题解 LGP8507 毕业后

0 条评论 OI 题解 无标签 hycqwq
简化题面简单来说，就是有 $a$ 门科目和 $b$ 个考生，每科最后 $w$（$w$ 是比例）的考生不及格，如果一个考生有 $2$ 科或更多科目不及格则无法毕业。思路一个很简单的容斥原理，每科 E 等人数之和不能超过 $b$，即每科 E 等人数最多为 $\lfloor b \div a \rfloor$。最后再把每科最多 E 等人数除以 $b$ 得到它在全部考生中的占比，$w_{\max} ...