# 清北学堂学习总结 day1 数据结构 练习

1.二叉搜索树

STL set直接做就可以了

2.树状数组+差分数列：

codevs 1081 线段树练习 2

1：给区间[a,b]的所有数都增加X

2：询问第i个数是什么？

3

1

2

3

2

1 2 3 2

2 3

5

1<=n<=100000

1<=q<=100000

```#define N 100100
#include<iostream>
#include<cstdio>
using namespace std;
#include<cstring>
int a[N],b[N],n,q,l,r,x,p;
long long  tree[N];
void build_tree(int k,int m)
{
while(k<=n)
{
tree[k]+=m;
k+=((-k)&k);
}
}
long long query(int k)
{
long long ans=0;
while(k)
{
ans+=tree[k];
k-=((-k)&k);
}
return ans;
}
void input()
{
scanf("%d",&n);
a[0]=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
b[i]=a[i]-a[i-1];
build_tree(i,b[i]);
}
}
int main()
{
input();
scanf("%d",&q);
for(int i=0;i<q;++i)
{
scanf("%d",&x);
if(x==1)
{
scanf("%d%d%d",&l,&r,&p);
build_tree(l,p);
build_tree(r+1,-p);
}
else
{
scanf("%d",&p);
cout<<query(p)<<endl;
}
}
return 0;
}```

3.ST表

Balanced Lineup

 Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 43893 Accepted: 20585 Case Time Limit: 2000MS

Description

For the daily milking, Farmer John‘s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

```6 3
1
7
3
4
2
5
1 5
4 6
2 2```

Sample Output

```6
3
0```

```#include<iostream>
#define N 50101
#include<cstdio>
#include<cstring>
using namespace std;
int hige[N],n,q,l,r;
#define K 17
int min_rmq[N][K+1];
int max_rmq[N][K+1];
int ff[(1<<K)+1];
void input()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
scanf("%d",&hige[i]);
}
void pre_chuli()
{
for(int i=1;i<=n;++i)
{
min_rmq[i][0]=hige[i];
max_rmq[i][0]=hige[i];
}
for(int j=1;j<=K;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
min_rmq[i][j]=min(min_rmq[i][j-1],min_rmq[i+(1<<j-1)][j-1]);
max_rmq[i][j]=max(max_rmq[i][j-1],max_rmq[i+(1<<j-1)][j-1]);
}
memset(ff,-1,sizeof(ff));
ff[0]=0;
for(int i=0;i<=K;++i)
ff[1<<i]=i;
for(int i=1;i<=(1<<K);++i)
if(ff[i]==-1)
ff[i]=ff[i-1];
}
int max_query(int l,int r)
{
int t=ff[r-l+1];
return max(max_rmq[l][t],max_rmq[r-(1<<t)+1][t]);
}
int min_query(int l,int r)
{
int t=ff[r-l+1];
return min(min_rmq[l][t],min_rmq[r-(1<<t)+1][t]);
}
int main()
{
input();
pre_chuli();
for(int i=1;i<=q;++i)
{
scanf("%d%d",&l,&r);
printf("%d\n",max_query(l,r)-min_query(l,r));
}
return 0;
}```

4.trie树

# cojs 173. 词链

★☆   输入文件：`link.in`   输出文件：`link.out`   简单对比

【问题描述】

int
integer

integer
intern

【输入格式】

【输出格式】

【输入输出样例】

5
i
int
integer
intern
internet

4

【数据范围】

50% 的数据， n<=1000

100% 的数据， n<=10000

```#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define N 10100
int n;
int ans=0;
int topt=0;
#define L 51
struct Trie{
int nxt[26];
int cnt;
}trie[L];
void dfs(int k,int pre_ans)
{/*dfs统计单词数目*/
for(int i=0;i<26;++i)
if(trie[k].nxt[i])
{
dfs(trie[k].nxt[i],pre_ans+trie[k].cnt);
}
ans=max(pre_ans+trie[k].cnt,ans);
}
void build(char *str)
{
int now=0;
while(*str)
{
if(!trie[now].nxt[*str-‘a‘])
trie[now].nxt[*str-‘a‘]=++topt;
now=trie[now].nxt[*str-‘a‘];
str++;
}
trie[now].cnt++;/*建树*/
}
void input()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
char s[L];
scanf("%s",s);
build(s);
}
dfs(0,0);
printf("%d\n",ans);
}
int main()
{
input();
//    fclose(stdin);fclose(stdout);
return 0;
}```

5.并查集--加权并查集

POJ   1182 食物链

 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 60173 Accepted: 17627

Description

1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。

Input

Output

Sample Input

```100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
```

Sample Output

`3`

Source

noi 01

```  1 /*Part I  - 权值(relation)的确定。
2     我们根据题意，森林中有3种动物。A吃B，B吃C，C吃A。
3     我们还要使用并查集，那么，我们就以动物之间的关系来作为并查集每个节点的
4     权值。
5     注意，我们不知道所给的动物（题目说了，输入只给编号）所属的种类。
6     所以，我们可以用动物之间“相对”的关系来确定一个并查集。
7     0 - 这个节点与它的父节点是同类
8     1 - 这个节点被它的父节点吃
9     2 - 这个节点吃它的父节点。
10
11     注意，这个0,1,2所代表的意义不是随便制定的，我们看题目中的要求。
12     说话的时候，第一个数字（下文中，设为d）指定了后面两种动物的关系：
13     1 - X与Y同类
14     2 - X吃Y
15
16     我们注意到，当 d = 1的时候，( d - 1 ) = 0，也就是我们制定的意义
17                 当 d = 2的时候，( d - 1 ) = 1，代表Y被X吃，也是我们指定的意义。
18     所以，这个0,1,2不是随便选的
19
20
21     Part II - 路径压缩，以及节点间关系确定
22     确定了权值之后，我们要确定有关的操作。
23     我们把所有的动物全初始化。
24     struct Animal
25     {
26         int num; //该节点（node）的编号
27         int parent; //该node的父亲
28         int relation; //该node与父节点的关系，0同类，1被父节点吃，2吃父节点
29     }; Animal ani[50010];
30         初始化为
31         For i = 0 to N do
32             ani[i].num = i;
33             ani[i].parent = i;
34             ani[i].relation = 0 ; //自己和自己是同类
35         End For
36
37         (1)路径压缩时的节点算法
38         我们设A,B,C动物集合如下：（为了以后便于举例）
39         A = { 1 , 2 , 3 ,4 ,5 }
40         B = { 6 , 7 , 8 ,9 ,10}
41         C = { 11, 12, 13,14,15}
42         假如我们已经有了一个集合，分别有3个元素
43         SET1 = {1,2}，我们规定集合中第一个元素为并查集的“代表”
44         假如现在有语句：
45         2 2 6
46         这是一句真话
47         2是6的父亲
48          ani[6].parent = 2;
49          ani[6].relation = 1;
50         那么，6和1的关系如何呢？
51          ani[2].parent = 1;
52          ani[2].relation = 0;
53         我们可以发现6与2的关系是 1.
54         通过穷举我们可以发现
55         ani[now].parent = ani[ani[now].parent].parent;
56         ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 3;
57         这个路径压缩算法是正确的
58         关于这个路径压缩算法，还有一点需要注意的地方，我们一会再谈
59         注意，根据当前节点的relation和当前节点父节点的relation推出
60         当前节点与其父节点的父节点的relation这个公式十分重要！！
61         它推不出来下面都理解不了！！自己用穷举法推一下：
62         好吧，为了方便伸手党，我给出穷举过程
63                 i      j
64         爷爷  父亲  儿子  儿子与爷爷
65                0      0       (i + j)%3 = 0
66                0      1       (i + j)%3 = 1
67                0      2       (i + j)%3 = 2
68                1      0       (i + j)%3 = 1
69                1      1       (i + j)%3 = 2
70                1      2       (i + j)%3 = 0
71                2      0       (i + j)%3 = 2
72                2      1       (i + j)%3 = 0
73                2      2       (i + j)%3 = 1
74         嗯，这样可以看到，( 儿子relation + 父亲relation ) % 3 = 儿子对爷爷的relation
75         这就是路径压缩的节点算法
76         (2) 集合间关系的确定
77         在初始化的时候，我们看到，每个集合都是一个元素，就是他本身。
78         这时候，每个集合都是自洽的（集合中每个元素都不违反题目的规定）
79         注意，我们使用并查集的目的就是尽量的把路径压缩，使之高度尽量矮
80         假设我们已经有一个集合
81         set1 = {1,2,7,10}
82         set2 = {11,4,8,13},每个编号所属的物种见上文
83         set3 = {12,5,4,9}
84         现在有一句话
85         2 13 2
86         这是一句真话,X = 13,Y = 2
87         我们要把这两个集合合并成一个集合。
88         直接
89         int a = findParent(ani[X]);
90         int b = findParent(ani[Y]);
91         ani[b].parent = a;
92         就是把Y所在集合的根节点的父亲设置成X所在集合的根节点。
93         但是，但是！！！！
94         Y所在集合的根结点与X所在集合的根节点的关系！！！要怎么确定呢？
95         我们设X,Y集合都是路径压缩过的，高度只有2层
96         我们先给出计算的公式
97         ani[b].relation = ( 3 - ani[Y].relation + ( d - 1 ) + ani[X].relation) % 3;
98         这个公式，是分三部分，这么推出来的
99         第一部分，好理解的一部分：
100         ( d - 1 ) :这是X和Y之间的relation，X是Y的父节点时，Y的relation就是这个
101         3 - ani[Y].relation = 根据Y与根节点的关系，逆推根节点与Y的关系
102         这部分也是穷举法推出来的，我们举例：
103         j
104         子         父相对于子的relation（即假如子是父的父节点，那么父的relation应该是什么，因为父现在是根节点，所以父.relation = 0，我们只能根据父的子节点反推子跟父节点的关系）
105          0             ( 3 - 0 ) % 3 = 0
106          1（父吃子）   ( 3 - 1 ) % 3 = 2 //父吃子
107          2（子吃父)    ( 3 - 2 ) % 3 = 1 //子吃父，一样的哦亲
108         ——————————————————————————————————————————————————————
109         我们的过程是这样的：
110         把ani[Y]，先连接到ani[X]上，再把ani[Y]的根节点移动到ani[X]上，最后，把ani[Y]的根节点移动到ani[X]的根节点上，这样算relation的
111         还记得么，如果我们有一个集合，压缩路径的时候父子关系是这么确定的
112         ani[爷爷].relation = ( ani[父亲].relation + ani[儿子].relation ) % 3
113         我们已知道,( d - 1 )就是X与Y的relation了
114         而 (3 - ani[Y].relation)就是 以Y为根节点时，他的父亲的relation
115         那么
116         我们假设把Y接到X上，也就说，现在X是Y的父亲，Y原来的根节点现在是Y的儿子
117           Y的relation   +     ani[Y]根节点相对于ani[Y]的relation
118         ( ( d - 1 )         +    ( 3 - ani[Y].relation) ) % 3
119         就是ani[Y]的父亲节点与ani[X]的relation了！
120
121         那么，不难得到，ani[Y]的根节点与ani[X]根节点的关系是：
122         ( ( d - 1 ) + ( 3 - ani[Y].relation) + ani[X].relation ) % 3 ->应用了同余定理
123         注意，这个当所有集合都是初始化状态的时候也适用哦
124         还是以最开头我们给的三个集合（分别代表三个物种）为例
125         2 1 6
126         带入公式
127         ani[6].relation = ( ( 2 - 1 ) + ( 3 - 0 ) + 0 ) % 3 = 1
128         也就是，6被1吃
129     Part III - 算法正确性的证明
130         首先，两个自洽的集合，合并以后仍然是自洽的
131         这个不难想吧，数学上有个什么对称性定理跟他很像的。
132         如果理解不了，就这么想！！
133         当set1和set2合并之后，set2的根节点得到了自己关于set1根节点的
134         正确relation值，变成了set1根节点的儿子，那么
135         set2的所有儿子只要用
136         ( ani[X].relation + ani[Y].relation ) % 3就能得到自己正确的relation值了
137         所以说，针对不在同一集合的两个元素的话，除非违背了（2）和（3），否则永远是真的
138         （无论这句话说的是什么，我们都可以根据所给X,Y推出两个子节点之间应有的关系，这个关系一确定，所有儿子的关系都可以确定）
139
140         其实所有的不同集合到最后都会被合并成一个集合的。
141         我们只要在一个集合中找那些假话就可以了。
142         首先，如何判断
143         1 X Y是不是假话。//此时 d = 1
144         if ( X 和 Y 不在同一集合)
145             Union(x,y,xroot,yroot,d)
146         else
147             if x.relation != y.relation  ->假话
148         其次，如何判断
149         2 X Y是不是假话 //此时d = 2
150         if ( X 和 Y 不在同一集合）
151             Union(x,y,xroot,yroot,d)
152         else
153             (ani[y].relation + 3 - ani[x].relation ) % 3 != 1 ->假话
154         这个公式是这么来的：
155         3 - ani[x].relation得到了根节点关于x的relation
156         ani[y] + 3 - ani[x].relation得到了y关于x的relation
157         所以，只要y关于x的relation不是1，就是y不被x吃的话，这句话肯定是假话！
158
159         (2)路径压缩要特别注意的一点（错在这里，要检讨自己）
160             路径压缩的时候，记得要
161             先findParent，再给当前节点的relation赋值。
162             否则有可能因为当前节点的父节点的relation不正确而导致错的稀里哗啦。
163             例子：
164             set1 = {1,2,7,10}
165             set2 = {3,4,8,11}
166             set3 = {12,5,14,9}
167             Union(1,3,1,3,1)
168             Union(3,12,3,12,2)
169             1 5 1
170             算5的relation
171             如果不先更新parent的relation，算出来应该是
172             ( 3 - 0 + 0 + 1 ) % 3 = 1，5被1吃，显然不对
173             这里面，+ 0的那个0是指根节点 12 的relation（未更新，这里的0是指12与11的relation）
174             如果更新完了的话，应该是
175             ( 3 - 0 + 2 + 1 ) % 3 = 0 ,5与1是同一物种，对了
176             这里面的 2 是更新节点12的relation（12与1的relation）*/
177 #define N 50100
178 int father[N];
179 #include<iostream>
180 #include<cstdio>
181 int val[N];
182 #include<cstring>
183 using namespace std;
184 int n,k;
185 int d,x,y;
186 int ans=0;
187 int find(int k)
188 {
189     if(k!=father[k])
190     {
191         int tmp=father[k];
192         father[k]=find(father[k]);
193         val[k]=(val[k]+val[tmp])%3;/*路径压缩的过程，利用儿子与父亲，父亲与爷爷的关系，求出儿子与爷爷的关系*/
194     }
195     return father[k];/*注意这里是return  father[k]，而不是k，因为这是路径压缩，father[k]都指到了根节点，而k没有*/
196 }
197 int main()
198 {
199     scanf("%d%d",&n,&k);
200     for(int i=1;i<=n;++i)
201     father[i]=i,val[i]=0;/*初始化并查集，val表示儿子与父亲的关系*/
202     for(int i=0;i<k;++i)
203     {
204         scanf("%d%d%d",&d,&x,&y);
205         if(x>n||y>n)
206         {
207             ans++;
208             continue;
209         }
210         if(d==1)
211         {
212             if(find(x)==find(y))
213             {
214                 if(val[x]!=val[y])
215                 ans++;
216             }
217             else
218             {
219                 val[father[x]]=(val[y]-val[x]+3)%3;
220                 father[father[x]]=father[y];
221              }
222         }
223         else
224         {
225             if(x==y)
226             {
227                 ans++;
228                 continue;
229             }
230             if(find(x)==find(y))
231             {
232                 if(val[x]!=(val[y]+1)%3)/*y的边指向x，x吃y，y离着根节点近*/
233                 ans++;
234             }
235             else{
236
237             //    father[father[x]]=father[y];/*放在上面是不对的，当初值的时候father[x]=x,father[y]=y,当把这个语句放到上面的时候，下面的语句就成了val[y]的赋值了，而不是val‘[x]的赋值，因为这个时候val[y]应该是0*/
238                 val[father[x]]=(val[y]+1-val[x]+3)%3;
239                father[father[x]]=father[y];
240             }
241         }
242     }
243     cout<<ans<<endl;
244     return 0;
245  } ```

6.线段树

### 3304 水果姐逛水果街Ⅰ

10
2 8 15 1 10 5 19 19 3 5
4
6 6
2 8
2 2
6 3

0
18
0
14

0<=苹果的价格<=10^8

0<n,m<=200000

#### 划分型DP动态规划区间型DP线段树树结构

```#include<iostream>
using namespace std;
#include<cstdio>
#define lch 2*k
#define rch 2*k+1
#define N 200001
#define INF 1<<30
struct node{
int min_,max_,max_val1,max_val2;
node(){min_=INF;max_=max_val1=max_val2=0;}
}tree[N*2+100];
int t=0;
int n,a[N],m;
void input()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
}
void update(int k)
{
tree[k].min_=min(tree[lch].min_,tree[rch].min_);
tree[k].max_=max(tree[lch].max_,tree[rch].max_);
tree[k].max_val1=max(tree[lch].max_val1,max(tree[rch].max_val1,tree[rch].max_-tree[lch].min_));
tree[k].max_val2=max(tree[lch].max_val2,max(tree[rch].max_val2,tree[lch].max_-tree[rch].min_));
}
void build_tree(int k,int l,int r)
{
if(l==r-1)
{
tree[k].max_=a[l];
tree[k].max_val1=tree[k].max_val2=0;
tree[k].min_=a[l];
return ;
}
int mid=(l+r)/2;
build_tree(lch,l,mid);
build_tree(rch,mid,r);
update(k);
}
node query(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return tree[k];
}
node ans;
int mid=(l+r)/2;
node b1;
if(x<mid)
{
ans=query(lch,l,mid,x,y);
}
if(y>mid)
{
b1=query(rch,mid,r,x,y);
ans.max_=max(ans.max_,b1.max_);
ans.min_=min(ans.min_,b1.min_);
ans.max_val1=max(ans.max_val1,max(b1.max_val1,b1.max_-ans.min_));
}
return ans;
}
node ex_query(int k,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return tree[k];
}
node ans;
int mid=(l+r)/2;
node b1;
if(x<mid)
{
ans=query(lch,l,mid,x,y);
}
if(y>mid)
{
b1=query(rch,mid,r,x,y);
ans.max_=max(ans.max_,b1.max_);
ans.min_=min(ans.min_,b1.min_);
ans.max_val2=max(ans.max_val2,max(b1.max_val2,ans.max_-b1.min_));
}
return ans;
}
int main()
{
input();
build_tree(1,1,n+1);
scanf("%d",&m);
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);

node ans;
if(x<=y)
{
ans=query(1,1,n+1,x,y+1);
printf("%d\n",ans.max_val1);
}
else{
ans=ex_query(1,1,n+1,y,x+1);
printf("%d\n",ans.max_val2);
}

}
return 0;
}```

7.

## 洛谷P1080 [NOIP2012提高组D1T2]国王游戏 [2017年5月计划 清北学堂51精英班Day1]

P1080 国王游戏 题目描述 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏.首先,他让每个大臣在左.右 手上面分别写下一个整数,国王自己也在左.右手上各写一个整数.然后,让这 n 位大臣排 成一排,国王站在队伍的最前面.排好队后,所有的大臣都会获得国王奖赏的若干金币,每 位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数,然后向下取整得到的结果. 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序, 使得获得奖赏最多的大

## P2327 [SCOI2005]扫雷 [2017年5月计划 清北学堂51精英班Day1]

P2327 [SCOI2005]扫雷 题目描述 输入输出格式 输入格式: 第一行为N,第二行有N个数,依次为第二列的格子中的数.(1<= N <= 10000) 输出格式: 一个数,即第一列中雷的摆放方案数. 输入输出样例 输入样例#1: 2 1 1 输出样例#1: 2 其实还是扫雷玩的少..知道思路之后很快 只需枚举前两个各自的情况,后面的各自便能够计算出来 注意几个细节(在代码里面) #include <iostream> #include <cstdio> #in

## 清北学堂2017NOIP冬令营入学测试

P4744 A's problem(a) 时间: 1000ms / 空间: 655360KiB / Java类名: Main 背景 冬令营入学测试题,每三天结算一次成绩.参与享优惠 描述 这是一道有背景的题目,小A也是一个有故事的人.但可惜的是这里纸张太小,小A无法把故事详细地说给大家听.可能小A自己也讲不清楚自己的故事,因为如果讲清了,也就没有这道题目了-- 小A的问题是这个样子,它找到了n份不同的工作,第i份工作每个月有ai的工资,每份工作需要小A每天工作8小时,一周工作7天.小A想知道性价

## 清北学堂 逃亡的准备

逃亡的准备 (hallows.pas/c/cpp)   [问题描述] 在<Harry Potter and the Deathly Hallows>中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量.体积.价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你. [输入文件](hallows.in) (1)第一行有2个整数,物品种数n和背包装

## 清北学堂 站军姿

/*2bc*cosA=b^2+c^2-a^2 模拟计算 50分*/ #include<iostream> #include<cstdio> #include<cmath> using namespace std; const double t=3.1415926535898; int n; double a,b,c,x,y,z,x2,y2,z2,s,k,m,w,p; int main () { freopen ("standing.in","