基本定理 算术基本定理 任何一个合数均可被唯一分解成若干质数的乘积。 也就是说任何合数都可以唯一地表示成 的形式，这条定理在之后的质数筛中有大用。 素数定理 中的质数个数约等于 可以用来粗略估计在当前数据范围下质数的个数，以便更具有针对性的选用质数筛法。据说这个定理有一个非常初等的证明，仅涉及到极限、自然对数函数和指数函数的一些简单性质（子供向），非常适合初中生茶余饭后作为谈资...

数位DP 简介 数位DP是一种基于按位枚举的计数类DP。一般来说，当题目要求对所有符合特殊性质的数字计数（且这些性质可以转化到数位上讨论）、对给定区间内的合法数做统计、数据范围中出现了超大的上界时，就可以考虑使用数位DP来进行求解。 数位DP的时间复杂度基本上是 级别的，其中 为状态数，可以看作是记忆化搜索数组每一维上界的总乘积。因此在大多数情况下它能做得很好。 数位DP 基本实现 数位...

您已获得最佳的阅读体验！ 题目地址：P10503 假设我们有一个称为 233 矩阵。在第一行，它可能是 233、2333、23333...（表示 ，，...）。此外，在 233 矩阵中，我们有 。现在已知 ，你能告诉我 233 矩阵中的 吗？ 发现 很小、 很大，于是选择使用 的矩阵快速幂做法。 假设矩阵一开始存储 列的信息，它看起来是这样的： 由于涉及到 的计算，我们需要...

您已获得最佳的阅读体验！ 题目地址：P10938 题目难度：省选/NOI- Vani 和 cl2 在一片树林里捉迷藏。 这片树林里有 座房子， 条有向道路，组成了一张有向无环图。 树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。 如果从房子 沿着路走下去能够到达 ，那么在 和 里的人是能够相互望见的。 现在 cl2 要在这 座房子里选择 座作为藏身点，同时 V...

您已获得最佳的阅读体验！ 题目地址：P10939 题目难度：提高+/省选- 给定一个 的棋盘，有一些格子禁止放棋子。 问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。 看到数据范围，，状压 DP 肯定是没戏的。转而寻找其他能够解决棋盘问题的算法。 棋盘是这样的（从隔壁 P3355 借的图）： ...

您已获得最佳的阅读体验！ 题目地址：P10935 题目难度：提高+/省选- 银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。 我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 。 现在对于 颗我们关注的恒星，有 对亮度之间的相对关系已经判明。 你的任务就是求出这 颗恒星的亮度值总和至少有多大。 输入格式： 第一行给出两个整数 和 。 之后 行，每行三个...

您已获得最佳的阅读体验！ 题目地址：P7812 题目难度：省选/NOI- 题目类型：提交答案  Special Judge 本题为提交答案题。 给你一个长为 的序列 ，定义 的排列 的权值为 你可以理解为这个排列是一个环，即 。 请构造一个权值尽量大的 的排列。 输入格式： 第一行一个整数 。 第二行 个整数表示序列 。 输出格式： 一行 个整数表示排列。 数据范围： 对于 ...

前言 遗传算法Genetic Algorithm，简称 GA。是一种基于随机化的最优解搜索算法，它和模拟退火Simulate Anneling都基于随机化，遗传算法通过模拟自然界生物的遗传和变异、自然选择和淘汰的过程来找到最优种群（最优解）；后者则是通过设定一个初始温度以及降温率、将当前最优解进行随机扰动以寻得更优的解来找到最优解。 （纯属虚构）遗传算法就好比生活在中原地区的 OIer 们，...

退火与模拟退火 退火，是一种物理过程。指通过将固体加热到一定温度，并让温度缓慢降低，从而让高能的粒子能够在每个温度均达到平衡态，最终让整个固体变为内能最小的状态的过程。通常用这个方法来使固体硬度变得更高。 而模拟退火则是使用计算机语言模拟物理学中退火的过程，达到求多峰函数最优解近似值的功能。它通过设定一个模拟初始温度、以及一个终止温度（可以理解为精度）和一个衰减率，每次随机选取一个函数值，并...

您已获得最佳的阅读体验！ 集训时讲到了这个题，刚好写篇题解记录一下思路。 题目地址：P3571 题目难度：NOI/NOI+/CTSC 给定一棵 个节点的有根树，根节点为 。 次询问，每次给定一个 ，用最少的操作次数遍历完整棵树，输出最少操作次数。每次操作可以选择访问不超过 个未访问的点，且这些点的父亲必须在这次操作之前被访问过。 。 这道题其实有一个裸结论可以套： 对于一棵树，一定...