[Dr.Lib]Note:Data Structures – C++ STL

本着不重新发明轮子的原则,我很少手码快排和其他数据结构……基本都是拖STL出来用……

STL中还是有不少实用的数据结构的……set,bitset,priority_queue,queue,vector,map……

bitset

Via http://www.cplusplus.com/reference/bitset/bitset/

Member functions

(constructor)
Construct bitset (public member function )
applicable operators
Bitset operators (function )

 

Bit access

operator[]
Access bit (public member function )
count
Count bits set (public member function )
size
Return size (public member function )
test
Return bit value (public member function )
any
Test if any bit is set (public member function )
none
Test if no bit is set (public member function )
all 
Test if all bits are set (public member function )

 

Bit operations

set
Set bits (public member function )
reset
Reset bits (public member function )
flip
Flip bits (public member function )

 

Bitset operations

to_string
Convert to string (public member function )
to_ulong
Convert to unsigned long integer (public member function )
to_ullong 
Convert to unsigned long long (public member function )

在一些模拟中……bitset还是不错的……不过用处也不是很大……

priority_queue

Member functions

(constructor)
Construct priority queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
top
Access top element (public member function )
push
Insert element (public member function )
emplace 
Construct and insert element (public member function )
pop
Remove top element (public member function )
swap 
Swap contents (public member function )

优先队列的用处就比较多了,据说优先队列优化dij秒爆SPFA[来源请求]……

只要定义了 operator< ,就可以用优先队列来做成大顶堆。小顶堆……要么改operator<,要么

priority_queue<T, vector<T>, greater<T> >

queue

Member functions

(constructor)
Construct queue (public member function )
empty
Test whether container is empty (public member function )
size
Return size (public member function )
front
Access next element (public member function )
back
Access last element (public member function )
push
Insert element (public member function )
emplace 
Construct and insert element (public member function )
pop
Remove next element (public member function )
swap 
Swap contents (public member function )

有优先队列优化的dij,就有队列优化的Bellman-Ford……

vector

Member functions

(constructor)
Construct vector (public member function )
(destructor)
Vector destructor (public member function )
operator=
Assign content (public member function )

Iterators:

begin
Return iterator to beginning (public member function )
end
Return iterator to end (public member function )
rbegin
Return reverse iterator to reverse beginning (public member function )
rend
Return reverse iterator to reverse end (public member function )
cbegin 
Return const_iterator to beginning (public member function )
cend 
Return const_iterator to end (public member function )
crbegin 
Return const_reverse_iterator to reverse beginning (public member function )
crend 
Return const_reverse_iterator to reverse end (public member function )

Capacity:

size
Return size (public member function )
max_size
Return maximum size (public member function )
resize
Change size (public member function )
capacity
Return size of allocated storage capacity (public member function )
empty
Test whether vector is empty (public member function )
reserve
Request a change in capacity (public member function )
shrink_to_fit 
Shrink to fit (public member function )

Element access:

operator[]
Access element (public member function )
at
Access element (public member function )
front
Access first element (public member function )
back
Access last element (public member function )
data 
Access data (public member function )

Modifiers:

assign
Assign vector content (public member function )
push_back
Add element at the end (public member function )
pop_back
Delete last element (public member function )
insert
Insert elements (public member function )
erase
Erase elements (public member function )
swap
Swap content (public member function )
clear
Clear content (public member function )
emplace 
Construct and insert element (public member function )
emplace_back 
Construct and insert element at the end (public member function )

Allocator:

get_allocator
Get allocator (public member function )

vector是个好东西,妈妈再也不用担心我的内存!

数组开大了爆内存,开小了爆下标……WTF……

还用的着担心邻接表MLE?vector没有压力。

map

Member functions

(constructor)
Construct multimap (public member function )
(destructor)
Multimap destructor (public member function )
operator=
Copy container content (public member function )

Iterators:

begin
Return iterator to beginning (public member function )
end
Return iterator to end (public member function )
rbegin
Return reverse iterator to reverse beginning (public member function )
rend
Return reverse iterator to reverse end (public member function )
cbegin 
Return const_iterator to beginning (public member function )
cend 
Return const_iterator to end (public member function )
crbegin 
Return const_reverse_iterator to reverse beginning (public member function )
crend 
Return const_reverse_iterator to reverse end (public member function )

Capacity:

empty
Test whether container is empty (public member function )
size
Return container size (public member function )
max_size
Return maximum size (public member function )

Modifiers:

insert
Insert element (public member function )
erase
Erase elements (public member function )
swap
Swap content (public member function )
clear
Clear content (public member function )
emplace 
Construct and insert element (public member function )
emplace_hint 
Construct and insert element with hint (public member function )

Observers:

key_comp
Return key comparison object (public member function )
value_comp
Return value comparison object (public member function )

Operations:

find
Get iterator to element (public member function )
count
Count elements with a specific key (public member function )
lower_bound
Return iterator to lower bound (public member function )
upper_bound
Return iterator to upper bound (public member function )
equal_range
Get range of equal elements (public member function )

Allocator:

get_allocator
Get allocator (public member function )

map用在一些需要存储键值对的地方……在一些需要维护数据的地方用这个偷懒一下也不错……

别忘了multimap。

 

[Dr.Lib]Note:Data Structures – 数据结构那些事

树状数组

[Dr.Lib]Note:Algorithms – 树状数组
树状数组是个简单高效的数据结构,实质上是省掉一半空间后的线段树加上中序遍历{Via ZKW《统计的力量》}

一般情况下,他可以做到单点更新,区间求和。

 http://wikioi.com/problem/1080/

小小的差分一下,就可以做到区间更新单点值

http://wikioi.com/problem/1081/

问题是区间更新区间和呢?

只能上线段树了吗?

NO!

http://wikioi.com/problem/1082/

朴素线段树

[Dr.Lib]Note:Algorithms – 线段树

*计算几何在长期的发展中,
诞生了许多实用的数据结构。
*区间查询,穿刺查询都是计算几何解决的问题
*作为特例中的特例,线段树解决的问题是:
*一维空间上的几何统计
 Via 《统计的力量》

线段树(Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

对于线段树中的每一个非叶子节点[a,b],它的左子树表示的区间为[a,(a+b)/2],右子树表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树。叶节点数目为N,即整个线段区间的长度。

http://wikioi.com/problem/1191

ZKW线段树

参见《统计的力量》

 

 

[Dr.Lib]Note:Math – 欧拉函数

正在纠结要不要码一篇欧拉函数……IvyEnd神犇的大作就已经出炉了……

Via http://www.ivy-end.com/archives/1021

欧拉函数\(\varphi \left ( N \right )\)表示小于或等于\(N\)的正整数中与\(N\)互质的数的个数。又称\(\varphi\)函数、欧拉商数。

下面介绍欧拉函数的几个性质:

  • \(\displaystyle\varphi\left ( 1 \right )=1\)。
  • \(\displaystyle\varphi \left( N\right )=N\cdot\prod_{p\mid N}\left ( \frac{p-1}{p} \right )\)。
  • \(\displaystyle\varphi \left ( p^{k} \right ) = p^{k}-p^{k-1}=\left(p-1 \right )\cdot p^{k-1}\),其中\(p\)为质数。
  • \(\displaystyle\varphi \left(mn \right )=\varphi \left(m \right )\cdot \varphi \left(n \right )\),其中\(\gcd \left ( m,n \right )=1\)。

我们根据这几个性质就可以求出欧拉函数。

基本思路是首先置\(\varphi \left ( N \right )=N\),然后再枚举素数\(p\),将\(p\)的整数倍的欧拉函数\(\varphi \left ( kp \right )\)进行操作\(\varphi \left ( kp \right )=\varphi \left ( kp \right )\cdot \frac{p-1}{p}\)即可。

以及求单点的函数值

应用:

欧拉定理

\(a^{\varphi(n)}=1 \mod {n}\)

 

原根个数

\(\varphi \left ( \varphi \left ( N \right ) \right )\)

对于原根的定义,我们可以这样来叙述:

若存在一个实数\(a\),使得\(a^{i}\mod{N},a\in\left \{ 1,2,3,\cdots ,N \right \}\)的结果各不相同,我们就成实数\(a\)为\(N\)的一个原根。

原根的个数等于\(\varphi \left ( \varphi \left ( N \right ) \right )\)。这样我们就可以很方便的求出原根的个数。(参考题目

指数循环节

Via http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9

\( A^{x}=A^{x\%\varphi(C) + \varphi(C)} \mod{C} (x \ge \varphi(C))\)

[Dr.Lib]Note:解题报告 – 上网(DP)

题4  上网

【问题描述】

假设有n个人要上网,却只有1台电脑可以上网。上网的时间是从1 szw 至 T szw ,szw是sxc,zsx,wl自创的时间单位,至于 szw怎么换算成s,min或h,没有人清楚。依次给出每个人在某个时间段内上网的快乐程度C(必须这个人在整个时间段内都在上网,才能获得快乐程度C,否则,快乐程度是0),请你得到使总的快乐程度达到最大的方案。

【输入格式】

第1行2个整数 n和T,含义如题目所述;

接下来有n个这样的结构(每两个相邻的结构之间有一空行,且第1个结构和第一行间有一空行):

第1行一个整数Mi,表示第i个人的时间段的个数;

接下来有Mi行,每行3个整数Xj,Yj,C,表示第i个人在[Xj,Yj]内上网的快乐程度为C,

因此有Xj-Yj-1=1,X1=1,Ymi=T,Xj<=Yj。

【输出格式】

仅输出一行,为总的最大的快乐程度。

【输入样例】

3 10

 

3

1 3 6

4 7 9

8 10 3

 

3

1 3 5

4 7 10

8 10 1

 

4

1 3 2

4 8 2

9 9 6

10 10 3

【输出样例】

25

【样例说明】

在[1,3]内,安排1上网,快乐程度为6;

在[4,7]内,安排2上网,快乐程度为10;

在[8,8]内,不安排;

在[9,9]内,安排3上网,快乐程度为6;

在[10,10]内,安排3上网,快乐程度为3;

这是使总的快乐程度达到最大的方案,对应的值是25。

【数据范围】

对于30%的数据,n<=4,所有的Mi<=5,T<=20;

对于60%的数据,n<=100,所有的Mi<=100,T<=2000;

对于100%的数据,n<=500,所有的Mi<=500,T<=500000,所有的0<C<=10^9,并保证最终解Max<=10^9。

 

【标程】

很明显,前30%的数据可以用暴力过,直接枚举每一个区间即可,时间复杂度是2^(n*m)

其实,拿到这到题,就很容易想到DP,用max[i]表示第i szw后,所能达到的最大快乐程度,状态转移方程如下:max[i]=max{max[i-1]max[x-1]+C[x,i]},边界情况max[0]=0,其中C[x,i]表示从x时刻开始玩到i时刻的快乐程度。具体操作时,枚举所有结束时刻是i的区间,比较这些区间的初始时刻x对应的max[x-1]+C[x,i]与当前max[i]的大小,如果max[x-1]+C[x,i]更大,就替换max[i]。可能对于很多选手来说,拿出状态转移方程并不难,问题在于怎么存每个区间。如果直接开2维数组,c:array[1..maxT,1..maxT] of longint,空间复杂度是T^2,可以过60%的数据。我们应该如何存区间呢?

我们开一个一维数组,g:array[1..maxn*maxm] of record x,y,c,l:longint; end,空间约4M,其中x,y表示对应区间的初始时刻和结束时刻,c表示快乐程度,l表示上一个和这个区间y值相同的区间所对应的位置。再开一个一维数组,l:array[1..maxT] of longintl[y]表示以y为结束时刻的最后一个区间所对应的位置。这样,我们就可以很轻松的找到以某个值y为结束时刻的区间了。DP的时间复杂度降到 O(maxn*maxm+T)。但事实上由于读入大数据文件比较耗时,所以标程过最后一个数据也要约0.4秒,因此把时限定为1.5s(我们同样可以用x做为标准)

此题主要考察动态规划和链表,拿60分相对容易,拿满分比较困难。

数据范围和类型:

数据 1 2 3 4 5 6 7 8 9 10
N值 3 4 4 65 78 98 400 450 498 500
M值 4 4 5 62 92 98 384 462 498 500
T值 10 16 19 1234 1674 98 25*10^4 35*10^4 45*10^4 5*10^5
平均分 3.81 2.90 3.24 2.33 2.33 2.84 1.19 1.19 1.14 1.08
类型 手工 随机 特殊 随机 随机 特殊 随机 随机 随机 随机

【个人报告】

赛场上前几题耗时太多没来得及打这题。妥妥的DP阿……

但确实没想那么多……

看了题解才知道确实有坑。

抽象的模型大概就是m条带权线段求不相交区间最大权值和……几个几个人是考你读入的……

果断读进来按终点排序,一条一条来DP。

 

 

[Dr.Lib]Note:Math – 不定方程

Via Ivy-Endhttp://www.ivy-end.com/archives/1010
关于这个算法,主要是参考NOIP2012 Day2 T1。即这里所讲的是求解这样一个线性模方程:\[ax\equiv 1\mod{p}\]的最小正整数解。

去年我是暴搜做的(PS+1),当时什么都不会。今天在这里介绍两种算法,一种是我国古代数学家秦九韶发明的「大衍求一术,还一种是著名的「扩展欧几里德算法」。

大衍求一术

首先来看一下大衍求一术。这里只介绍它的计算方法,至于证明可以参考扩展欧几里德算法。

例1:求解方程\(23x\equiv 1\mod{97}\)。

解:我们只需要列出下面这张表就可以得到求解\[\begin{matrix}23^{1} & 23^{1} & 3^{17} & 3^{17} & 1^{38}\\ 97^{0} & 5^{4} & 5^{4} & 2^{21} & 2^{21}\end{matrix}\]结果就是38。

接下来我们来理论化的表述一下这个算法的过程:

假设输入\(a,b\)满足\(a>b\)。那么我们用\(a_{n},A_{n}\)分别表示第一行的底数和奇数,\(b_{n},B_{n}\)分别表示第二行的底数和奇数,如果\(a_{i}>b_{i}\),那么\(a_{i+1}=a_{i}\mod{b_{i}},A_{i+1}=A_{i}+B_{i}\cdot \left [ \frac{a_{i}}{b_{i}} \right ],b_{i+1}=b_{i},B_{i+1}=B_{i}\);如果\(a_{i}<b_{i}\)则上面的结论倒过来即可。

算法结束当且仅当\(a_{i}=1\),此时\(A_{i}\)即为所求的最小正整数解。

例2:求解方程\(97x\equiv 1\mod{23}\)。

解:我们只需要列出下面这张表就可以得到求解\[\begin{matrix}97^{1} & 5^{1} & 5^{1} & 2^{5} & 2^{5} & \\ 23^{0} & 23^{0} & 3^{4} & 3^{4} & 1^{9} & 1^{14}\end{matrix}\]结果就是14。

对于这个结果,如果1最先出现在下面一行,则需要再计算一次,而且这次计算必须使得余数是1。

假设输入\(a,b\)满足\(a<b\)。中间的步骤和之前一行,在计算过程中必然存在一个\(i\)使得\(b_{i}=1\),此时我们只需计算\(B_{i+1}\)即可得到结果。其中\(B_{i+1}=A_{i}+B_{i}\cdot \left(a_{i} – 1\right)\)。

扩展欧几里德算法

可能上面的算法对于某些人来说比较晦涩,我们下面来介绍一下扩展欧几里德算法。首先介绍一个定理:

方程\(ax+by=\gcd\left ( a,b \right )\)一定有解。

这样我们的问题就可以转化为求方程\(ax+b\cdot \left ( -y \right )=1\),在这里,我们先求出方程\(ax+b\cdot \left ( -y \right )=\gcd\left(a,b\right)\)的解,然后只要将结果除以\(\gcd\left(a,b\right)\)就行了。

下面来推导一下扩展欧几里德算法。

我们已知\[ax+by=\gcd\left ( a,b \right )\],且\(\gcd\left ( a,b \right )=\gcd\left(b,a\mod b \right )\)。不妨设\[bx{}'+\left ( a\mod b \right )y{}'=\gcd\left ( b,a\mod b \right )\]。此时就有\[bx{}'+\left ( a\mod b \right )y{}'=ax+by\],展开得到\[bx{}'+\left ( a-\left [ \frac{a}{b} \right ]\cdot b \right )y{}’=ax+by\],化简得\[ay{}'+b\left (x{}'-\left [ \frac{a}{b} \right ]\cdot y{}’ \right )=ax+by\]。因此可以得到\[x=y{}',y=x{}'-\left [ \frac{a}{b} \right ]\cdot y{}’\]。

这样我们就可以用递归来实现扩展欧几里德算法了。

欧拉定理

\(a^{phi(n)}=1 \mod {n}\)
令\(x=a^{phi(n) -1}\mod{n}\)有\(ax=1  \mod{n}\)则x即为答案。
只需求出phi(n)就可以了。