基础数据结构

学习
字数统计: 5.1k   |   阅读时长≈ 23 分钟

基础数据结构

1. 链表与邻接表

1.1. 单链表

最主要的应用是邻接表，用于存储图和树

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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
// 注意90%的题都是用数组来模拟数据结构
const int N=1e5+10;
// head:头结点的下标
// e[i]:表示节点i的值
// ne[i]:表示节点i的下一个地址
// idx:存储当前已经用到了哪个点
int head,e[N],ne[N],idx;

// 初始化
void init() {
	head=-1; // 初始时没有头结点
	idx=0; // 从0号点开始
}

// 链式前向星

// 将x插到头结点
void add_to_head(int x) {
	e[idx]=x,ne[idx]=head,head=idx++;
}

// 将x插入到下标是k的点后面
void add(int k,int x) {
	e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}

// 删除操作
void remove(int k) {
	ne[k]=ne[ne[k]];
}

int main() {
	int m;
	cin>>m;
	init();
	while(m--){
		int k,x;
		char op;
		cin>>op;
		if(op=='H') {
			cin>>x;
			add_to_head(x);
		}
		// 注意,这里是k-1是因为对于题目来说
		// 第k个插入的点的下标是k-1
		else if(op=='D') {
			cin>>k;
			if(!k)
				head=ne[head]; // 如果是头结点的处理方法
			remove(k-1);
		} else {
			cin>>k>>x;
			add(k-1,x);
		}
	}
	for(int i=head;i!=-1;i=ne[i])
		cout<<e[i]<<' ';
	cout<<endl;
	return 0;
}

1.2. 双链表

用于优化单链表问题的时间复杂度

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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 双链表的数组表示形式
const int N=1e5+10;
int m;
// head:头结点
// e[i]:存储点i的值
// l[i]:存储点i的左节点
// r[i]:存储点i的右节点
// idx:存储当前遍历到哪个点了
int head,e[N],l[N],r[N],idx;

// 注意:在该模板中,节点0是最后一个节点,节点1是第一个节点
void init() {
	// 自带两个点0和1,互为左右端点
	l[1]=0;
	r[0]=1;
	idx=2; // 下一个点的编号是2
}

// 双链表插入节点
void insert(int a,int x) {
	e[idx]=x;
	l[idx]=a;
	r[idx]=r[a];
	// 顺序不能反
	l[r[a]]=idx;
	r[a]=idx++;
}

void remove(int a) {
	r[l[a]]=r[a];
	l[r[a]]=l[a];
}

int main() {
	init();
	int m;
	cin>>m;
	while(m--) {
		int k,x;
		string op;
		cin>>op;
		if(op=="L") {
			cin>>x;
			insert(0,x); // 在最左侧插入
		}
		else if(op=="R") {
			cin>>x;
			insert(l[1],x); // 在最右侧插入
		}
		// 因为队头是1,所以第k个插入的元素的下标是
		else if(op=="D") {
			cin>>k;
			remove(k+1);
		}
		// 左插,直接在第k+1个元素的左节点右插即可
		else if(op=="IL") {
			cin>>k>>x;
			insert(l[k+1],x);
		}
		// 右插直接调用insert
		else {
			cin>>k>>x;
			insert(k+1,x);
		}
	}
	// 只要没有遍历到头结点
	for(int i=r[0];i!=1;i=r[i])
		cout<<e[i]<<' ';
	cout<<endl;
	return 0;
}

2. 单调栈

用于一维数组中，找到每个元素左边所有比他小的且离它本身最近的元素的下标

  • 维护一个栈，当遍历到ai的时候，栈中的元素就是 $a_,\ a_2,\ …\ ,a_{i-1}$，如果对于 $[a_1~a_{i-1}]$ 中的元素，假设有 $a_x$ 和$a_y$ ，其中 $x<=y$ 且 $a_x>=a_y$ ，则可以将 $a_x$ 这个元素从栈中删去，即可得到一个单调栈
  • 所以，每次弹出栈顶，只要栈顶是 $>=a_i$ 的，就可以删掉，直到找到一个 $stack[tt]<a_i$
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10;
int n;
int stk[N],tt; // tt:栈顶

int main() {
	// 比赛建议用scanf和printf
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		// 只要栈顶非空且栈顶>=x,则弹出并删除此栈顶
		while(tt&&stk[tt]>=x)
			tt--;
		if(tt)
			cout<<stk[tt]<<' ';
		else
			cout<<-1<<' '; // 找不到呗
		
		// 把数据放进stk
		stk[++tt]=x;
	}
	return 0;
}

3. 单调队列

用于求滑动窗口中的最大值和最小值

  • 只要队列中存在前一个数比后一个数大，那么前一个数一定没有用，这样去掉过后就会形成一个严格单调上升的序列，每一次弹出队头即可。
  • 注意99%的情况下比赛方不开 $O2$ 优化，如果不开 $O2$ 优化的话$STL$ 库就会比数组的模拟慢一些。自我感觉比单调栈、$KMP$ 算法都还要难理解。
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e6+10;
int a[N],q[N]; // q:单调队列
int n,k; // n:元素个数,k:窗口大小

int main() {
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	int hh=0,tt=-1; // 队头队尾初始化为0和-1
	// 处理每一个窗口
	for(int i=0;i<n;i++) {
		// 检查队列的头部是否已经滑出窗口,如果是,则将队列头部向前移动一位
		// hh<=tt:队列不存在,i-k+1>q[hh]:
		// 因为每次只能前进一格,所以不用while循环
		if(hh<=tt && i-k+1>q[hh])
			hh++;
		// 队列非空且队尾元素小于当前元素,将队尾出队
		while(hh<=tt && a[q[tt]]<=a[i])
			tt--;
		// 当前元素入队
		q[+tt]=i;
		// 在窗口满时,输出窗口的最大值
		if(i>=k-1)
			cout<<a[q[hh]]<<' ';
	}
	return 0;
}

4. KMP算法

仔细理解next数组的含义，想加强理解看AcWing数据结构(一)的2:30:50开始

  • $next[i]=j$，表明的是对于子串 $p$ ，$p[1,\ …\ , j]$ 的元素等于 $p[i-j+1,\ …\ , i]$ 的元素，其中 $i$ 是源串 $s$ 的指针，$j$ 是子串 $p$ 的指针，即 $next$ 函数仅于自身这个子串有关，而与源串无关。其实就是找到，以 $j$ 这个点为终点的，后缀与前缀的最大公共长度
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10,M=1e6+10;
int n,m;
// i不用回退,只遍历一遍,j回退到next[j]
// p:子串,s:源串,ne:子串的next数组
// next数组的性质:前后值最多增加1,减少没有限制
char p[N],s[M];
int ne[N];

int main() {
	cin>>n>>p+1>>m>>s+1; // char:可以+1,下标从1开始
	
	// 求next数组过程
	// ne[1]=0不用算(只能回退到0),所以i从2开始
	// j和下面一样,是试图与i匹配的子串,即源串和子串都是本身
	for(int i=2,j=0;i<=n;i++) {
		// 只要不匹配,退而求其次
		while(j && p[i]!=p[j+1])
			j=ne[j];
		// 对眼,前进一步
		if(p[i]==p[j+1])
			j++;
		// 填充next数组
		ne[i]=j;
	}

	// kmp匹配过程
	// i枚举的是当前的s[i],j从0开始
	// p中和当前s试图匹配的是p[j+1],因为j从0开始
	for(int i=1,j=0;i<=m;i++) {
		// 1:回退
		// 只要j没有退回起点(不用重新匹配)
		// 并且当前s[i]不能和当前p[j+1]匹配的话
		while(j && s[i]!=p[j+1])
			j=ne[j];
		// 匹配了则直接找下一位
		if(s[i]==p[j+1])
			j++;
		// 输出所有出现位置的起始下标
		if(j==n) {
			// 匹配成功,i减去子串长度,即是起始下标(从0开始)
			cout<<i-n<<' ';
			j=ne[j]; // 更新ne[j],下次可以回退到这里
		}
	}
	return 0;
}

5. Trie树

高效存储和查找字符串集合的数据结构

Trie2.PNG 
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<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 用Trie树的题目一定限制了字符的个数,如英文字母等等
const int N=1e5+10; // 字符串总长度不超过1e5

// son[i][j]=2: i是第几层,根节点从0开始,j代表字母如'a'=0,2是当前记录到的哪个点的编号
int son[N][26]; // 只包含小写字母,所以每个最多向外延申26个节点,每个节点的儿子是什么
int cnt[N]; // 以当前这个点结尾的单词有多少个
int idx; // 下标是0的点,既是根节点,也是空节点
char str[N]; // 每次的字符串
	
void insert(char str[]) {
	int p=0; // 从根节点开始遍历
	for(int i=0;str[i];i++) {
		int u=str[i]-'a'; // 将a~z映射到0~25
		if(!son[p][u])
			son[p][u]=++idx; // 没有该子节点就创建一个
		p=son[p][u]; // 走到p的子节点,继续往下遍历和创建
	}
	cnt[p]++; // 以节点p结尾的单词个数+1
}

// 读取字符串,查询其在字符串集合中出现的次数
int query(char str[]) {
	int p=0;
	for(int i=0;str[i];i++) {
		int u=str[i]-'a';
		if(!son[p][u])
			return 0; // 该节点不存在,字符串不存在
		p=son[p][u]; // 如果找到了继续往下查询
	}
	return cnt[p]; // 返回字符串出现的次数
}

int main() {
	int m;
	cin>>m;
	while(m--) {
		char op;
		cin>>op>>str;
		if(op=='I')
			insert(str);
		else if(op=='Q')
			cout<<query(str)<<endl;
	}
	return 0;
}

6. 并查集

快速的执行以下操作：将两个集合合并、询问两个元素是否存在一个集合中，时间近乎 $O(1)$

  • 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点存储它的父节点，fa[x]表示x的父节点。

  • Q1：如何判断树根？

    • A1：if(fa[x]==x)

  • Q2：如何求x的集合编号？

    • A2：while(fa[x]!=x) x=fa[x]，每次都要用一个while循环来找很麻烦，直接路径压缩，让所有点都指向自己的祖先节点就行了

  • Q3：如何合并两个区间？fa[x]是x的集合编号，fa[y]是y的集合编号？

    • A3：fa[x]=y 或者 fa[y]=x 都可
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10;
int fa[N];
int n,m;
// 返回x的祖先节点
// 路径压缩版
int find(int x) {
	// 如果父节点不是本身
	if(fa[x]!=x)
		// 把父节点更新成自己的父节点
		fa[x]=find(fa[x]);
	// 返回父节点的编号
	return fa[x];
}

// 连接a/b两个节点所在的集合
void merge(int a,int b) {
	fa[find(a)]=find(b); // a的祖先节点变成b的祖先节点
}

int main() {
	cin>>n>>m;
	// 初始时所有点都自成集合
	for(int i=1;i<=n;i++) {
		fa[i]=i;
	}
	while(m--) {
		char op;
		int a,b;
		cin>>op>>a>>b;
		if(op=='M')
			merge(a,b);
		else {
			if(find(a)==find(b))
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}
	}
	return 0;
}

7. 堆

  1. 插入一个数，heap[++size]=x, up(size)
  2. 求集合中的最小值，heap[1]
  3. 删除最小值，heap[1]=heap[size], size--, down(1) ：用最后一个元素覆盖第一个元素，再把size减1，再维护根节点
  4. 删除任意一个元素，heap[k]=heap[size], size--, down(k), up(k)：删除一个元素，可能上升可能下降，down和up虽然都写但只会执行其中的一个
  5. 修改任意一个元素，heap[k]=x, down(k), up(k)
  • STL库中的堆只能实现前三个，堆是一棵完全二叉树，在模板中用一维数组来维护这棵完全二叉树

7.1. 堆排序

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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10;
int n,m;
int h[N],sz;

// 堆的down操作
void down(int u) {
	int t=u;
	// 如果左孩子比父节点更小,则记录
	if(u*2<=sz && h[u*2]<h[t])
		t=u*2;
	// 如果右孩子比父节点更小,则记录
	if(u*2+1<=sz && h[u*2+1]<h[t])
		t=u*2+1;
	// 说明需要交换节点
	if(u!=t) {
		swap(h[u],h[t]);
		down(t);
	}
}

void up(int u) {
	// 比较简单,因为u节点只用跟父节点相比较
	while(u/2 && h[u/2]>h[u]) {
		swap(h[u/2],h[u]);
		u/=2;
	}
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>h[i];	
	}
	sz=n;
	// 只用进行log(n)次down操作
	for(int i=n/2;i;i--)
		down(i);
	while(m--) {
		cout<<h[1]<<' '; // 把最小值弹出
		// 删除头结点的方法:
		h[1]=h[sz]; // 用最后一个节点覆盖头结点,再把sz--
		sz--;
		down(1); // 再down一下即可
	}
	return 0;
}

7.2. 模拟堆

实现以上物种操作

  • 讲道理，感觉不用理解得特别深
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
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+10;
int n,m;
// ph[k]:第k个插入点,在堆内的下标是什么,ph[j]=k,第j个插入的点在堆内的下标是k
// hp[k]:堆内的某个点,是第几个插入点,hp[k]=j,堆里面下标是j的点对应的在ph中的下标是j
// p:下标(指针),h:(heap)堆,hp和ph是数组指针和堆之间的双向映射
int h[N],ph[N],hp[N],sz;

// 要完成操作4和操作5,必须构建ph和hp之间的映射关系

// 重构交换两个点之间的元素的函数
void heap_swap(int a,int b) {
	swap(ph[hp[a]],ph[hp[b]]);
	swap(hp[a],hp[b]);
	swap(h[a],h[b]);
}

void down(int u) {
	int t=u;
	if(u*2<=sz && h[u*2]<h[t])
		t=u*2;
	if(u*2+1<=sz && h[u*2+1]<h[t])
		t=u*2+1;
	if(u!=t) {
		heap_swap(u,t);
		down(t);
	}
}

void up(int u) {
	while(u/2 && h[u/2]>h[u]) {
		heap_swap(u/2,u);
		u/=2;
	}
}

int main() {
	int n;
	cin>>n;
	int m; // 记录第几个插入的数
	while(n--) {
		string op;
		int k,x;
		cin>>op;
		if(op=="I") {
			cin>>x;
			sz++;
			m++;
			ph[m]=sz,hp[sz]=m;
			h[sz]=x;
			up(sz);
		} else if(op=="PM") {
			cout<<h[1]<<endl;
		} else if(op=="DM") {
			heap_swap(1,sz);
			sz--;
			down(1);
		} else if(op=="D") {
			cin>>k;
			k=ph[k];
			heap_swap(k,sz);
			sz--;
			down(k),up(k);
		} else {
			cin>>k>>x;
			k=ph[k];
			h[k]=x;
			down(k),up(k); 
		}
	}
	return 0;
}

8. Hash表

存储结构：开放寻址法、拉链法，另一个应用是字符串哈希方式

  • Hash表也称散列表，有两种处理地址冲突的方法，所以也有两种数据结构来存储，分别是开放寻址法和拉链法
  • Hash表的算法时间复杂度一般都是 $O(1)$ 的，所以一般不手动排序，这样时间复杂度反而会扩大成 $O(nlog^n)$
  • STL库中的哈希表数据结构是 $unorder_map$，通常不使用，因为会比手写的 $Hash$ 表慢 $3$ 倍左右。

8.1. 拉链法

在这里插入图片描述 
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<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 哈希:取模这个数要尽量取质数,并且离2的n次方尽可能远,这样冲突的概率才最小
const int N=1e5+3; // 大于1e5的第一个质数
// h[i]:哈希表的第i槽,是一个邻接表
// e[i]:第i个节点的值
// ne[i]:下一条边的下标
int h[N],e[N],ne[N],idx;
int n;

void insert(int x) {
	// 注意x最小可以取10^-9,所以先%N,再加上N才会一定得到一个正数
	// 把x映射到0~1e5+3之间
	// x%N有可能得到负数,所以+N变回正数
	int k=(x%N+N)%N;
	// 链式前向星头插法
	e[idx]=x,ne[idx]=h[k],h[k]=idx++;	
}

bool find(int x) {
	int k=(x%N+N)%N; // 求得x的映射地址
	// 去这条链上找目标值
	for(int i=h[k];i!=-1;i=ne[i]) {
		if(e[i]==x)
			return true; // 找到了
	}
	return false;
}

int main() {
	cin>>n;
	string op;
	memset(h,-1,sizeof h);
	int x;
	while(n--) {
		cin>>op>>x;
		if(op=="I")
			insert(x);
		else {
			if(find(x))
				cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
		}
	}
	return 0;
}

8.2. 开放寻址法

  • 实际上用的更多的哈希表做法，也更好理解，因为只用开一个数组，但是这个一维数组开的空间大小一般是题目范围的2~3倍。
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<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 因为第一个大于2e5(1e5*2,这是一个经验值)的质数是2e5+3
const int N=2e5+3;
const int null=0x3f3f3f3f;
int h[N];

// 如果x在哈希表中已存在,返回x所在的位置
// 如果x在哈希表中不存在,返回它应该存储的位置
int find(int x) {
	int k=(x%N+N)%N; // k是x预期存储的地址
	// 如果有人占用了这个位置并且占用这个位置的不是我自己的话
	while(h[k]!=null && h[k]!=x) {
		k++; // 就向下找下一个位置
		// 如果找满了都找不到,则赋值又从第一个位置开始找
		// 并且这个过程是一定会停止的,因为坑比人多
		if(k==N) 
			k=0;
	}
	return k;
}

int main() {
	// 1:因为N是1e5,先找大于2e5的第一个质数是多少
//	for(int i=2e5;;i++) {
//		bool flag=true;
//		for(int j=2;j*j<=i;j++) {
//			if(i%j==0) {
//				flag=false;
//				break;
//			}
//		}
//		if(flag) {
//			cout<<i<<endl;
//			break;
//		}
//	}
	int n;
	cin>>n;
	memset(h,0x3f,sizeof h);
	while(n--) {
		string op;
		int x;
		cin>>op>>x;
		
		if(op=="I")
			h[find(x)]=x; // 插入一个值
		else {
			if(h[find(x)]==null)
				cout<<"No"<<endl;
			else
				cout<<"Yes"<<endl;
		}
	}
	return 0;
}

8.3. 字符串前缀哈希

h[i] 代表前i个字符的哈希值

image-20231124144802886

  • 对于一个字符串”ABCD”，我们可以把四个数字看成p进制的1234，那么ABCD就可以从p进制转换成十进制，得到的结果应该是 $1×p^3 + 2×p^2 + 3×p^1 + 4×p^0$，再mod一个Q，就可以把任意一个字符串的值映射到$[0,Q-1]$的数值。

  • 注意一般情况下，1）不能把一个字母映射成0，比如把字母A映射成0，那么AA的值也是0，这样多个字符就可能被映射成一个值；2）假设人品足够好，不存在冲突，设置$p=131$或$13331$，$Q=2^{64}$，在这种情况下99%情况下不会冲突；3）对于h中的每一个元素都要模上$Q=2 ^{64}$，可以用$unsigned\ long\ long$这种数据类型来开h数组，通过自然溢出的方式来等价于取模运算。

  • 假设想求字符串的子串从$[L,R]$这个子串的哈希值，已知$h[R]$和$h[L-1]$，让$h[L-1]×p^{(k-L+1)}$就可以使h[L]和h[R]对齐，所以转换公式是$h[R]-h[l] × p^{(k-L+1)}$，预处理前缀哈希值就应该是：$h[i]=h[i-1]×p+str[i]$。

  • 字符串哈希有一个KMP算法都无法做到的操作：给一个字符串，给两个区间，问这两个子串是否是相同的，并且只用 $O(1)$ 的时间就能解决

image-20231124151032942
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信