义往尘沙

分类

数据结构(1) 未归档(4) 算法(1)

/ 注册

全部文章（共6篇）

Nim游戏入门+SG函数

对于经典的Nim游戏，只需要把每一堆初始状态都异或起来，最后得到的结果非0的为必胜状态，结果为0的为必败状态。原理：异或的结果非0的状态总能通过一次取物品操作，将此状态转化为结果为0的状态；而异或结果为0的状态如果不是最终状态（所有堆都是0）经过一次取物品操作，总会变为异或结果非0的状态...

2021-07-29

0 528

线段树模板+简短解析

不多bibi，线段树懂得都懂，会用才是最难的 struct Node { int l,r; //int s/Max/Min/.....想要用线段树存的东西，下文中用X代替 //int lz //懒标记，在需要区间修改的题目中使用 }tr[N]; inline void push_...

2021-07-29

0 458

入门思维题题单

题解：某些思维题的题解.md-C/C++文档类资源-CSDN下载 1.取因数 https://ac.nowcoder.com/acm/contest/11176/A 2.玩游戏 https://ac.nowcoder.com/acm/problem/15874 3.GCD https...

2021-07-29

0 584

卡特兰数简要原理及组合数实现

卡特兰数就结论来说是指从1到n所有数经过入栈和出栈后得到的排列的种类数，值为 C(2n,n)/(n+1) 原理：将其转换为从(0,0)点到(n,n)点的路径数中不越过y=x线的路径数，用所有的路径数减去非法路径数，每条非法路径都会经过y=x+1这条线，将其经过y=x+1这条线后的路径对这条线作...

2021-07-29

0 742

除法取模及快速幂模板

除法是不能直接相除取模的，所以需要将除法转换为乘法即：变形得 ≡ 1 (mod p) 由费马小定理 %p ≡ 1 (mod p) 得 ≡ 1 (mod p) 即 b 对质数 p 的逆元快速幂模板： int Mod = 1e9+7; ll gmi(ll a, ll b =...

2021-07-29

0 840

ST表，O(1)查询区间最大(小)值

ST表首先预处理了一部分的区间最大值，处理的部分的左端点为数组的每个点，长度为的所有区间，个数就是个，查询时将查询的区间分成可能有重叠的两部分，查询的值就是这两部分的最大值，分成的两部分的长度均为，这样两部分就都可以直接查询，具体实现： const int N = 1e5 + 7;...

2021-07-29

0 579