P11996 我是黄色恐龙大将军 题解 题目重述 对于正整数 nnn，定义： ana_nan​ 为 2n2^n2n 在十进制下的最高非零位数字 bnb_nbn​ 为 5n5^n5n 在十进制下的最高非零位数字 求所有可能的 an×bna_n \times b_nan​×bn​ 的值的和（相同值仅计算一次）。 解题思路 关键步骤 观察模式 计算前若干项的 an×bna_n \time

更加洛谷的观感感受 写数论文章写爽了。 矩阵快速幂 矩阵乘法 矩阵乘法要求 设 AAA 为 m×pm \times pm×p 的矩阵，BBB 为 p×np \times np×n 的矩阵。 矩阵乘法必须第一个矩阵的列数等于第二个矩阵的行数。 A×BA \times BA×B 是一个 m×nm \times nm×n 的矩阵。 矩阵乘法定义 设 A×B=CA \times B = CA×B=

更洛谷的观感体验。 好吧，也是不鸽了，上篇文章的续集来了。 筛法求因数和 给定 nnn，求 111 ~ nnn 的因数和。 前置芝士补充 根据唯一分解定理，一个数 nnn 为： n=∏i=1spiain=\prod_{i=1}^s p_i^{a_i} n=i=1∏s​piai​​ 一个质数 piaip_i^{a_i}piai​​ 的因数有 pi0,pi1,pi2,…,piaip_i^0,p_i

筛法基础 给定 nnn，求出 111 ~ nnn 中所有的质数，封装成 get_prime(int n) 的数组。 暴力 不就是验证质数 nnn 遍吗？ int p[N], cnt; bool is_prime(int x) { if(x == 1) return false; for(int i = 2; i * i <= x; i++) if(x % i == 0)

更洛谷的观感体验 题目分析 这道题说了一棵特殊的树，其中每个节点 kkk（2≤k2\leq k2≤k）的父节点是 kkk 的最大真因数（kkk 的因数中除了 kkk 本身外最大的因数）。根节点是 111。要处理多个查询，每个查询给出两个节点编号 xxx 和 yyy，需要计算它们在树上的距离（即连接路径的边数）。 观察 每个节点的父节点是其最大真因数。例如： 节点 333 的父节点是 111（

教练要求做的题，没想到可以发题解。 题意 将 nnn 个点分为 222 个矩阵，使其面积最小。 做法 先按照距离 (0,0)(0,0)(0,0) 点的 xxx 或 yyy 的差值递增排序（按 xxx 分一次, yyy 分执行一次）。 再枚举从那个点分为两部分，算出面积即可。 在计算面积面积时需要知道区间最大值和最小值，需要用到 ST 表。 注意：不开 long long 见祖宗。 代码 #i

又有题可以发题解啦。 题目大意 第 iii 天可以收入 bib_ibi​，1块可以换 aia_iai​ 个游戏币，每个游戏币能去玩无梦，问每天最多玩多少。 思路 显然，这道题具有单调性，所以可以用二分。 那 check 该如何考虑？ 单调栈，记录一个 pip_ipi​，为第 iii 天的下一个更优的 aia_iai​（即 api>aia_{p_i} > a_iapi​​>a

树链剖分：shù liàn pōu fēn。 （为什么要写拼音因为总是拼成pō和pāo）。 思路 模板题：。 初步分析 这道题需要把树的路径当做区间修改。 所以区间修改你想到了什么？ 没错，。 但是路径是不连续的，怎么区间修改。所以就需要多个连续区间赋值。 树链剖分 （网上找了张图，觉得挺好。） 重孩子、轻孩子和重链 首先我们需要知道重孩子、轻孩子和重链。 以下内容要求全文背诵。 重孩子

美好的一天从写题解开始。 感谢 @jhdrgfj 的思路 思路 很显然，设 fi,jf_{i,j}fi,j​ 为在第 iii 天造成 jjj 点伤害。 但是，每一天都是一个 01 背包，任意两天的魔力值都是互不影响的，所以考虑每一天一次 dp。 设 fif_ifi​ 为将魔力值提高到 iii 的最小花费（当天），就是求 01 背包。 code #include<bits/stdc++.h

这题是一道绝世好题。 为什么咩？ 因为它代码长。 因为它没有运用什么高级算法，但用低级算法组成了一道紫题。 题意转化 读完题后，我们可以发现，重复吃菜是对题目没有贡献的，所以即使没有能吃并且没有吃过的的菜，也不重复吃。 换一种讲法，就是每种菜只有一盘，问最少要吃多少天。（原本是周，以下为了方便说成天） 思路 首先，根据算法标签我们得知应该使用二分，因为算法标签天数越多越容易每种菜都吃一遍，反之