Logo

菜单

一些短小有趣的题
数学 #数论#导数#极限

一些短小有趣的题

快回老家了，闲来无事遇到了一些有趣的小问题，作为活跃思维的小菜还是挺好的。 \pi^e 和 e^\pi 谁大？ 这题是和同学讲批话时想到的。 主要体现了一个统一形式的想法，先说结论 e^\pi> \pi^e ，下面证明它。 即证：e^{\frac{1}{e}}>\pi^{\frac{1}{\pi}}

fogflea 发布于 2026-02-14
CF1476F Lanterns
Sol #dp#贪心

CF1476F Lanterns

题 Sol 应该存在一种经典技巧吧，就是那种可行性DP通过某种手段（感觉最常见的是贪心）压缩一个状态维度。 看到这个题首先应该有个 \texttt{native} 的想法（基于经验？）：考虑设 f_{i,j} 为考虑前 i 个灯笼，能覆盖前缀 [1,j] 的可行性。 然后这里估计能列个方程吧，又或者

fogflea 发布于 2025-08-27
一些对象的基本转化和分类方式
方法总结

一些对象的基本转化和分类方式

转化的基本方向： 复杂 -> 简单 性质少 -> 性质多 序列 单个元素 研究一个元素 x 和整个序列的偏序关系可将每个元素按 >x ， <x 化为 1,0 可将一个元素变为一个坐标点 (index,x) 区间 可将一个区间

fogflea 发布于 2025-08-13
[ZJOI2019] 语言
Sol #虚树#树上差分#线段树#ZJOI

[ZJOI2019] 语言

From zxy的思维技巧 而来。 传送门 这真是一道套路的好题啊。 首先要计算二元组 (a,b) 的个数，看数据范围肯定枚举一个 a ，然后计算所有满足的 b ，最后求和后除以 2 。 然后具体的考虑怎么计算所谓 b 的个数，考虑一个点 u ，

fogflea 发布于 2025-07-18
重链剖分
算法学习 #树剖

重链剖分

重链剖分剖分方式 重链剖分的剖分方式是：每次选择子树中最大的子树作为重儿子，其余的子树作为轻儿子。而重链是指一条从根节点到当前节点的路径上，出根节点外，链上其他节点都是重儿子的连边构成的链。如下图： 图中的红色边就是重链，而黑色边就是轻链。每个叶子节点也有一条以自己为起点，长度为 0 的重链。 从图

fogflea 发布于 2024-08-29
倍增法求LCA
算法学习 #图论#树论

倍增法求LCA

朴素算法求LCA 首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲 int lca(int u, int v) { if (depth[u] < depth[v]) { swap(u, v); } while (depth[u

fogflea 发布于 2024-08-23
BSGS算法
算法学习 #数论

BSGS算法

离散对数问题 假设有一个同余方程a^x \equiv b \pmod m，其中a,b,m都是给定的整数，a与m互素。如何求解x的值？ 第一个想法可能是暴力枚举，将x从0开始枚举到m-1，直到找到一个满足方程的x。时间复杂度是

fogflea 发布于 2024-08-23
模意义下的乘法逆元
OI #数论

模意义下的乘法逆元

乘法逆元在我看来就相当于模意义下的除法，在模意义下，如果 a 和 m 互质，那么 a 关于模 m 的乘法逆元 a^{-1} 存在，且满足 a \times a^{-1} \equiv 1 \pmod m。 本文主要讲解乘法逆元的四种求法。 费马小定理方法 费马小定理表明对于任意整数 a 和素数 p，

fogflea 发布于 2024-08-23
扩展欧几里得算法
算法学习 #数论

扩展欧几里得算法

欧几里得算法是求解两个数的最大公约数的算法，而扩展欧几里得算法则是求解一元线性方程 ax+by=c 的整数解的算法，是欧几里得算法的升级版，也是提高的数论内容中的重要算法之一。 这个算法的原理是利用欧几里得算法求解最大公约数的过程中，不断地更新 x 和 y 的值，直到求解出整数解。具体的过程如下：

fogflea 发布于 2024-08-22
线段树
数据结构学习 #线段树

线段树

线段树真的是一种挺折磨人的数据结构，但它的应用范围也是非常广泛的。它可以在 O(\log n) 的时间内完成区间修改和区间查询。似乎有句话是这么说的：树状数组能做的，线段树都能做；线段树能做的，树状数组不一定能做。 线段树的操作 线段树是一种二叉树，它的每一个节点都代表了一个区间。对于一个区间 [l

fogflea 发布于 2024-08-22
树状数组
数据结构学习 #树状数组

树状数组

二十天左右的集训结束了，虽然学校的教学完全学不到任何东西，但得承认通过自学学到了不少东西。 自学的第一个知识就是树状数组，它可以在 O(\log n) 的时间内完成单点修改和前缀和查询。由于码量奇少，在搭配上差分数组和权值数组，就能实现许多骚操作。 树状数组的结构 以下以维护区间和为例。假设使用c[

fogflea 发布于 2024-08-20
上一页 下一页