3 数学常识

尚未进行身份认证

我要认证

DSFZ最低水平

等级
TA的排名 24w+

关于斐波那契数列的一些小(晓)性质

关于斐波那契数列的一些小性质1.gcd(Fi,Fi+1)=1gcd(Fi,Fi+1)=1gcd(F_i,F_{i+1})=1 这个看起来很显然 下面给出严谨的证明 利用数学归纳法: 我们已知F1=1,F2=1,F3=2F1=1,F2=1,F3=2F_1=1,F_2=1,F_3=2可知对于i≤3i≤3i \le 3,都有gcd(Fi,Fi+1)=1gcd(Fi,Fi+1)=1gcd(F_...

2018-06-16 16:22:24

【NOI2017】整数(压位分块+set)

【NOI2017】整数题目简述: 一开始你有一个数x=0x=0x=0 n(n≤106)n(n≤106)n(n \le 10^6)次操作: 1.给xxx加上a×2ka×2ka \times 2^k (a≤109,k≤3×107)(a≤109,k≤3×107)(a \le 10^9,k \le 3 \times 10^7) 2.查询xxx的二进制表达表示2b(b≤3×107)2b(b≤3×...

2018-06-15 15:36:21

bzoj3555 [Ctsc2014]企鹅QQ

bzoj3555 [Ctsc2014]企鹅QQ又是一道字符串哈希 这道题要求你求只差一位上的字母的字符串的对数。 观察范围n=30000,L=200n=30000,L=200n=30000,L=200 那就大力出奇迹就好了 暴力枚举哪一位不同就可以了 复杂度O(NLlog2N)O(NLlog2N)O(NLlog_2N) 随便跑无压力#include<iostream&...

2018-06-07 10:35:46

bzoj2795 [POI2012]OKR-A Horrible Poem[字符串hash]

bzoj2795 [POI2012]OKR-A Horrible Poem[字符串hash]蒟蒻第一次写字符串hash 瑟瑟发抖 简述题意:给你一个字符串,每次 询问你一个区间内字符串的最小循环节长度为多少 循环节有三个有趣的性质:循环节长度一定是序列长度的约数循环节的倍数还是循环节对于区间[l,r][l,r][l,r],如果s[l...r−len]=s[l+len...r]s...

2018-06-07 09:55:09

[SCOI2012]喵星球上的点名[广义后缀自动机]

题目链接 这道题一看就是SAM傻逼题吧 建一个广义后缀自动机,直接大力跑就可以了。 第二问的话可以存储每个节点可以作为哪些单词的结尾就可以了 luogu最后一个点TLE,我也不知道怎么回事#include<iostream>#include<cstdio>#include<cstring>#include<algorithm&am

2018-06-04 10:56:06

六 一 欢乐给给赛 T3题解

六 一 欢乐给给赛 T3题解题目传送门 这道题其实很简单,题如其名,不知道各路dalao为何装弱。 第一种解法: 对于每个查询进行贪心 复杂度:O((Q+1)n)=O(n2)O((Q+1)n)=O(n2)O((Q+1)n)=O(n^2) 实际得分:30 代码什么的就不粘了,大家肯定都会写。 第二种解法: 我们考虑到每个数都是正整数,说明以aiaia_i为lsq序列的第一个元素的...

2018-06-02 08:26:34

[bzoj4242]水壶【网格图曼哈顿最小生成树+树上倍增】

bzoj4242 水壶此题思路很明显,构造最小生成树之后在树上倍增即可 注:本题不一定存在最小生成树,可能只有最小生成森林 此题的难点在于怎么求最小生成树 我们需要最小化边集才能保证Kruskal的复杂度 我们将所有的建筑推入队列,对地图进行染色 如果两股势力相交了,就表明可能产生了一条在最小生成树上的边 我们利用这些边就可以快速求出最小生成树了 代码剧毒4K+ 自行欣赏...

2018-05-17 20:23:43

【bzoj3720】GTY的妹子树【块状树模板】

bzoj3720GTY的妹子树圆方树上块状果,点分树下你和我,虚树下面做游戏,仙人掌上欢乐多 这道题题目很长 大概说的是: 要求你写出一个数据结构,维护一颗带点权的树,兹瓷: ~~ 1. 单点修改点权 2. 查询子树内点权大于x的点的个数 3. 新给出一个点,并将这个点与已有点做link ~~似乎以前学过的任何数据结构都不能做这么奇怪的事情呢 我们的块状树就闪亮...

2018-05-17 14:48:19

bzoj4337树的同构

树的同构采用hash的方法判断是否同构 把每棵树的每个节点当作根节点求一次hash 我的计算方法: 将一个节点的儿子的hash排序 Hash[u]=∑i∗hash[i]∗prime[i]∗(i|prime[i])∗(ixorprime[i])∗hash[i])mod1000000007Hash[u]=∑i∗hash[i]∗prime[i]∗(i|prime[i])∗(ixorprime...

2018-05-15 20:25:33

九省联考 一双木棋

一双木棋状压+min-max对抗搜索 说出来丢人,笔者作为高一试水狗这题就滚粗了 我果然什么也不会 本题思路很明确,直接记忆化min-max对抗搜索即可 为啥我没想到 所谓min-max对抗搜索就是双方都采取最优策略,都希望获得最大值/最小值时应该采取的一种搜索方式 可以转化为一方希望得到最大值,一方希望得到最小值的问题 瞎**爆搜就可以了 每次判断一下轮到谁出手,即判断一下应...

2018-04-08 10:52:53

assass_cannotin的超级配对堆模板

template<class T,int maxsize,bool compare(const T &a,const T &b)>class Pairing_Heap{private: int nxxt[maxsize],to[maxsize],head[maxsize],fa[maxsize],Root,node[maxsize],node_index,H...

2018-03-22 12:14:25

HLPP模板 qaq

HLPP模板// luogu-judger-enable-o2#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#define MAXN 13000#define N 250000using nam...

2018-03-20 11:28:13

最小费用最大流模板

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#define MAXN 1000010using namespace std;inline void read(int &x){ in...

2018-02-27 13:03:05

NOIP 2017 列队

列队题目传送门 我是向其他dalao学会了这个神奇的解法,但是在某知名优秀OJ上会被卡成90分 真是令人伤心&&头大 算了 我不打算卡常了 本蒟蒻只会用Splay这种低级数据结构 像树状数组常数这么小的神奇数据结构我根本不会 分块真是令人头大 算了,这题关分块p事 考虑每次的操作我们弹出(x,y),在调整矩阵,再将(x,y)加到矩阵右下角 大概是这样 复杂...

2018-02-26 20:30:23

Euler-Tour Tree模板[bzoj 3786]及其講解

Euler-Tour-TreeETT即Euler-Tour-Tree,也就是什麽歐拉游覽樹 是一種可以維護子樹操作的動態樹 支持link,cut,單點修改,子樹修改,查詢點到根的信息 (爲什麽別的不行呢?因爲我不會,貌似ETT不支持換根,鏈操作什麽的) 怎麽做呢? 我們維護一棵樹的歐拉序 歐拉序是括號序列,一個點進棧時記錄一次dfn,出棧時再記錄一次dfn 就得到了一個有趣的序列...

2018-02-25 20:40:58

【非旋Treap的近親?!】左偏樹[數組版]

左偏樹話説左偏樹和非旋Treap好像好像的呢 沒什麽可説 至於爲什麽用數組寫 是因爲luogu模板題要求刪除最前面那個數用指針寫起來麻煩#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>#d...

2018-02-24 21:24:42

非旋Treap練習題(維護父指針)ZJOI2006書架

這道題沒什麼好說的, 比較特殊的一點就是要維護父指針來查詢比指定點小的節點個數 具體看一下代碼就清楚了#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define MAXN 80010using namespace std;inlin...

2018-02-13 11:37:03

Treap永不旋轉!!![維修數列]

前言Splay是會轉的的好,Treap是不會轉的妙,我們不用轉也能實現神奇的操作 在這裡比較複雜的是插入區間的操作,這是Treap沒有嘗試過的如何O(n)O(n)O(n)構造Treap?Splay可以遞歸構造,但是Treap有key的問題,顯然不能那樣構造 那怎麼構造呢? 我們利用棧來解決這個問題 我們將每次構造出來的節點放到棧裏,當我們再次要構造一個新節點時,我們和棧頂節...

2018-02-11 23:15:21

非旋Treap的區間翻轉(文藝平衡樹)

前言在學習這一節之前顯然要先會非旋Treap的基本操作 Split和MergeSplit和MergeSplit和Merge就可以了正題首先,我們用Treap的中序遍曆來代表現在的數列 顯然翻轉區間相當於交換子樹 同時值得注意的是堆的性質不會影響到樹的中序遍曆(這個自己要想一想) 我們在之前強調Merge(a,b)Merge(a,b)Merge(a,b)的大小問題,在這裡只要...

2018-02-11 15:40:28

非旋Treap維護普通平衡樹的基本操作

前言其實我寫過旋轉的Treap,我也寫過可以旋轉不停的Splay 但是我發現Splay克我,所以我學了一下神奇的非旋Treap 效率並不低,效率較低的部分在insert,要調用4次O(log2n)O(log2n)O(log_{2}{n})的函數 其他操作或1次或2次 表現較好在我們學習之前我們可能需要一些關於旋轉Treap的知識帶旋轉Treap本文並不是講述帶旋轉Treap的文...

2018-02-11 13:34:56

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!