jijidawang
jijidawang
全部文章
分类
未归档(35)
题解(1)
归档
标签
去牛客网
登录
/
注册
jijidawang的博客
全部文章
(共36篇)
题解【洛谷 P1466 [USACO2.2]集合 Subset Sums】
题目传送门 设 \(sum=1+2+3+4+\dots+n=\dfrac{n(n+1)}{2}\)。 如果 \(2\nmid sum\),则显然没有方案。 如果 \(2\mid sum\),则这两个集合的和必为 \(\dfrac{sum}{2}\)。 将 \(\dfrac{s...
题解
dp
洛谷
背包
2020-05-13
0
395
乘法逆元
前置芝士: 同余 普通逆元 逆元是模意义下的除法。 就是求解同余方程 \(ax\equiv 1\pmod m\)。 用 exgcd 求解即可。 Code: #include<iostream> #include<cstdio> using namesp...
2020-05-09
0
309
浅谈二维前缀和
首先要了解一个叫做前缀和的东西。 二维前缀和其实就是将普通前缀和加了一维。 也就是可以求一个矩阵内任意子矩阵元素和。 仿照一维前缀和,转移方程如下: \[sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j} \] 这个转移方...
2020-05-09
0
320
浅谈位运算
目录 位运算前言 位运算应用 1 快速幂 2 最大公约数 3 xor 一些应用 4 其他 位运算前言 程序中所有东西在计算机中都是以二进制储存的。 位运算可以直接操作这些二进制。 所以位运算相对于普通运算要快。 这些是所有位...
2020-05-09
0
311
浅谈 Lucas 定理
Lucas 定理是用来求 \(C^n_m\mod p\) 的。 定理 \[C^n_m\equiv C^{n\bmod p}_{m\bmod p}\times C^{n/p}_{m/p}\pmod p \] 证明 由二项式定理得 \(C_a^b\) 为 \((1+x)^a\) 中 \(...
2020-05-09
0
257
浅谈 exgcd
众所周知欧几里得算法是: \[\gcd(a,b)=\gcd(b,a\bmod \,b) \] 也叫辗转相除法。 拓展欧几里得算法(exgcd),可以用来找到形如 \(ax+by=\gcd(a,b)\) 的方程的一组特解。 由裴蜀定理知,原方程一定有解。 我们利用辗转相除法(普通欧几...
2020-05-08
0
355
【洛谷P1754 球迷购票问题】题解
传送门 卡特兰数经典 \(\texttt{AB}\) 分拆问题。 分析: 题意相当于排列 \(n\) 个 \(\texttt A\) 和 \(n\) 个 \(\texttt B\),使得相邻 \(\texttt{AB}\)(有序!)消掉,然后左右元素并到一起再消,最后消完的序...
题解
dp
洛谷
2020-05-08
0
313
浅谈前缀和
引入 如果你想维护一个数据结构,有一个序列 \(a\),每次查询 \(l\sim r\) 区间和(求 \(\sum\limits_{i=l}^ra_i\)),只有查询,线段树&树状数组难免有些大材小用,但是维护它效率要高,甚至要达到 \(\mathcal{O}(1)\)。 这个东西该怎么...
2020-05-03
0
246
浅谈 LCA
LCA(Least Common Ancestors),最近公共祖先,定义为两节点最近的公共祖先好像是废话 前置芝士: 图论 此文章中均设 \(\mathrm{fa}_i\) 为 \(i\) 的父亲,\(\mathrm{dep}_i\) 为 \(i\) 的深度。 暴力 显然我...
2020-05-03
0
234
浅谈Meet in the middle——MITM
目测观看人数 \(0+0+0=0\) \(\mathrm{Meet\;in\;the\;middle}\)(简称 \(\rm MITM\)),顾名思义就是在中间相遇。 可以理解为就是起点跑搜索树基本一半的状态,终点也跑搜索树基本一半的状态,最后撞到中间,一种类似双向 DFS 的东西...
2020-04-20
0
441
首页
上一页
1
2
3
4
下一页
末页