P7668 [JOI 2018 Final] 团子制作 / Dango Maker
~竟然是青题，我想了两个小时...~ 我真的不知道这道题该怎么快速想到思路，因为按照中间的那个点来选还是太神了。如果有能更快想到的方法希望能指出。 我看到这道题，第一反应是感觉思路挺多的。 首先肯定是先手搓看一下有没有规律。 我找了 $20^+mi
阅读全文分类：题解
共 15 篇文章
P3705 [SDOI2017] 新生舞会
[P3705 [SDOI2017] 新生舞会](https://www.luogu.com.cn/problem/P3705)。 题目要求最大化： $$ \frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n} $$
阅读全文
题解：P6300 悔改
本文介绍了洛谷题目 P6300 的解法，通过生成函数将问题转化为卷积形式，利用离散化将枚举量优化至 $O(\sqrt n)$ 级别，最终使用 NTT 计算卷积，时间复杂度为 $O(m\sqrt n\log m)$。
阅读全文
题解：CF1685C Bring Balance
本文介绍了 CF1685C 题目的解法。通过将括号匹配转化为前缀和折线图，利用翻转区间后最低点变为原最高点的性质，得出最多只需两次翻转的结论。若只需一次翻转，则通过贪心在负数两侧寻找最大前缀和端点判断合法性。
阅读全文
题解：CF1667C Half Queen Cover
本文介绍了 CF1667C Half Queen Cover 问题的解法。首先通过分析行列与对角线的覆盖关系，推导出所需棋子数 k 的理论下界为 ceil((2n-1)/3)。随后给出了一种具体的构造方法，利用斜线覆盖剩余矩阵，并附带了 C++ 代码实现。
阅读全文
题解：AT_agc061_d [AGC061D] Almost Multiplication Table
本文介绍了洛谷专栏上一道关于近似乘法表的算法题，通过二分答案和构造可行解的方法，对题目中的两个变量进行分类讨论，并详细解释了代码实现过程，包括时间复杂度的证明和代码细节。
阅读全文
题解：P2479 [SDOI2010] 捉迷藏
本文介绍了一种考场上快速解题的人类智慧方法。作者通过比较斜率 x/y 进行排序并取中间值来解决问题。为保险起见可随机旋转坐标系，但不旋转也能快速通过。该方法仅需 20 分钟即可搞定，是目前最快的解法。
阅读全文
题解：CF1620F Bipartite Array
本文介绍了 CF1620F Bipartite Array 的解法。指出存在长度大于等于 3 的逆序对会产生奇环，不满足二分性质。因此需将数组排成两个上升子序列，并用动态规划求解，定义状态 a 和 b 分别记录前一位取正或负时另一段末尾的最小值。
阅读全文
题解：CF1684G Euclid Guess
本文讲解了 CF1684G Euclid Guess 的解法。根据元素 x 与 m 的比例关系，将数对分为大元素和小元素。大元素需匹配满足整除条件的小元素，小元素可自我消耗。最终将该构造问题转化为二分图匹配模型，利用 DFS 求解。
阅读全文
P3455 [POI 2007] ZAP-Queries
本文介绍了一道求最大公约数为特定值的数对数量的题目。通过莫比乌斯反演推导出计算公式后，利用整除分块技术将时间复杂度从 O(n) 优化至根号级别，并详细解释了整除分块的原理与代码实现。
阅读全文
题解：UVA10111 Find the Winning Move
本文讲解了 alpha-beta 剪枝算法的原理及应用。文章先介绍 Minimax 算法，说明博弈树中双方分别求最大和最小值的搜索过程，随后阐述通过记录 alpha 和 beta 值剪去多余分支的优化思路。最后结合题目给出将胜负设为 1 和 -1 并枚举空位搜索的代码。
阅读全文
题解：P5270 无论怎样神树大人都会删库跑路
本文介绍洛谷题目 P5270 的解法。核心是设计哈希判断数字出现次数是否相同，并用 unsigned long long 自然溢出避免精度误差。针对大量询问，通过计算操作循环节优化复杂度，统计时需处理长度不足及非完整循环节部分。作者提醒注意细节。
阅读全文P7668 [JOI 2018 Final] 团子制作 / Dango Maker
~竟然是青题，我想了两个小时...~ 我真的不知道这道题该怎么快速想到思路，因为按照中间的那个点来选还是太神了。如果有能更快想到的方法希望能指出。 我看到这道题，第一反应是感觉思路挺多的。 首先肯定是先手搓看一下有没有规律。 我找了 $20^+mi
临时
本文介绍了洛谷题目 P1674 [USACO05FEB] Secret Milking Machine G 的题面。题目要求在 N 个区域和 P 条道路的农场中，寻找 T 条从区域 1 到区域 N 且不重复经过同一条道路的路线，并求出这些路线中经过的最长道路的最小长度。
P3705 [SDOI2017] 新生舞会
[P3705 [SDOI2017] 新生舞会](https://www.luogu.com.cn/problem/P3705)。 题目要求最大化： $$ \frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n} $$
题解：P6300 悔改
本文介绍了洛谷题目 P6300 的解法，通过生成函数将问题转化为卷积形式，利用离散化将枚举量优化至 $O(\sqrt n)$ 级别，最终使用 NTT 计算卷积，时间复杂度为 $O(m\sqrt n\log m)$。
题解：CF1896G Pepe Racing
这道题要求对一组数进行排序，通过将数分成多个栈，并不断比较栈顶元素来找出最大值，最后通过优化查询次数和考虑特殊情况来提高效率。
题解：CF1685C Bring Balance
本文介绍了 CF1685C 题目的解法。通过将括号匹配转化为前缀和折线图，利用翻转区间后最低点变为原最高点的性质，得出最多只需两次翻转的结论。若只需一次翻转，则通过贪心在负数两侧寻找最大前缀和端点判断合法性。
题解：CF1667C Half Queen Cover
本文介绍了 CF1667C Half Queen Cover 问题的解法。首先通过分析行列与对角线的覆盖关系，推导出所需棋子数 k 的理论下界为 ceil((2n-1)/3)。随后给出了一种具体的构造方法，利用斜线覆盖剩余矩阵，并附带了 C++ 代码实现。
题解：AT_agc061_d [AGC061D] Almost Multiplication Table
本文介绍了洛谷专栏上一道关于近似乘法表的算法题，通过二分答案和构造可行解的方法，对题目中的两个变量进行分类讨论，并详细解释了代码实现过程，包括时间复杂度的证明和代码细节。
题解：P2479 [SDOI2010] 捉迷藏
本文介绍了一种考场上快速解题的人类智慧方法。作者通过比较斜率 x/y 进行排序并取中间值来解决问题。为保险起见可随机旋转坐标系，但不旋转也能快速通过。该方法仅需 20 分钟即可搞定，是目前最快的解法。
题解：CF1620F Bipartite Array
本文介绍了 CF1620F Bipartite Array 的解法。指出存在长度大于等于 3 的逆序对会产生奇环，不满足二分性质。因此需将数组排成两个上升子序列，并用动态规划求解，定义状态 a 和 b 分别记录前一位取正或负时另一段末尾的最小值。
题解：CF1684G Euclid Guess
本文讲解了 CF1684G Euclid Guess 的解法。根据元素 x 与 m 的比例关系，将数对分为大元素和小元素。大元素需匹配满足整除条件的小元素，小元素可自我消耗。最终将该构造问题转化为二分图匹配模型，利用 DFS 求解。
P3455 [POI 2007] ZAP-Queries
本文介绍了一道求最大公约数为特定值的数对数量的题目。通过莫比乌斯反演推导出计算公式后，利用整除分块技术将时间复杂度从 O(n) 优化至根号级别，并详细解释了整除分块的原理与代码实现。
CF 外训做题记录
本文分享了 CF1209E2 和 CF1922F 两道 Codeforces 题目的题解，均采用状压 dp。前者结合贪心策略优化列的选择，后者通过区间 dp 和 0/1 状态表示求解最小代价。
题解：UVA10111 Find the Winning Move
本文讲解了 alpha-beta 剪枝算法的原理及应用。文章先介绍 Minimax 算法，说明博弈树中双方分别求最大和最小值的搜索过程，随后阐述通过记录 alpha 和 beta 值剪去多余分支的优化思路。最后结合题目给出将胜负设为 1 和 -1 并枚举空位搜索的代码。
题解：P5270 无论怎样神树大人都会删库跑路
本文介绍洛谷题目 P5270 的解法。核心是设计哈希判断数字出现次数是否相同，并用 unsigned long long 自然溢出避免精度误差。针对大量询问，通过计算操作循环节优化复杂度，统计时需处理长度不足及非完整循环节部分。作者提醒注意细节。