0713 总结

题目

• T1
• T2
• T3
• T4

问题分析

T1

一道黄题。$\color{white}{水题}$

第一眼就是一个一维 DP，再推一下式子可以发现这道题数组都不用开，几个变量就解决了，最终耗时10min。

$$100pts$$

T2

在考场上先看的数据范围，发现是 $1\le n\le 50$，就开始思考 $O(n^4)$ 的做法，然后就先表示了一个 DP 数组 $dp[i][j]$ 表示 $[i,j]$ 区间内的最少涂色次数，然后思考状态转移。

随后我发现了一种状态转移的方法，在 $s[i] == s[j]$ 的情况下，可以在左右两边找到最长的 $s[i]$，然后将 $dp[i][j]$ 用 $dp[p1][p2]$ 更新。这种做法是 $O(n^3)$ 的。

代码长这样：

if(s[i]==s[j]){
	int p1=i+1,p2=j-1;
	while(p1<=j&&p2>=i&&(s[p1]==s[p1-1]||s[p2]==s[p2+1])){
		if(s[p1]==s[p1-1]) p1++;
		if(s[p2]==s[p2+1]) p2--;
	}
	dp[i][j]=dp[p1][p2]+1;
}

但是考场上并没有举出反例证明这是错的，其实反例非常好构造 AAQWQAACBCAA 就是一个，这是没有考虑 AA***AA***AA 的贡献造成的。

实际上这样推就行：

dp[i][j]=min(dp[i+1][j],dp[i][j-1]);

$$O(n^2)$$

以后一定要多模几组样例。

$$100pts->70pts（洛谷）/40pts（本地）$$

T3

因为是 DP 专练，所以肯定不打 DP 啊必然是想着怎样 DP 的。

模拟了一下二维 DP，发现式子十分好推，只不过转移时代码又臭又长，只能作罢。

接着打了一个 DFS，发现 DFS 下来非常好写，于是观察了一下时间复杂度，发现要炸，赶紧想怎么优化。

发现 BFS 的板子跟 DFS 差不多，于是打了一个 BFS，再进行了一下优化，算了一下时间复杂度和常数，发现是 $O(能过)$，于是开开心心交上去了，其实算一算空间复杂度就知道要炸，而且本来的代码是能过的，但是我竟然把数组开小了！！！。

就是挺智障的一个错，本来能得 $60pts$ 的现在只能得 $40pts$ 了。

$$100pts（预期）->60pts（实际）->40pts（脑瘫）$$

T4

考场上其实是想好了怎么递推的，递推式其实也非常好想，然后再写出来就会发现其实是一道斜率优化板子题。

但是观察数据范围可以发现 $2 \le n \le 20000$，感觉 $O(n^2)$ 也可以过，于是就将循环展开了 $16$ 次，因为 $\log_2 20000$ 其实也就 $15$ 的样子。

果然，展开了以后进行一下模拟，发现极限数据也就 $200ms$ 左右的样子，最后交上去经过最终的重测时间也就是斜率优化的 $2$ 倍左右，成功节省下来了不知道干什么用的时间。

$$100pts$$

总结

这次考试我有很多地方就是有很多脑瘫的错误，最后检查代码是也没有检查出来，本来预计大概可以 AK 的，最终也只拿了 $280pts(rank\ 3^{rd})$，有点可惜。

再次审视了我考场上的注释，发现我绝大部分的错误原因都在考场上想到了，但为什么我没改出来啊！！！！

教训就是除了要分析时间复杂度还要分析空间复杂度，还有就是要对自己的递推式再三审视，考虑所有情况，检查是也要仔细一点，不要再像某些 T3 一样把数组开小了。$\color{white}{总而言之，菜就多练}$