夜间模式
字体
阴影
滤镜
主题色
拓展欧几里得算法与应用
欧几里得算法 即:$gcd(a,b)=gcd(b,a$%$b)$ 欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法——$gcd$。 说白了就是求最大公约数。一行代码搞定: [crayon-5e319144725c3433980117/] 拓展欧几里得算法 定理 定理1:设$a$和$n$不全为$0$,则存在整数$x,y$,满足$ax+by…
Luogu 2019三月月赛 P5239 回忆京都 题解
题意 题目背景讲太多了吧。。。一句话题意: 有$Q$个询问,每个询问求出: $$\sum_{i=1}^n\sum_{j=1}^m C_j^i$$ 对于$60$%的数据,$q \leq 10, n\leq100,m\leq100$。 对于$100$%的数据,$q \leq 1000,n\leq1000,m\leq1000$。 思路 对于60%的数据 …
10182. 「一本通 5.5 练习 3」理想的正方形
题意 有一个 $a\times b$ 的整数组成的矩阵,现请你从中找出一个 $n\times n$ 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 思路 设$dp[i][j][k]$表示以$i,j$为左上角的正方形变成为$k$内的最大值,$dp2[i][j][k]$表示最小值。 可知,$dp[i][j][k]=max(dp[i+1][j…
zkw线段树 学习笔记
前置知识 C++位运算学过线段树(其实关系不大) 什么是zkw线段树 就是一种线段树。(废话) 与普通线段树相比,zkw线段树更快、更短小。 本篇博客讲一个例题:Luogu P3372 普通线段树 zkw线段树 zkw线段树的实现 首先来看一看变量的定义与BuildTree操作 这是一棵求和的线段树(废话) 然后我们发现它有16个叶子节点。 而$1…
2240. 「CQOI2014」数三角形
三倍经验 LOJ #2240. 「CQOI2014」数三角形 BZOJ 3505: [Cqoi2014]数三角形 Luogu P3166 [CQOI2014]数三角形 (Luogu要大一些。。。) 题意 给定一个$n \times m$的网格,请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三…
主席树(静态) 学习笔记
在学习主席树之前 你必须学习: 线段树。 前缀和。 sort函数、unique函数以及lower_bound函数的使用方法。 什么是主席树 主席树又叫函数式线段树,又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。 主席树的模板 由于主席树比较难理解,所以结合代码理解一下: [crayon-…
10137. 「一本通 4.4 练习 4」跳跳棋
题意 跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏:棋盘上有三颗棋子,分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$(注意:棋子是没有区别的)。跳动的规则很简单,任意选一颗棋子,对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。…
10187. 「一本通 5.6 例 4」Cats Transport
题意 小S养了$M$只猫,雇了$P$位饲养员。农场旁边有$N$座山,从$1$到$N$编号,第$i$座山与第$i-1$座山的距离为$D_i$,饲养员都住在$1$号山上。 有一天,第$i$只猫到第$H_i$座山玩,一直玩到$T_i$停止。饲养员们必须接回所有的猫,饲养员们行走的速度为$1$个单位每单位时间。 问如何计划每个饲养员从$1$号山出发的时间,…
10162. 「一本通 5.2 练习 5」骑士
题意 有$n$个骑士,每个骑士有一个自己的战斗值,每个骑士也有且仅有唯一一个自己讨厌的骑士,每个骑士不可能与自己讨厌的骑士一起上场战斗,问最高的战斗值之和是多少? 思路 这道题与没有上司的舞会很像。但是注意,这道题可能会有环的存在,所以我们需要对于每个环,把它切割成两部分,再分别树形dp,然后取最大值,加入ans中。 树形dp的思路很简单: 设$f…