概述
说起来，链表是少数几个在正式学习之前就有点概念的数据结构。
记得很久很久之前有一题，貌似是要插入什么，当时是用线段树(?)解决了问题，但是想，为什么数组之间插入元素这么不方便呢？
然后就想到可以自己做个结构体用指针接起来，这样插入就可以O(1)实现了！
后来知道这就是链表。
再后来知道，这样插入也是非常不支持的，因为找到插入的位置也是O(n)的。
又后来，学会了数组模拟链表，可以快速找到插入位置。
然后就是一个非常兹磁的东西了！其实很多时候都是用于优化，程序的主算法都不会改变的。
下面是一些例题：
例题
[BZOJ 1098] 办公楼biu
[Description]
求一个n点m边的无向图补图的连通块数。
[Hint]
n≤105,m≤2⋅106
[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≤105,1≤k≤n/2,s≤109
[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⋅105)的环形序列，每个位置不同的权值，要求选出m个不相邻的元素使得权值最大。
[Solution]
大致同数据备份，只是链表是环状的。
[BZOJ 2288] 生日礼物
[Description]
在长度为n的整数序列里选出不超过m段连续的子序列，使得选出的元素和最大。
[Hint]
n,m≤105
[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;
}
|
