新手村-数组*

跟数组有关的题目基本上都要用到循环,所以请先完成1-3。

[洛谷日报#86]NOIP选手必知的编程技巧

一个动态更新的洛谷综合题单

P1046 陶陶摘苹果 过滤

题目描述

陶陶家的院子里有一棵苹果树,每到秋天树上就会结出10个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。

现在已知10个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。

说明

NOIP2005普及组第一题

Code $O(n)$

dalao们的题解真是。。无言以对。望西楼。月如。。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main(){
int apple[10], hand;
for(int i = 0; i < 10; ++i)
cin>>apple[i];
cin>>hand;

int ans = 0;
for(int i = 0; i < 10; ++i)
ans += (hand + 30 >= apple[i]);
cout<<ans;
}

*P1047 校门外的树 单调栈、线段树

题目描述

某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,…,L,都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。

Code $O(MlogM)$

Force $O(LMC)$

模拟。

L:马路长度。M:区间数量。C:区间平均长度。(如果数据比较饱满,可以当作$O(n^3)$理解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define Max 105
#define Lax 10005
int main(){
int L, M;
int a[Max][2];
cin>>L>>M;
for(int i = 0; i < M; ++i)
cin>>a[i][0]>>a[i][1];

bool result[Lax]={0}; //对每颗树设置灯
for(int i = 0; i < M; ++i)
for(int j = a[i][0]; j <= a[i][1]; ++j)
result[j] = 1;

int Result = 0;
for(int i = 0; i <= L; ++i)
Result += !result[i]; //反转求和
cout<<Result;
}

单调栈 $O(MlogM)$

我们先给M个区间按照所有端点的先后排个序,需要$O(MlogM)​$。

从最左边开始遍历,则每一个区间都有一个诞生时间消亡时间

一个好玩的现象是:

1548266549452

我们可能碰到以上两种区间形态,但是它们在这道题的影响是等效的!这不是括号匹配问题么。。

我们只须维护一个栈(存储[):(我把单调栈形象地叫做栈灯

  • 当栈为空时,树存在,做记录【灯亮,通行】
  • 当栈不为空,树被砍了,跳过【灯灭,阻塞】
    • 遇到[,压入栈
    • 遇到],弹出一个[

然后就可以愉快地单调栈辣~

当然,这可能是广义的单调栈。。2333

事实上,只需要维护[的数量就行了,用一个int size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define Max 105 * 2

struct Endpoint{
int site; //where is this comma
int dire; //direction: 1, left comma [ ; -1, right comma ]
};

bool cmp(Endpoint a, Endpoint b){
return a.site < b.site;
}

int main(){
int L, M;
Endpoint p[Max * 2];
cin>>L>>M;
for(int i = 0; i < M*2; i += 2){ //every step for 2 paired elements
cin>> p[i].site >> p[i + 1].site;
p[i].dire = 1; // 1, left comma
p[i+1].dire = -1; //-1, right comma
}

sort(p, p + M*2, cmp); //sort by site, O(MlogM)

int ans = 0;
int size = 0; //initialize stack size to 0
int bias = -1; //bias for caculating, imagine there is a right comma ] at site:-1
p[M*2].site = L + 1; p[M*2].dire = 1; //imagine there is a left comma [ at site:L+1
for(int i = 0; i <= M*2; i++){ //O(M)
if(!size){ //stack is empty
ans += p[i].site - bias - 1;
}
size += p[i].dire; //renew stack size
bias = p[i].site; //renew bias
}

cout<<ans;
}

感觉栈这种存储结构就像人脑的深层记忆一样,适合于长期的记忆以及高频浅层思考/操作

相对而言,队列则适合短期的记忆以及深度思考。

单调队列=单调栈+队列。由于增加了头部通道,单调队列的记忆能力比较灵活,并且可以同时进行深层、浅层思考。

线段树

一步一步理解线段树

以后有空再学orz

1
2


P1427 小鱼的数字游戏 栈、指针反转

题目描述

小鱼最近被要求参加一个数字游戏,要求它把看到的一串数字(长度不一定,以0结束,最多不超过100个,数字不超过2^32-1),记住了然后反着念出来(表示结束的数字0就不要念出来了)。这对小鱼的那点记忆力来说实在是太难了,你也不想想小鱼的整个脑袋才多大,其中一部分还是好吃的肉!所以请你帮小鱼编程解决这个问题。

Code $O(n)$

滑稽题解

作者: ASZIIIS
更新时间: 2018-10-29 21:47

在Ta的博客查看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main(){
stack<int> a;
int tmp;
while(cin>>tmp){
if(tmp == 0) break;
a.push(tmp);
}
while(!a.empty()){
printf("%d ", a.top()); a.pop();
}
}

向量反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

void reverse(vector<int> &a){
int i = 0, j = a.size() - 1;
while( i < j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++; j--;
}
}

int main(){
vector<int> a;
int tmp;
while(cin>>tmp){
if(tmp == 0) break;
a.push_back(tmp);
}
int len = a.size();

reverse(a);

for(int i = 0; i < len; ++i){
printf("%d ", a[i]);
}
}

指针反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main(){
vector<int> a;
int tmp;
while(cin>>tmp){
if(tmp == 0) break;
a.push_back(tmp);
}
int len = a.size();

for(int i = len - 1; i >= 0; --i){
printf("%d ", a[i]);
}
}

*P1428 小鱼比可爱 归并排序、树状数组

题目描述

人比人,气死人;鱼比鱼,难死鱼。小鱼最近参加了一个“比可爱”比赛,比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排,头都朝向左边,然后每只鱼会得到一个整数数值,表示这只鱼的可爱程度,很显然整数越大,表示这只鱼越可爱,而且任意两只鱼的可爱程度可能一样。由于所有的鱼头都朝向左边,所以每只鱼只能看见在它左边的鱼的可爱程度,它们心里都在计算,在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

Code $O(nlogn)$

本题就是求逆序对。是一个排序问题,复杂度下界显然是$O(nlogn)​$。

Force $O(n^2)$

对每条鱼分别统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int main(){
vector<int> a, ans;
int n;
cin >> n;
for(int i = 0; i < n; ++i){
int tmp;
cin >> tmp;
a.push_back(tmp);
}

for(int i = 0; i < n; ++i){
ans.push_back(0);
for(int j = 0; j < i; ++j)
ans[i] += a[i] > a[j];
}

for(int i = 0; i < n; ++i){
cout<<ans[i]<<" \n"[i == n-1];
}
}

归并排序 $O(nlogn)$

1
2


树状数组 $O(nlogn)$

1
2


错误方法: STL自定义 $O(nlogn)$

主要是因为STL的sort不具有局部性。(stable也一样)当swap某两个元素时可能错过两者中间的许多逆序数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

vector<int> ans; //answer
struct fish{
int pos; //position
int cute; //cute
};

bool Cmp(fish &a, fish &b){
cout<<"cmp: "<<a.cute <<" vs. "<<b.cute<<endl;
cout<<" "<<a.pos <<" "<<b.pos<<endl;
if(a.cute > b.cute){
cout<<"----"<<b.cute<<" at:"<<b.pos<<"++!"<<endl;
ans[a.pos] ++;
return 1;
}
return 0;
}

int main(){
vector<fish> Fish;
int n;
cin >> n;
ans.resize(n + 1, 0);

for(int i = 0; i < n; ++i){
int tmp; cin >> tmp;
fish Newfi; Newfi.pos =i, Newfi.cute = tmp; //new fish
Fish.push_back(Newfi);
}

sort(Fish.begin(), Fish.end(), Cmp);

for(int i = 0; i < n; ++i)
cout<<ans[i]<<" \n"[i == n-1];
}

错误方法: 单调栈 $O(n)$

本方法只能求出元素的最大临近单调序列的长度。

但是逆序的统计不需要单调性。因此不可用栈灯。

维护一个单调不减栈。每一个元素记录<位置,可爱值>

  • 新元素更可爱?
    • 存入,更新栈大小
  • 新元素不够可爱?
    • 不断弹出元素,将此刻栈的大小作为元素位置的rank,直到栈对于新元素保序
    • 存入,更新栈大小
  • 没有新元素了?
    • 依次弹出所有元,操作如上,直到栈空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

struct fish{
int pos; //position
int cute; //cute
};

int main(){
stack<fish> a;
int n;
cin >> n;

vector<int> ans; //answer
ans.resize(n + 1, 0);
int rank = -1;
for(int i = 0; i < n; ++i){
int tmp; cin >> tmp;
fish Newfi; Newfi.pos =i, Newfi.cute = tmp; //new fish

if(a.empty() || a.top().cute < Newfi.cute){
a.push(Newfi), rank++; //a reserves the index of each element instead of real value
// cout<<"Push1:"<<tmp<<endl;
}
else{
while(!a.empty() && a.top().cute >= Newfi.cute){
// cout<<"Pop :"<<a.top().cute<<endl;
// cout<<"----> ans["<<a.top().pos<<"] = "<<rank<<endl;
ans[a.top().pos] = rank--; a.pop();
}
a.push(Newfi), rank++;
// cout<<"Push2:"<<tmp<<endl;
}
// cout<<"------------End for "<<i<<"------------"<<endl;
}
while(!a.empty()){
// cout<<"Pop :"<<a.top().cute<<endl;
// cout<<"----> ans["<<a.top().pos<<"] = "<<rank<<endl;
ans[a.top().pos] = rank--; a.pop();
}

for(int i = 0; i < n; ++i)
cout<<ans[i]<<" \n"[i == n-1];
}

P2141 珠心算测验 模拟、集合

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

(本题目为2014NOIP普及T1)

Code $O(n^2)$

Force $O(n^3)\rightarrow O(n)$

模拟模拟。遍历遍历。期望复杂度就是三次方。

  • 如果数据的结构是Fibonacci数列的话,复杂度骤降到$O(n)$。(概率极小)

统计的不是满足==的式子,而是满足==的元素!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
vector<int> Set;
cin>>n;
Set.resize(n, 0);
for(int i = 0; i < n; ++i)
cin>>Set[i];

int ans = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
for(int k = 0; k < n && k!=j; ++k)
if(Set[i] == Set[j] + Set[k]){
ans ++;
goto below; //提前跳出两层循环
}
}
below: ans = ans; //设置一个跳转语句
}

cout<<ans;
return 0;
}

这里有一个细微的BUG就是:求的数字必须是在集合中的,不能重复统计。必须在统计到1次Set[i]后立马进入下一个循环!使用goto语句。

标记 $O(n^2)+O(M+n)$

利用额外的空间$O(M)​$来加快查询。M:输入中的最大数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
vector<int> Set;
cin>>n;
Set.resize(n, 0);
int Max_n = 0;
for(int i = 0; i < n; ++i){
cin>>Set[i];
Max_n = max(Max_n, Set[i]); //Max_n是输入中的最大数字
}

vector<bool> Query; //查询
Query.resize(Max_n*2 + 1, 0); //空间对应Max_n的两倍,这样便不会溢出

int ans = 0;
for(int j = 0; j < n; ++j) //处理Query查询
for(int k = 0; k < n && k!=j; ++k)
Query[Set[j] + Set[k]] = 1;
for(int i = 0; i < n; ++i) //求ans
if(Query[Set[i]]) ans++;

cout<<ans;
return 0;
}

STL_set() $O(n^2logn)$

作者: Anfangen
更新时间: 2017-10-31 22:23

在Ta的博客查看

STL中的set容器的一点总结

思路是这样的:在标记法中我们利用额外的空间$O(M)​$来加快查询。但也可以通过额外的集合set的方法,其中插入、查找的复杂度是logn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
vector<int> Set;
set<int> Query; //查询,Query改为STL集合
cin>>n;
Set.resize(n, 0);
for(int i = 0; i < n; ++i)
cin>>Set[i];

int ans = 0;
for(int j = 0; j < n; ++j) //处理Query
for(int k = 0; k < n && k!=j; ++k)
Query.insert(Set[j] + Set[k]); //插入Query

for(int i = 0; i < n; ++i) //求ans
if(Query.find(Set[i]) != Query.end()) ans++;

cout<<ans;
return 0;
}

P1567 统计天数 单调队列

题目背景

统计天数

题目描述

炎热的夏日,KC非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。

经历千辛万苦,他收集了连续N(1<=N<=10^7)天的最高气温数据。

现在,他想知道最高气温一直上升的最长连续天数。

Code

Force 40% $O(n^2)\rightarrow O(n)$

仍然是遍历。复杂度不稳定。

这是第一道暴力过不了的题。。按理说平摊下来应该是$O(n)​$才对orz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main(){
ios::sync_with_stdio(false); // 读入优化
int n;
cin >> n;
vector<int> a; a.resize(n, 0);
for(int i = 0; i < n; ++i)
cin>>a[i];

int ans = 0;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n && j!=i; ++j)
if(a[j - 1] <= a[j]) continue;
else{
ans = max(ans, j - i);
break;
}

cout<<ans;
}

单调队列 $O(n)$

上上个题(P1428可爱鱼)拿来就能用orz。(并不能)

注意天数是连续的!!!

故不使用单调栈,而使用单调队列,每一个新出现的破坏规则的元素都会使一切之前的累计前功尽弃

仍然只需要记录栈/队列的大小

pre = tmp;一句应该放到循环最后,而不是在if里面条件执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int main(){
int n;
cin >> n;
int ans = 0;
int pre = 0; // bias, 0 degree at -1 day
int tmp,count= 1; // days count
for(int i = 0; i < n; ++i){
cin>>tmp;
if(pre <= tmp){
count++;
}
else{
ans = max(ans, count);
count = 1;
}
pre = tmp;
}
cout<<ans;
}
0%