爱吃咸鱼的喵の无名小站 > 2018百度之星程序设计大赛（资格赛） 子串查询 HDU6345 解题思路

2018百度之星程序设计大赛（资格赛） 子串查询 HDU6345 解题思路

2019-01-18

线段树, 前缀和

题目链接 HDU 6345 子串查询

1、题目分析

  本题只要看懂了题意其实还是不难的，题目意思是要求出给定区间中最小子串的个数，所以1、找到最小子串 2、求出最小子串的个数
  根据题意，其实最小子串就是给定区间中字典序最小的单个字母，明白了这点，那么本题的就是求解，给定区间中字典序最小的单个字母出现的次数

2、细节思路

  根据题目，数据的数量级为$10^5$,暴力查询求解肯定会超时，不难想到，其实这个字典序最小字母次数是满足区间加法的，假设给定两个相连区间$[a,b]$和$[b,c]$，两个区间中最小字母分别为$x1,x2$,出现次数分别为$t1,t2$,那么两个区间合并后的区间为$[a,c]$，合并之后区间的最小字母和出现次数分别记为$x3,t3$。不难得到，有以下情况:

条件 结论
$x1=x2$ $x3=x1=x1$ $t3=t1+t2$
$x1>x2$ $x3=x2$ $ t3=t2$
$x1<x2$ $x3=x1$ $t3=t1$

满足区间加法的问题都能用线段树来解决，所以此题的关键在于线段树的编写。

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
//注意 ！！！重载运算符 + 不要改变本身对象
struct Sum {
	int number;
	char ch;
	Sum() {
		ch = 'Z'+1;
		number = 0;
	}
	Sum operator +(const Sum &rhs) {
		Sum temp;
		temp.number = number;
		temp.ch = ch;
		
		if(temp.ch==rhs.ch)
		temp.number= number+rhs.number;
	   else if (temp.ch > rhs.ch)
	   {
		   temp.number = rhs.number;
		   temp.ch = rhs.ch;
	   }
		return temp;
	}
	Sum& operator =(const Sum &rhs) {
		ch = rhs.ch;
		number = rhs.number;
		return *this;
	}
	bool operator >(const Sum &rhs) {
		return ch > rhs.ch;
	}
	bool operator <(const Sum &rhs)
	{
		return ch < rhs.ch;
	}
	bool operator == (const Sum &rhs)
	{
		return ch == rhs.ch;
	}
};

这里每一个sum有两个属性,ch表示该区间的最小字母,number代表最小字母出现次数。

4、程序代码

其他部分的代码和普通的线段树没什么区别，全部代码如下：

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define  mem(a,b) memset(a,b,sizeof(a))
#define  NUM_OF_CHAR  26
using namespace std;
const int maxn = 100000 + 1000;
char A[maxn];
int T;
int length,q;

//注意 ！！！重载运算符 + 不要改变本身对象
struct Sum {
	int number;
	char ch;
	Sum() {
		ch = 'Z'+1;
		number = 0;
	}
	Sum operator +(const Sum &rhs) {
		
		Sum temp;
		temp.number = number;
		temp.ch = ch;
		
		if(temp.ch==rhs.ch)
		temp.number= number+rhs.number;
	   else if (temp.ch > rhs.ch)
	   {
		   temp.number = rhs.number;
		   temp.ch = rhs.ch;
	   }

		return temp;
	}
	Sum& operator =(const Sum &rhs) {
		ch = rhs.ch;
		number = rhs.number;
		return *this;
	}

	bool operator >(const Sum &rhs) {
		return ch > rhs.ch;
	}
	bool operator <(const Sum &rhs)
	{
		return ch < rhs.ch;
	}
	bool operator == (const Sum &rhs)
	{
		return ch == rhs.ch;
	}
};


Sum sum[maxn << 2];

//更新节点的函数
inline void PushUp(int rt)
{
	int left = rt << 1;
	int right = rt << 1 | 1;
	//每个字母的个数分别为 左子树和右子树每个字母的个数之和
	sum[rt] = sum[left] + sum[right];

	//printf("sum[%d] = sum[%d] + sum[%d]\n", rt, left, right);

}

//建立线段树
void Build(int l, int r, int rt)
{
	//printf("Build(l = %d ,r = %d, rt = %d)\n", l, r, rt);
	
	//如果到了叶子节点那么保存该节点的值
	if (l == r)
	{	
		//该字母出现一次
		sum[rt].number = 1;
		sum[rt].ch = A[l];
		//printf("到达叶子节点rt = %d  sum[%d].number = %d sum[%d].ch = %c\n", rt, rt, sum[rt].number, rt, sum[rt].ch);
		return;
	}
	//计算中点
	int m = (l + r) >> 1;

	//递归建立左右子树
	Build(l, m, rt << 1);
	Build(m + 1, r, rt << 1 | 1);
	//左右子树建立完毕之后 建立本节点

	PushUp(rt);
}



//查询函数，查找在(L,R)中的每个字母的和
Sum Query(int L, int R, int l, int r, int st)
{
	//printf("L = %d , R= %d, l= %d ,r = %d , st =%d \n", L, R, l, r, st);
	//如果范围在 (L,R）之中，那么直接返回值
	if (L <= l&&R >= r)
	{
		//printf("return sum[%d]\n", st);
		//for (int i = 0; i < 5; i++)
		//	printf("sum[%d].ch[%d] = %d  ", st, i, sum[st].ch[i]);
		//printf("\n");
		return sum[st];
	}

	Sum ans;
	//mem(&ans, 0);
	//printf(" 递归计算\n");
	//for (int i = 0; i < 5; i++)
	//	printf("初始化ans.ch[%d] = %d  ", i, ans.ch[i]);
	//printf("\n");

	int m = (l + r) >> 1;
	//查找与子区间是否存在并集，如果不存在则不用查找
	if (m >= L) ans = ans + Query(L, R, l, m, st << 1);
	if (m < R) ans = ans + Query(L, R, m + 1, r, st << 1 | 1);

	//for (int i = 0; i < 5; i++)
	//	printf("ans.ch[%d] = %d  ",i, ans.ch[i]);
	//printf("\n");
	//统计完毕返回
	return ans;

}

void solve()
{
	int left_bound;
	int right_bound;
	Sum my_ans;
	while (q--)
	{
		scanf("%d%d", &left_bound, &right_bound);

		//printf("left_bound = %d,right_bound = %d \n", left_bound, right_bound);
		my_ans = Query(left_bound, right_bound, 1, length, 1);
			
		//for (int i = 0; i < 5; i++)
		//	printf("my_ans.ch[%d] = %d   ", i, my_ans.ch[i]);
		//printf("\n");

		printf("%d\n", my_ans.number);
	}
}

int main()
{
	int kcase = 1;
	freopen("C:\\Users\\lenovo\\Desktop\\test\\in.txt", "r", stdin);
	freopen("C:\\Users\\lenovo\\Desktop\\test\\out.txt", "w", stdout);
	scanf("%d", &T);
	//mem(sum, 0);
	while (T--)
	{
		scanf("%d%d", &length, &q);
		scanf("%s", A+1);

		Build(1, length, 1);

		//for (int i = 1; i < 6; i++)
		//	printf("sum[%d].ch = %c sum[%d].number = %d  ", i, sum[i].ch, i, sum[i].number);
		//printf("\n");
		printf("Case #%d:\n", kcase++);
		solve();
	}
	return 0;
}