笨蛋少女剑士

分类

题解(4)

/ 注册

全部文章（共14篇）

题解 | #拼接木棍#

题解：BISHI91 拼接木棍题目链接拼接木棍题目描述给定段小木棍长度，原始有若干根同长大木棍，将其切割后得到这些小木棍。求原始大木棍的最小可能长度。解题思路设所有小木棍长度总和为，最长小木棍为。原始大木棍长度必须满足且。按从小到大（即从到）枚举所有能整除 ...

2025-08-08

0 18

题解 | #【模板】记忆化搜索#

题解：BISHI90 【模板】记忆化搜索题目链接递归函数记忆化题目描述定义函数：若或或，则；若且，则；否则，。给定若干组（均不超过），输出对取模的结果。解题思路该递归具有大量重叠子问题，且输入上界为，可用动态规划自底向上求解。两种安全实...

2025-08-08

0 19

题解 | #余数求和#

题解：BISHI42 余数求和题目链接余数求和题目描述给定正整数，计算。解题思路将求和拆成两部分：当时，有，贡献为；其余用整除分块：。令，在区间上不变，且，于是区间贡献为。整体复杂度。代码 c++ java python #incl...

2025-08-08

0 40

题解 | #【模板】整除分块#

题解：BISHI41 【模板】整除分块题目链接【模板】整除分块题目描述给定正整数，求表达式的值。解题思路直接求和是，不可行。利用“整除分块”，当处于一个区间内时，取值相同。设，则该维持不变的最大右端点为。于是把区间一次性贡献：，再令继续。该做法步数为不同...

2025-08-08

0 17

题解 | #数组取精#

题解：BISHI40 数组取精题目链接数组取精题目描述给定两个长度为的正整数序列与。定义子集（，元素互异）为“精华子集”，当且仅当同时满足：请构造任意一个满足条件的精华子集并输出其大小及下标。解题思路分块配对 + 贪心：将下标按降序排序为，并将其两两配成...

2025-08-08

0 16

题解 | #【模板】Pollard-Pho算法#

题解：BISHI39 【模板】Pollard-Pho算法题目链接【模板】Pollard-Pho算法（素数判定）题目描述给定组询问，每次给出一个正整数，判断是否为质数。可能较大。解题思路本题仅需素性测试，用 Miller–Rabin（米勒拉宾）随机化判定的确定化基即可在位范...

2025-08-08

0 15

题解 | #有向二分图构造#

题解：BISHI38 有向二分图构造题目链接有向二分图构造题目描述给定一张有向图，含个点与条有向边。需要给每个点染成黑或白两色。若一条边的起点为黑色、终点为白色，则称其为“核心边”。请构造一种染色方案，使得核心边的条数不少于，并输出你构造方案下所有核心边的编号（按输入顺序从到 ...

2025-08-08

0 16

题解 | #数位差与数值和的构造#

题解：BISHI37 数位差与数值和的构造题目链接数位差与数值和的构造题目描述给定整数，请构造非负整数，满足，且，其中表示的十进制各位数字之和。保证解一定存在。解题思路目标是让与的数位和尽量均衡，同时保证逐位相加无进位，从而自然满足。设的十进制从高到低的每一...

2025-08-08

0 15

题解 | #【模板】扩展巴什博弈#

题解：BISHI36 【模板】扩展巴什博弈题目链接【模板】扩展巴什博弈题目描述有一堆石子，双方轮流取走石子。设初始石子数为，每次必须取走到颗（含端点）。若某时刻剩余石子少于则无法行动，该玩家失败；拿到最后一颗者获胜。给出多组，判断先手是否必胜（YES/NO）。解题思路经典...

2025-08-08

1 18

题解 | #【模板】巴什博弈#

题解：BISHI35 【模板】巴什博弈题目链接【模板】巴什博弈题目描述有一堆石子，双方轮流取走石子。设初始石子数为，每次可以取走到颗（即至多颗），拿到最后一个石子者获胜。给出多组数据，判断先手是否必胜，输出 YES/NO。解题思路经典巴什博弈。关键在于把局面维持在的倍...

2025-08-08

0 18