更好的阅读体验：http://222.203.110.13/d/luogu/blog/250/67e93696ae751d0c51624113

比赛链接

前言

本场比赛赛题均为需要时空优化的，都是好题，质量还是可以的~

本题解若有笔误请找作者，然后请不要抄袭题解！

T1 【模板】最长公共子序列

题目大意

求两个从 $1 \sim n$ 的排列的最长公共子序列。

解题思路

模版题就讲细一点。

【50 pts 做法】

看题直接 DP 秒了，想必大家做了这个都可以写出这种做法。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

代码就不放了，很简单的。

【60 pts 做法】

我们发现只用了 $f_{i,j},f_{i-1,j-1},f_{i,j-1}$，所以原来 $n$ 行 $n$ 列只用了最后两行，那果断滚动数组。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int t, n, f[2][N], a[N], b[N];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++)
	{
		t ^= 1;
		for (int j = 1; j <= n; j++)
		{
			if (a[i] == b[j]) f[t][j] = f[t ^ 1][j - 1] + 1;
			else f[t][j] = max(f[t ^ 1][j], f[t][j - 1]);
		}
		
	}
	cout << f[t][n];
	return 0;
 }

【100 pts 做法】

可以看做是特殊 LCS 转 LIS，用 $ind$ 记录 $b_j$ 元素到索引 $j$ 的映射。（具体老师都讲了）

• 时间复杂度：$O(n \log n)$。
• 空间复杂度：$O(n)$。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, a[N], b[N], idx[N], ans, c[N];

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i], idx[b[i]] = i;
	for (int i = 0; i < n; i++) a[i] = idx[a[i]];
	for (int i = 0; i < n; i++)
	{
		int p = lower_bound(c, c + ans, a[i]) - c;
		c[p] = a[i];
		if (p == ans) ans++;
	}
	cout << ans << endl;
	return 0;
 }

T2 [IOI2000] 回文字串

题目大意

就出将给定字符串变成回文词所需要插入的最少字符数。

解题思路

好吧这道 IOI 的题还是很水的qwq

【做法 1】

就是求它的正序串与它的逆序串求出最长公共子序列即可。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int f[1005][1005];
char a[1005], b[1005];

int main()
{
	cin >> (a + 1);
	int n = strlen(a + 1);
	strcpy(b + 1, a + 1);
	reverse(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if(a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
			else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
		}
	}
	cout << n - f[n][n];
	return 0;
 }

【做法 2】

我们发现只会用到 $f_{l+1,r-1},f_{l+1,r},f_{l,r-1}$，那肯定可以改滚动数组 $l$ 降一维。

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。

终于有个首 A 了，开赛大概 10mins 就 A 了，真的很水。

代码如下：

#include <bits/stdc++.h> 
using namespace std;

int f[2][1005], t, n;
char s[1005];

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = n - 1; i > 0; i--)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (s[i] == s[j]) f[t ^ 1][j] = f[t][j - 1];
			else f[t ^ 1][j] = min(f[t][j], f[t ^ 1][j - 1]) + 1;
		}
		t ^= 1;
	}
	cout << f[t][n] << endl;
	return 0;
}

T3 [NOIP2015 提高组] 子串

题目大意

现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 $B$ 相等？

解题思路