链表小结

概述

说起来,链表是少数几个在正式学习之前就有点概念的数据结构。
记得很久很久之前有一题,貌似是要插入什么,当时是用线段树(?)解决了问题,但是想,为什么数组之间插入元素这么不方便呢?
然后就想到可以自己做个结构体用指针接起来,这样插入就可以$O(1)$实现了!
后来知道这就是链表。
再后来知道,这样插入也是非常不支持的,因为找到插入的位置也是$O(n)$的。
又后来,学会了数组模拟链表,可以快速找到插入位置。
然后就是一个非常兹磁的东西了!其实很多时候都是用于优化,程序的主算法都不会改变的。
下面是一些例题:

例题

[BZOJ 1098] 办公楼biu

[Description]

求一个n点m边的无向图补图的连通块数。

[Hint]

$n≤10^5,m≤2·10^6$

[Solution]

直接建补图肯定是爆炸的。
考虑某个点,不与它相邻的点在补图中肯定跟它位于同一个连通块。
与这些点不相连的所有点肯定也与这些点位于同一个连通块。
这样,可以一次把一个连通块里的所有点找出来。
删除后找下一个连通块。
提高效率的办法就是用链表。
永远都只考虑链表内的元素。
因为每条边和每个点都只会被访问一次,总复杂度为$O(n+m)$.

[Code]

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

const int maxn=1e5+10;
const int maxm=2e6;

int to[2*maxm],nxt[2*maxm],cur[maxn],cnt;
void insert(int x,int y){
to[cnt]=x,nxt[cnt]=cur[y],cur[y]=cnt++;
to[cnt]=y,nxt[cnt]=cur[x],cur[x]=cnt++;
}

bool flag[maxn];
int pre[maxn],off[maxn];

queue<int> q;
int res[maxn];
void work(int n){
int sum=0;
while(off[0]<=n){
int s=off[0]; q.push(s);
off[pre[s]]=off[s],pre[off[s]]=pre[s],res[sum]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=cur[u];i>=0;i=nxt[i])
flag[to[i]]=true;
for(int i=off[0];i<=n;i=off[i])
if(!flag[i]){
off[pre[i]]=off[i],pre[off[i]]=pre[i],flag[i]=false;
res[sum]++;
q.push(i);
}
else flag[i]=false;
}
sum++;
}
printf("%d\n",sum);
sort(res,res+sum);
for(int i=0;i<sum;i++) printf("%d ",res[i]);
}

int main(){
memset(cur,-1,sizeof(cur));
int n=read(),m=read();
for(int i=0;i<m;i++) insert(read(),read());
for(int i=0;i<=n+1;i++) pre[i]=i-1,off[i]=i+1;
work(n);
return 0;
}

[BZOJ 1150] CTSC2007 数据备份

[Description]

这里写图片描述

[Hint]

$n≤10^5,1≤k≤n/2,s≤10^9$

[Solution]

易得所有电缆一定是相邻的。
现在要选择k条不相邻的电缆使得距离最小。
再次使用链表,每次选择一个最小的元素加入答案,删除两边元素,并在原位置生成一个两边元素和减去自身的新元素。
每次选取元素个数-1,进行k次选取。
这样做的意义是,既保证不选择相邻元素,当需要选择相邻元素时又可以做到。
然后就可以愉快地AC辣~

[Code]

数组模拟链表。

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
45
46
47
48
49
50
51
52
#include<queue>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;

inline int read(){
int x=0; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}

typedef long long ll;
const ll inf=~0ull>>2;
const int maxn=2e5;
ll c[maxn+10];
bool exist[maxn+10];
int pre[maxn],nxt[maxn];

struct data{
ll x; int pos;
bool operator < (const data d) const {
return x>d.x;
}
};
priority_queue<data> heap;

int main(){
int n=read(),k=read(); ll ans=0;
fill(exist,exist+n+1,true);
for(int i=0;i<n;i++) c[i]=read();
for(int i=n-1;i;i--) c[i]-=c[i-1];
c[0]=c[n]=inf;
for(int i=0;i<=n;i++) pre[i]=i-1,nxt[i]=i+1;
for(int i=1;i<n;i++) heap.push((data){c[i],i});
while(k--){
data d=heap.top(); heap.pop();
int p=d.pos;
if(exist[p]==false){ k++; continue; }
ans+=d.x;
c[p]=d.x=c[pre[p]]+c[nxt[p]]-c[p];
int l=pre[pre[p]]>=0?pre[pre[p]]:pre[p];
int r=nxt[nxt[p]]<=n?nxt[nxt[p]]:nxt[p];
if(nxt[l]!=p) exist[nxt[l]]=false;
if(pre[r]!=p) exist[pre[r]]=false;
nxt[l]=p,pre[p]=l; nxt[p]=r,pre[r]=p;
heap.push(d);
}
printf("%lld",ans);
return 0;
}

[BZOJ 2151] 种树

[Description]

一个长度为$n(n≤2\cdot 10^5)$的环形序列,每个位置不同的权值,要求选出m个不相邻的元素使得全职最大。

[Solution]

大致同数据备份,只是链表是环状的。

[BZOJ 2288] 生日礼物

[Description]

在长度为n的整数序列里选出不超过m段连续的子序列,使得选出的元素和最大。

[Hint]

$n,m≤10^5$

[Solution]

我们将连续的正整数和负整数分别合并,并不影响答案。
要是合并后正整数个数小于m,直接得到答案。
我们最终的结果是要得到m个正整数。
用堆每次选出绝对值最小的一个元素,将它与旁边两个数合并,因为它绝对值最小,得到的新数一定跟它符号相反。
这样做的意义是,若这个数为正整数,无论从左边或右边的区间选中它总和一定会减少;若这个数为负整数,左右区间合并之后可以达到更优。
合并中最左最右的负整数要抛弃。
这样合并知道只剩m个正整数为止,就是问题的答案。
进行操作最适合的数据结构为链表。

[Code]

用结构体实现链表,查找非常慢。(建议不要看)

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int abs(int x){ return x<0?-x:x; }

const int maxn=1e5;
int a[maxn],n,m;

int s[maxn],cnt;
bool cmp(const int x,const int y){ return y<x; }
int count(){
sort(s,s+cnt,cmp);
int res=0;
for(int i=0;i<m;i++)
if(s[i]>0) res+=s[i];
else break;
return res;
}

bool being[maxn];
struct data{
int x,no;
data(int a,int b){ x=a,no=b; }
bool operator < (const data d) const {
return x>d.x;
}
};
priority_queue<data> q;

struct Chain{
int x,no;
Chain*nxt;
Chain(int a,int b){ x=a,no=b; nxt=NULL; }
Chain*find(int k){
if(this->nxt->no==k) return this;
return nxt->find(k);
}
};
void insert(int a,int b,Chain*&c){
c->nxt=new Chain(a,b); c=c->nxt;
}

void merge(){
int num=cnt,k=-m; cnt=0;
for(int i=0,now=1;i<num;i=now++){
while(now<num && (long long)s[i]*s[now]>=0) s[i]+=s[now++];
s[cnt++]=s[i];
}
Chain*head=0,*tail=NULL;
for(int i=0,num=0;i<cnt;i++){
if(!i && s[i]<0) continue;
if(i==cnt-1 && s[i]<0) continue;
q.push((data){abs(s[i]),num});
if(!num) head=tail=new Chain(s[i],num++);
else insert(s[i],num++,tail);
if(s[i]>0) k++;
}
for(int i=0;i<k;i++){
data d=q.top(); q.pop();
if(being[d.no]){ i--; continue; }
Chain*c;
if(head && head->no==d.no){
c=head;
being[c->nxt->no]=true,c->x+=c->nxt->x,c->nxt=c->nxt->nxt;
if(c->x<0){ being[c->no]=true; head=head->nxt; continue; }
}
else{
c=head->find(d.no);
being[c->no]=true,c->no=c->nxt->no,c->x+=c->nxt->x,c->nxt=c->nxt->nxt;
if(c->nxt) being[c->nxt->no]=true,c->x+=c->nxt->x,c->nxt=c->nxt->nxt;
if(c->x<0 && !c->nxt){ being[c->no]=true; continue; }
}
q.push((data){abs(c->x),c->no});
}
cnt=0;
while(head){
if(head->x>0) s[cnt++]=head->x;
head=head->nxt;
}
}

int main(){
scanf("%d%d",&n,&m);
if(!m){ putchar('0'); return 0; }
for(int i=0;i<n;i++) scanf("%d",&a[i]);
int sum=0;
for(int i=0,now=0;i<n;i++){
now+=a[i];
if(i==n-1 || a[i]*a[i+1]<=0){
if(now>0) sum++;
s[cnt++]=now,now=0;
}
}
if(sum>m) merge();
printf("%d",count());
return 0;
}