前言

笔者一直在想抽出一点时间来好好地写一写 NOIP 早年的题目。然而一来因为一直没有时间，二来对早年的大搜索，dp 和大模拟实在是充满恐惧，就没有敢动笔写。

然而，随着笔者一直在一点点成长，OI 水平也在慢慢地进步，这些起初看起来很让人抓狂的模拟题，也不再是那么的不顺手了。

尽管早年的题目与当今 NOIP 的题目偏重不尽相同，但是我觉得无论是以前的，还是现在的，做 NOIP 套题的感觉，和琢磨高效算法的快感是不变的— —这不正是我们热爱 OI 的原因吗？

希望我们不忘初心吧，以后还能一如既往地热爱 OI，热爱这种充满思考的生活。

整体难度分析

毕竟是早年的 NOIP 题目，总体来讲并不难。

早期的 NOIP 对算法的要求并不高，但对代码能力和思维的要求较高，题目类型偏重于大模拟、搜索和 dp。即使是在数据结构和高级算法盛行的今天，我们也要时常做一做这些题目，确保自己的码力。毕竟，算法知识是思维上的问题，想要落实在实践中，就必须以代码作为载体。这也是为什么，笔者的第一篇解题报告，从 NOIP2001 TG 写起。

空有思维却不能落于实地，那再完美的思路，也只是空中楼阁罢了；实践能力更强的人，走得才能更久。

题解

T1 一元三次方程求解

题意分析

求三次方程 \(ax^3+bx^2+cx+d=0\) 的三个实根。

题目思路

非常裸的一道二分答案题。

题目保证存在三个实数根，也就保证了应该有三个单调区间，就有了两个极值点。

定义函数 \(f(x)=ax^3+bx^2+cx+d\)，我们可以求出其导数为 \(f^\prime(x)={3ax}^2+2bx+c\)，那么原函数的两个极值点分别为导函数的顶点，用求根公式求出极值点，即 \(x_{1,2}=\dfrac{-2b\pm\sqrt{(2b)^2-4\times3ac}}{2\times 3a}=\dfrac{-b\pm\sqrt{b^2-3ac}}{3a}\)。

求出两个极值点后，将区间 \([-100,100]\) 分割为三个单调小区间 \([-100,x_1]\)，\([x_1,x_2]\)，\([x_2,100]\)，分别对这三个区间进行二分答案，就可以求出所有的零点。时间复杂度 \(\mathcal{O}(\)能过\()\) QwQ。

注意精度，而且系数要用 double 存储。

代码

#include 
#include 
using namespace std;
const double eps = 1e-5;

double a, b, c, d;
struct Part{  //定义区间结构体 
	double left, right;  //左右端点 
	int deriv;  //区间单调性 
} A, B, C;

inline double calc(double x) {
	return a * pow(x, 3) + b * pow(x, 2) + c * x + d;
}

void Binary_Search(Part p) {  //二分答案求出某个区间中的零点 
	double mid;
	
	while(abs(p.right - p.left) >= eps) 
		mid = (p.right + p.left) / 2, (calc(mid) * p.deriv > 0) ? (p.right = mid) : (p.left = mid);
		
	printf("%.2f ", mid);
}

int main(void) {
	freopen("solve.in", "r", stdin);
	freopen("solve.out", "w", stdout);
	
	scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
	
	A.left = -100;
	A.right = B.left = (- b - sqrt(b * b - 3 * a * c)) / (3 * a);  //导数法求出三次函数的极值点 
	B.right = C.left = (- b + sqrt(b * b - 3 * a * c)) / (3 * a);
	C.right = 100;
	
	A.deriv = calc(A.left) > calc(A.right) ? -1 : 1; Binary_Search(A);  //二分求出三个单调区间的零点 
	B.deriv = calc(B.left) > calc(B.right) ? -1 : 1; Binary_Search(B);
	C.deriv = calc(C.left) > calc(C.right) ? -1 : 1; Binary_Search(C);
	
	return 0;
}

T2 数的划分

题意分析

求出将 \(n\) 能表示成多少种 \(k\) 个正整数的和的形式，如果两种表示形式中，加数只是顺序不同，则算作同一种形式。

一种能过的解法

这道题当然是一道 dp 题，我们定义 \(dp(i,j)\) 代表将 \(i\) 分成 \(j\) 个正整数和的方案数。

更加形象地，我们可以认为 \(dp(i,j)\) 代表把 \(i\) 个球放入 \(j\) 个盒子里，且每个盒子都不能为空的放法。那么，我们可以先往所有的盒子里先放一个球，剩下了 \(i-j\) 个球，因为所有的盒子都不是空的，就可以随便放了，那么有 \(dp(i-j, 1)+dp(i-j, 2)+\cdots+dp(i-j, j)\) 中放法。

所以状态转移方程为：

\[dp(i, j)=\sum_{k=1}^j{dp(i-j, k)} \]

然后暴力转移就可以，时间复杂度为 \(\Theta(n^2k)\)。

优化算法

这道题中 \(n\) 和 \(k\) 都特别小，所以 \(\Theta(n^2k)\) 是可以完成的，如果将 \(n\) 和 \(k\) 都放大亿些，例如 \(n\le 2\times10^5\)，\(k\le 600\)（传送门），这个时候，\(\Theta(n^2k)\) 就会被卡爆时了 QwQ。

我们发现，在 dp 的过程中，我们产生了大量的重复转移：如果我们可以通过某一个确定的值，直接求出 \(dp(i,j)\)，那就可以将时间复杂度优化到 \(\Theta(nk)\)，这就是很大的一个优化了！

当然，这是可以做到的：考虑 \(dp(i-1,j-1)\) 的转移方程，有

\[\begin{aligned} dp(i-1,j-1) &= \sum_{k=1}^{j-1}{dp((i-1)-(j-1),k)}\\ &= \sum_{k=1}^{j-1}{dp(i-j,k)}\\ &= \sum_{k=1}^j{dp(i-j,k)}-dp(i-j,j)\\ &= dp(i,j)-dp(i-j,j) \end{aligned} \]

移项，得 \(dp(i,j)=dp(i-j,j)+dp(i-1,j-1)\)，这个时候，我们就可以 \(\Theta(1)\) 转移每个状态，整个时间复杂度为 \(\Theta(nk)\)，进行了优化。

同时，我们发现 \(dp(i,j)\) 只与 \(dp(i-j,j)\) 与 \(dp(i-1,j-1)\) 有关，于是可以压掉 \(j\) 一维，将空间复杂度压到 \(\Theta(n)\)。但是我没有 QwQ。

代码

#include 
#define reg register
using namespace std;
const int maxN=201;

int n, k;
int dp[201][7] = {{1}};  //定义 dp[i][j] 为数 i 划分为 j 份的方案数 
int main(void){
	freopen("divide.in", "r", stdin);
	freopen("divide.out", "w", stdout);
	
	scanf("%d%d", &n, &k);
	
	for(reg int j(1); j <= k; ++j)
		for(reg int i(j); i <= n; ++i)
				dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];  //状态转移 
	
	printf("%d", dp[n][k]);
	return 0;
}
//by CaO

总结

这道题的思路很简单，但非常引人深思。要求出状态转移方程并不难，但是想要进行时间复杂度的优化，就需要在方程上利用数学推导简化计算。

事实上，我们学习这么多的算法，无论是通过数学的方式，还是通过数据结构优化复杂度，目的归根结底只有一个，就是减少计算过程中的重复搜索。

T3 统计单词个数

题意分析

给定一个字符串和一个含有 \(s\) 个词的词典，将这个字符串分成 \(k\) 个部分，并求出这 \(k\) 个部分最多可以包含多少个单词。注意：如果两个单词的首字母在原串中位置相同，那么只能选择一个。

题目思路

依旧是一道 dp 题，我们定义 \(dp(i,j)\) 为将前 \(i\) 个字符串分成 \(j\) 个部分，包含的最多单词数，那么很明显，我们可以枚举所有划分的断点 \(k\)，就可以求出 \(dp(k,j-1)+cnt(k+1,i)\)，其中 \(cnt(i,j)\) 代表区间 \([i,j]\) 的子串中包含多少词典中的单词。

状态转移方程即为：

\[dp(i,j)=\max\limits_{k\in[1,i-1]} (dp(k,j-1)+cnt(k+1,i)) \]

字符串有 \(p\) 行，一共 \(20p\) 个字符，我们可以 \(\Theta(400p^2)\) 对所有的区间 \([l,r]\) 预处理出 \(cnt(l,r)\)，然后再完成 dp。总的时间复杂度为 \(\Theta(400p^2k)\)。

注意边界状态。

代码

#include 
#include 
#define reg register
using namespace std;

int p, k, s;
int dp[201][41];  //定义 dp[i][j] 为将前 i 个字符划分为 j 份包含的最大单词数 
int cnt[201][201];  //定义 cnt[i][j] 为区间 [i, j] 中包含的单词数 
//状态转移方程为：dp[i][j] = max(dp[i][l] + dp[l + 1][j]), l = i, i + 1, ..., j 

string str, tmp;
string dict[7];

int found(int l, int r) {  //寻找区间 [l, r] 之间是否有以 str[l] 为起点的单词 
	string sub = str.substr(l, r - l + 1);
	
	for(reg int i(1); i <= s; ++i)
		if(sub.find(dict[i]) == 0)
			return 1;
	
	return 0;
}

int main(void) {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout); 
	
	cin >> p >> k;
	for(reg int i(1); i <= p; ++i) 
		cin >> tmp, str += tmp;  //拼接字符串 
	
	cin >> s;
	for(reg int i(1); i <= s; ++i)
		cin >> dict[i];
	
	for(reg int j = str.size() - 1; j >= 0; --j)
		for(reg int i(j); i >= 0; --i)
			cnt[i][j] = cnt[i + 1][j] + found(i, j);
	
	for(reg int i(0); str[i]; ++i)
		dp[i][1] = cnt[0][i];
	
	for(reg int i(1); i < k; ++i)
		dp[i][i + 1] = dp[i - 1][i] + cnt[i][i];  //设置边界状态 
	
	for(reg int i(0); str[i]; ++i)
		for(reg int j(1); j <= k && j < i; ++j)
			for(reg int l(j); l < i; ++l)
				dp[i][j] = max(dp[i][j], dp[l][j - 1] + cnt[l + 1][i]);  //状态转移 

	printf("%d", dp[str.size() - 1][k]);
	return 0;
}
//by CaO

T4 Car 的旅行路线

题意分析

在 Decartes 坐标系中存在 \(S\) 个矩形，Car 可以在这些矩形的顶点上移动：

• 对于第 \(i\) 个矩形，从这个矩形上的一个点移动到另一个点，若距离为 \(d\)，那么她就要耗费 \(t_i\cdot d\) 的花费，\(i=1,2,\cdots,S\)；

• 从某个矩形上的一个点移动到另一个矩形上的另一个点，若距离为 \(d\)，那么她就要耗费 \(T\cdot d\) 的花费。

Car 可以从矩形 \(A\) 上的任一个点出发，移动到矩形 \(B\) 上的任一个点上，求她需要的最小花费。

题目思路

虽然这是一道蓝题，但是思路却十分简单— —建稠密图跑 Dijkstra：因为任意两个点之间的花费都唯一确定，而且花费的值总是大于 \(0\) 的，我们考虑任意两点之间建一条双向边，双向边的权值就是两点之间的花费。于是我们就可以在图上以 \(A\) 的四个顶点为源点跑 Dijkstra 了。

这里有一些小细节：

考虑到这张图是稠密图，在不加堆优化的情况下，Dijkstra 的复杂度为 \(\mathcal{O}(|V|^2+|E|)\)，稠密图下为 \(\mathcal{O}(|V|^2)\)；加了堆优化的复杂度为 \(\mathcal{O}((|E|+|V|)\log|V|)\)，稠密图下会退化到 \(\mathcal{O}(|V|^2\log|V|)\)，反倒不如不加。

单次询问中有 \(S\) 个矩形，就有 \(4S\) 个顶点，时间复杂度为 \(\mathcal{O}(16S^2)\)，\(n\) 次询问后的复杂度为 \(\mathcal{O}(16n\overline{S^2})\)。本题中，\(n\le 10\)，\(S\le 100\)，则 \(16n\overline{S^2}\le 1.6\times10^6\)，可以轻松扫过。

每个矩形都只给了三个顶点，怎么判断第四个顶点的坐标？我们可以通过勾股逆定理求出这三个顶点中，构成直角的顶点坐标 \(A(x_1,y_1)\)，另外两个点坐标为 \(B(x_2,y_2),C(x_3,y_3)\)，那么 \(\vec{AB}+\vec{AC}=\vec{AD}\)，即：

\[(x_2-x_1,y_2-y_1)+(x_3-x_1,y_3-y_1)=(x_4-x_1,y_4-y_1) \]

有：

\[\begin{cases} x_2+x_3-2x_1=x_4-x_1,\\ y_2+y_3-2y_1=y_4-y_1. \end{cases} \]

那么第四个点的坐标就是 \((x_2+x_3-x_1,y_2+y_3-y_1)\).

代码

口胡五分钟，代码两小时……这道题的细节还是挺多的，不要漏了。

#include 
#include 
#include 
#include 
#define SQ_OF_DIS(A, B) ((x[A] - x[B]) * (x[A] - x[B])\
                        +(y[A] - y[B]) * (y[A] - y[B]))
#define reg register
using namespace std;
const int maxN = 50001;

int n, s, t, A, B;
int top, head[501];

//状态压缩，对于编号为 i 的节点，i >> 2 代表其所在城市的信息，i & 3 代表机场的编号 
struct Point {
	int x, y;
	double dis;
	bool vis;
} point[501];  //统计机场的信息 

struct Edge {
	int to;
	double w;
	int next;
} edge[maxN];

inline void add_edge(int u, int v, double w) {
	edge[++top].to = v;
	edge[top].w = w;
	edge[top].next = head[u];
	head[u] = top;
}

inline double getDis(int M, int N) {
	return sqrt(pow(point[M].x - point[N].x, 2) + pow(point[M].y - point[N].y, 2));
}  //两点间距离函数 

inline void getOther(int x[], int y[]) {  //给定其中三个点，求出矩形第四个点 
	if(SQ_OF_DIS(0, 1) == SQ_OF_DIS(0, 2) + SQ_OF_DIS(1, 2)) {
		x[3] = x[0] + x[1] - x[2];
		y[3] = y[0] + y[1] - y[2];
	}
	
	else if(SQ_OF_DIS(0, 2) == SQ_OF_DIS(0, 1) + SQ_OF_DIS(2, 1)) {
		x[3] = x[0] + x[2] - x[1];
		y[3] = y[0] + y[2] - y[1];
	}
	
	else if(SQ_OF_DIS(1, 2) == SQ_OF_DIS(1, 0) + SQ_OF_DIS(2, 0)) {
		x[3] = x[1] + x[2] - x[0];
		y[3] = y[1] + y[2] - y[0];
	}
}

int main(void){
	freopen("travel.in", "r", stdin);
	freopen("travel.out", "w", stdout);
	
	scanf("%d", &n);
	
	while(n--) {
		top = 0;  //一定不要忘了清空多测！！！ 
		memset(head, 0, sizeof(head));
		memset(edge, 0, sizeof(edge));
		memset(point, 0, sizeof(point));
		
		scanf("%d%d%d%d", &s, &t, &A, &B);
		
		for(reg int i(0); i < (s << 2); ++i)
			point[i].dis = 1e+10;  //初始化 
		
		for(reg int i(0); i < 4; ++i)
			point[(A - 1) << 2 | i].dis = 0;
		
		int cur = (A - 1) << 2;
		for(reg int i(0); i < s; ++i) {
			int x[4], y[4], ti;
			
			for(reg int j(0); j < 3; ++j)
				scanf("%d%d", &x[j], &y[j]);
			scanf("%d", &ti);
			
			getOther(x, y);
			
			for(reg int j(0); j < 4; ++j) {			
				point[(i << 2) | j].x = x[j];
				point[(i << 2) | j].y = y[j];
				
				for(reg int k(j - 1); k >= 0; --k) {
					add_edge((i << 2) | j, (i << 2) | k, ti * getDis((i << 2) | j, (i << 2) | k));
					add_edge((i << 2) | k, (i << 2) | j, ti * getDis((i << 2) | j, (i << 2) | k));
				}
			}
		}
		
		for(reg int i(0); i < (s << 2); ++i)
			for(reg int j(0); j < (s << 2); ++j) {
				if(i >> 2 == j >> 2) continue;
				add_edge(i, j, t * getDis(i, j));
			}
		
		//Dijkstra 算法求出最短路，稠密图中选择不加堆优化 
		while(!point[cur].vis) {
			double mindis = 1e+10;
			point[cur].vis = true;
			
			for(int ptr = head[cur]; ptr; ptr = edge[ptr].next) {
				int curv = edge[ptr].to;
				point[curv].dis = min(point[curv].dis, point[cur].dis + edge[ptr].w);
			}
			
			for(reg int i(0); i < (s << 2); ++i)
				if(!point[i].vis && point[i].dis < mindis)
					cur = i, mindis = point[i].dis;
		}
		
		double ans = point[(B - 1) << 2].dis;
		
		for(reg int i(1); i < 4; ++i)
			ans = min(ans, point[(B - 1) << 2 | i].dis);
		
		printf("%.1lf\n", ans);
	}
	return 0;
}
//by CaO

总结

尽管作为 NOIP2001 TG 的最后一道题，它的思维并不难，但是它的计算几何方面的处理以及建图都是非常锻炼码力的，这也是为什么我一直推荐刷一刷早年的 NOIP 题的原因— —近年 OI 题目的趋势开始向思维和代码难度双提升的方向发展，只有既将算法烂熟于心，又稳步提升代码能力，才能在风云变幻的 OI 圈中屹立不倒。