517coding 题解合集

发表于 | 阅读次数：

写个合集，加深一下自己的理解。

$517$ 的题切起来真的是有一种奇妙的快感。

$T3960$

题意

给定一个长度为 $N$ 的整数序列以及整数 $S$ 。求最短的连续子序列的长度使得这个连续子序列的和大于等于 $S$ 。
如果找不着，输出 $0$ 。

$1\le N \le 10^{5}$

题解

使用双指针。

代码

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>

const int N = 1e5 + 5;

int n, s;
int sum[N];

int main()
{
	scanf("%d%d", &n, &s);
	for (int i = 1; i <= n; i ++)
	{
		int x;
		scanf("%d", &x);
		sum[i] = sum[i - 1] + x;
	}
	if (sum[n] < s)
	{
		printf("0");
		return 0;
	}
	int l = 1, r = 1, ans = n;
	while (sum[r] < s)
		r ++;
	while (r <= n)
	{
		while (sum[r] - sum[l] >= s)
			l ++;
		ans = std::min(ans, r - l + 1);
		r ++;
	}
	printf("%d", ans);
	return 0;
}

$T3970$

题意

给定长度为 $N$ 整数序列，要求计算有多少区间，它里面数字的异或之和=相加之和。

$1\le N \le 2 \cdot 10^{5}$

题解

发现异或之和=相加之和的要求是这些数的二进制的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
#include <bits/stdc++.h>
typedef long long ll;

const int N = 2e5 + 5;

int n;
ll a[N];
ll s1[N], s2[N];
ll ans;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%lld", &a[i]), s1[i] = s1[i - 1] + a[i], s2[i] = s2[i - 1] ^ a[i];
	int l = 1, r = 1;
	while (r <= n)
	{
		while (s1[r] - s1[l - 1] != (s2[r] ^ s2[l - 1]))
			l ++;
		ans += r - l + 1; // 此处加上的是以 r 为右边界的方案
		r ++;
	}
	printf("%lld", ans);
	return 0;
}

$T3980$

题意

给定 $n$ 个整数, 从中选出若干个数字（每个数字最多选一次），使得它们的和取余 $m$ 最大，求最大的余数。

$1 \le n \le 35,1 \le m \le 10^9$

题解

使用折半搜索
其特征为 $O(2^n)$ 会爆，但是 $O(2^{\frac{n}{2}})$ 不会爆，而且左右两边可以以某种方式合并。

我们枚举左右两半所有情况，注意到如果两边的两种方案加起来大于 $m$ ，那么一定不是最优的。
正规的说，如果有 $a,b < m$ ，那么 $a + b - m < \min(a,b)$

所以对于左半边的每一种方案，我们二分右半边与其加起来小于 $m$ 的最大值的方案，并用其更新答案。

太优美了！

代码

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

const int N = 35 + 5;
const int INF = 1 << 30;

int n, m;
int a[N];
std::vector <int> ans[2];

int dfs(int p, int r, int sum, int num)
{
	ans[num].push_back(sum);
	for (int i = p + 1; i <= r; i ++)
		dfs(i, r, (sum + a[i]) % m, num);
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++)
		scanf("%d", &a[i]), a[i] %= m;
	dfs(0, n / 2, 0, 0);
	dfs(n / 2, n, 0, 1);
	std::sort(ans[0].begin(), ans[0].end());
	std::sort(ans[1].begin(), ans[1].end());
	int res = 0;
	for (int i = 0; i < ans[0].size(); i ++)
		res = std::max(res, ans[0][i] + *--std::lower_bound(ans[1].begin(), ans[1].end(), m - ans[0][i]));
	printf("%d", res);
	return 0;
}

$T3990$

题意

给定一个长度为N的字符串 $S$ 。

每次可以从 $S$ 的开头或者结尾取出一个字符，放到一个 $T$ 字符串的尾部。

输出字典序最小的 $T$ 字符串，每 $80$ 个字符换一行输出。

$1 \le N \le 2000$

题解

$l,r$ 记录当前走到位置，当 $s[l]!=s[r]$ 时明显输出小的那个，否则往里面探同样深度，得到哪边后来最优走哪边。

代码

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

int n;
std::string s;
int cnt;

void print(char c)
{
	putchar(c);
	cnt ++;
	if (cnt % 80 == 0)
		printf("\n");
}

int main()
{
	scanf("%d", &n);
	std::cin >> s;
	int l = 0, r = n - 1;
	while (l <= r)
	{
		bool f = 0;
		for (int i = 0; 2 * i <= r - l; i ++) // l + i <= r - i
		{
			if (s[l + i] < s[r - i])
			{
				f = 0;
				break;
			}
			else if (s[l + i] > s[r - i])
			{
				f = 1;
				break;
			}
		}
		if (!f)
			print(s[l ++]);
		else
			print(s[r --]);
	}
	return 0;
}