L2-002 链表去重（分数 25）

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉，即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21->-15->-15->-7->15，你需要输出去重后的链表 21->-15->-7，还有被删除的链表 -15->15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（<= 10^5，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中 地址 是该结点的地址，键值 是绝对值不超过 10^4 的整数，下一个结点 是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

题面解读

不按顺序给出一个链表，第一行输出删除重复元素后的链表，第二行输出删除的元素组成的新链表

解题思路

维护两个数组，nxt[]和val[]分别记录一个节点的后续节点和值，下标就是节点编号，这样就可以根据题目要求建立一个链表。后面可以用带含义数组去重可以用unordered_map去重，分为两个链表，注意连接关系以及最后一个节点连接-1。

注意1：用printf的%05d输出，用C++函数还是比较难处理的。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
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
#define PII pair<int, int> 
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;

int L, n;
int nxt[N], val[N];
vector<int> a, b;
bool vis[N];

void sol(){
	cin >> L >> n;
	for (int i = 1; i <= n; i++){
		int od, ne, v;
		scanf("%d%d%d", &od, &v, &ne);
		nxt[od] = ne, val[od] = v;
	}
	for (int p = L; p != -1; p = nxt[p])
		if (vis[abs(val[p])])
			b.push_back(p);
		else{
			vis[abs(val[p])] = true;
			a.push_back(p);
		}
	int lena = a.size();
	for (int i = 0; i < lena; i++){
		printf("%05d %d ", a[i], val[a[i]]);
		if (i < lena - 1)
			printf("%05d\n", a[i + 1]);
		else
			printf("-1\n");
	}
	int lenb = b.size();
	for (int i = 0; i < lenb; i++){
		printf("%05d %d ", b[i], val[b[i]]);
		if (i < lenb - 1)
			printf("%05d\n", b[i + 1]);
		else
			printf("-1\n");
	}
}

int main(){
		sol();
}

L2-003 月饼（分数 25）

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价，以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼，以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数，以及一个不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

题面解读

可拆分背包模型

解题思路

可拆分背包模型，按照平均值进行排序选择。

注意：题目中的坑人描述 正整数 和 正数，因此要用double存每个物品的库存量和总售价。

题解代码

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
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int N = 1010;

double sum = 0;
int n, mx;
struct obj{
	double c, p;
	double ave;
}a[N];

bool cmp(obj x, obj y){
	if (x.ave == y.ave)
		return x.c > y.c;
	else
		return x.ave > y.ave;
}

void sol(){
	cin >> n >> mx;
	for (int i = 1; i <= n; i++)
		cin >> a[i].c;
	for (int i = 1; i <= n; i++)
		cin >> a[i].p;
	for (int i = 1; i <= n; i++)
		a[i].ave = 1.0 * a[i].p / a[i].c;
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1;i <= n; i++)
		if (a[i].c <= mx){
			sum += a[i].p;
			mx -= a[i].c;
		}
		else{
			if (mx > 0)
			sum += mx * a[i].ave;
			break;
		}
	cout << fixed << setprecision(2) << sum << endl;
}

int main(){
	IO
	sol();
	return 0;
}

L2-004 这是一棵二叉搜索树吗？（分数 25）

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

  • 其左子树中所有结点的键值小于该结点的键值；
  • 其右子树中所有结点的键值大于等于该结点的键值；
  • 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是一对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（<= 1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES，然后在下一行中输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

题面解读

给定一个二叉数的前序遍历，判断是否是二叉搜索树的前序遍历或是其镜像的前序遍历，是的话输出其后序遍历。

解题思路

前序遍历顺序是 根-左-右，那一个区间的第一个数一定是root，以正常二叉搜索树为例，从root后第一个数往后找，找第一个大于等于root的数，这个数就是左右两个子树的分界点，从这个数往后遍历如果出现比root大的数那么就不是一颗二叉搜索树，最后递归左右子树，继续进行判断，如果都满足条件就true否则false；镜像的话同理。再看如果是一颗二叉搜索树的前序遍历如何求他的后序遍历，

前序遍历到后序遍历

可以看下手话的图帮助理解，可以再递归左右子树的同时将root添加到一个vector中，可以和判断二叉树的递归放在一起做，后序遍历就在左右子树遍历完之后再将根添加进vector中，或者只有一个节点时候也要添加进vector。

题解代码

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
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
const int N = 1010;

int n;
vector<int> a, h;

bool dfs(int l, int r, int op){
	int root = a[l];
	int p = l + 1;
	if (l > r)
		return true;
	if (l == r){
		h.push_back(root);
		return true;
	}
	if (op == true){
		while (p <= r && a[p] < root) p++;
		for (int i = p; i <= r; i++)
			if (a[i] < root)
				return false;
		if (!dfs(l + 1, p - 1, op))
			return false;
		if (!dfs(p, r, op))
			return false;
		h.push_back(root);
		return true;
	}
	else{
		while (p <= r && a[p] >= root) p++;
		for (int i = p; i <= r; i++)
			if (a[i] >= root)
				return false;
		if (!dfs(l + 1, p - 1, op))
			return false;
		if (!dfs(p, r, op))
			return false;
		h.push_back(root);
		return true;
	}	
}

void sol(){
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	if (dfs(0, n - 1, true)){
		cout << "YES" << endl;
		for (int i = 0; i < h.size(); i++){
			cout << h[i];
			if (i < h.size() - 1)
				cout << ' ';
		}
	}
	else{
		h.clear();
		vector<int>().swap(h);
		if (dfs(0, n - 1, false)){
			cout << "YES" << endl;
			for (int i = 0; i < h.size(); i++){
				cout << h[i];
				if (i < h.size() - 1)
					cout << ' ';
			}
		}
		else{
			cout << "NO" << endl;
		}
	} 
}

int main(){
	IO
	sol();
	return 0;
}

L2-008 最长对称子串（分数 25）

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定 Is PAT&TAP symmetric?，最长对称子串为 s PAT&TAP s，于是你应该输出 11。

输入格式：

输入在一行中给出长度不超过 1000 的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

题面解读

给你一个字符串，求他最长对称子串长度。

解题思路

这题思路我自己想出来了，但碍于我的代码功底并不强，导致有很多的小错误。打*的注释都是我当时犯得错误。

我想到了字符串的子串匹配做法，是用字符串哈希来做，只是需要两个数组，一个存前缀哈希一个存后缀哈希。

题解代码

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
#include <bits/stdc++.h>
using namespace std;

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
const int N = 1010;

uls P = 131;
uls p[N], sum1[N], sum2[N];
char s[N], t[N];

uls cal(int l, int r, bool op){
	if (op)
		return sum1[r] - sum1[l - 1] * p[r - l + 1];
	else
		return sum2[l] - sum2[r + 1] * p[r - l + 1];//*r-l+1不是l-r-1
}

void sol(){
	fgets(s + 1, N, stdin);
	int len = strlen(s + 1);
	p[0] = 1;
	for (int i = 1; i <= len; i++){
		p[i] = p[i - 1] * P;
		sum1[i] = sum1[i - 1] * P + s[i];
	}
	for (int i = len; i >= 1; i--)
		sum2[i] = sum2[i + 1] * P + s[i];
	int maxn = 1;//*找不到长度>=2的就输出1
	for (int i = 1; i < len; i++)
		for (int j = i + 1; j <= len; j++)
			if (cal(i, j, true) == cal(i, j, false))
				maxn = max(maxn, j - i + 1); //*不是i-j+1
	cout << maxn << endl;
}

int main(){
	IO
	sol();
	return 0;
}