简单的测试题 题解

1.排序

原题

USACO07MAR Gold T2:Ranking the Cows

原题范围：$n\le1000,m\le10000$

题目 官方题解 数据

题解

应该可以发现，把一对关系转换成一条边后，问题就转换成求出有向图的传递闭包。做完传递闭包后，答案就等于$\frac {n*(n-1)/2}2$-联通的点对数。当有向图中出现环时，即为自相矛盾。

考虑如何计算传递闭包：

Floyd

使用$f_{i,j}=f_{i,j}\lor(f_{i,k}\land f_{k,j})$，其中$k,i,j\in 1\ldots n$计算。当然，初始值为$f_{i,j}=\begin{cases}true&i=j\\ false &i\ne j\end{cases}$。

最后统计答案时注意减去自环，同时判断是否有环。

这样时间复杂度时$O(n^3)$的，可以得到30分。

压位优化

用$T_i^k$表示从i经过前k个点能到达的点的集合，则有

$$T_i=\begin{cases}T_i^{k-1}&k\notin T_i^{k-1}\\T_i^{k-1}\cup T_k^{k-1}&k\in T_i^{k-1}\end{cases}$$

使用std::bitset或者手动压位，时间复杂度为$O(\frac{n^3}w)$，可以得到60分。

拓扑序

如果原图不是DAG，则自相矛盾，否则进行拓扑排序。倒着枚举拓扑序中的点u，那么u的可达点集为u可以直接到达的点的可达点集取并。

实际上不需要求出拓扑排序，只要dfs就可以解决了，时间复杂度$O(nm)$，可以得到60分。

压位后时间复杂度为$O(\frac{nm}w)$，可以得到100分。

总结

预期难度：普及+/提高

作为T1还是比较简单的，因为省选讲过。

2.录制

原题

USACO14JAN Silver T3:Recording the Moolympics

原题范围：$n\le150,k=2$

题目 官方题解 数据

题解

k=1

当只有一台录像机时相对比较简单，你应该录制的下一个项目总是最早结束并且还没有开始的。

这样显然时最优的，因为这样有更大的机会能录制后面的项目。所以只要按结束时间排序后贪心即可，时间复杂度$O(n\log n)$。

当然也可以使用动态规划，方程$f_i=f_j+1$，其中$t_j\le s_i$，时间复杂度$O(n^2)$。

k=2

很遗憾，如果直接运行两次上述贪心的答案并不正确。以下是一个简单的反例：

1
2
|-| |-| |---------|
|---------| |-| |-|

其中-表示项目的时间，第一次贪心选择了短的那些项目后，就不能同时选择两个长的项目了。而最优方案为上图描述。

但是仍然可以用动态规划，用二维的状态，并且强制选择的项目必须在当前状态的两个节目都没有开始前结束。这样可以避免重复，时间复杂度$O(n^3)$。

实际上，贪心也是可以做的，仍然按照结束时间排序，记录最后一次录制的项目结束时间。

• 如果一个项目在两台录像机的节目都没结束前开始，显然不能安排。
• 如果这个项目只能在一台录像机上录制，就在这台录像机上录制。
• 否则，贪心地选择在结束时间迟的录像机上录制。

因为选择排在后面的项目不会比当前项目更优，所以可以证明其正确性。

更普遍的情况

当$k\le n$时，仍然可以使用动态规划，只不过时间复杂度为$O(n^{k+1})$，空间复杂度$O(n^k)$，实际无法接受。

然而，贪心很容易推广到$k\le n$的情况。维护所有录像机上最后一次录制的项目结束时间，对于每个项目，找到所有录像机结束时间中最大的小于等于开始时间的，将其更新为结束时间。如果没有找到，则不能安排这个项目。

用平衡树来维护所有录像机的结束时间，可以在$O(\log k)$的时间内完成上述操作。使用std::multiset就很方便(结束时间可能有重复)，先用upper_bound找到第一个大于开始时间的位置，再–就得到了最后一个小于等于开始时间的位置。把这个值删除，并插入新的值即可。这样时间复杂度为$n\log n+n\log k=O(n\log n)$。

记录方案

使用动态规划很容易记录方案，只要在转移时同时维护方案即可。

贪心也很容易记录，在维护结束时间的同时，记录这个时间对应的录像机编号。在更新时把项目编号记录到对应的录像机编号中即可，用std::vector或边表。

总结

预期难度：普及+/提高

主要考察了贪心，以及STL的运用。实际上USACO银组使用set非常常见，虽然原题不用。

3.加法解释

原题

USACO17OPEN Platinum T3:COWBASIC

与原题完全相同

题目 官方题解 数据

题解

对于没有嵌套的数据，直接模拟即可。而只有一个变量的情况也可以一些方法通过。下面考虑普遍的情况：

实际上，将一段代码重复运行若干次可以使用通项公式。但是这种方法逻辑上比较复杂，而且还需要逆元，具体请参见官方题解。

更简单的方法是使用矩阵，因为矩阵本来就用来解决这类问题。例如循环$x=ax+b​$，构造初始矩阵$V=\begin{pmatrix}x\\1\end{pmatrix}​$，转移矩阵$M=\begin{pmatrix}a&b\\ 0&1\end{pmatrix}​$，则$MV=\begin{pmatrix}a*x+b*1\\0*x+1*1\end{pmatrix}​$，既然$M​$表示一次循环，则$M^n​$就可以表示n次循环。而$M^n​$只要用矩阵快速幂求即可。

普通的赋值语句则可以用矩阵乘法实现，十分方便。这样，只要记录所有变量和1，按照程序构造矩阵，最后输出要求的变量的值。使用std::map来标记变量名的序号也很方便。

循环嵌套用栈来实现，保存临时矩阵和循环次数。当有新的循环时，压入一个单位矩阵；循环结束时，执行完矩阵快速幂后与下一层相乘。

每个循环最多计算$\log_210^5\sim17$次100x100的矩阵乘法，最多有50个循环。实际运算量不到1亿，注意以下常数问题就可以通过了。

另外，语法分析也比较麻烦，充分利用空格是很方便的。

总结

预期难度：提高+/省选-(洛谷的难度偏高)

这题还是比较巧妙的，因此在原题和这里都作为T3。需要认真思考，熟练应用矩阵，并且一定的代码实现能力。

4.新挑战*

题解

思路

测试点#1直接std::sort就可以了。如果内存足够，那么测试点#2也只要如此就可以了。由于内存不够，我们需要使用外部排序。测试点#3内存足够开2个数组了，但是直接std::sort太慢了，我们需要使用浮点数基数排序。

外部排序就是把数据分成若干段，每段都在内存中排序后写入临时文件。然后执行多路归并，最好用堆维护最小值。这样时间复杂度仍然是$O(n\log n)$的，只是文件读写需要额外的时间。实际上，用二进制文件保存，总共只要读40MB写40MB，使用缓冲区技术，还是很快的。

基数排序就是用冬令营的松式基排，参考洛谷上的题解，排序2亿个32位整数都不在话下。关键在于如何把浮点数转换为整数。实际上，我们使用的浮点数都有一个很强的性质：如果符号相同，那么除去符号位外剩余的位解释成整数，其大小关系等价于原数的绝对值大小关系。也就是说，32位浮点数可以与32位整数一一对应，除了-0和NaN外。具体的，浮点数相当于整数原码，转为补码后把符号位取反就是32位无符号整数了。

实际上，这题考察了相当多的技巧：

动态分配内存

由于不同的测试点内存限制不同，就需要根据数据规模动态分配内存。实际上，C/C++/Pascal中都有相关的方法。另外，作为一种好习惯，用完这些内存后，应该在堆上释放空间。

C通常用malloc或calloc来分配内存，前者不初始化空间，而后者初始化为0.用free来释放空间。具体的介绍可以自己查阅资料。

1
2
3
4
#include<stdlib.h>
void* malloc( size_t size );
void* calloc( size_t num, size_t size );
void free( void* ptr );

C++用new来分配内存，用delete来释放，比C更加方便。例如

1
2
3
float *a=new float [n];
//do something
delete [] a;

Pascal除了用new/dispose来动态分配单个对象外，还可以用GetMem/FreeMem来分配内存块。

1
2
procedure Getmem(out p: pointer; Size: PtrUInt);
procedure Freemem(p: pointer; Size: PtrUInt)

执行转换

在浮点数基数排序中，我们需要把浮点数转换为整数，或者反着转换，要求其位表示相同。除了用指针外，更加有趣的方法使用C/C++中的union或Pascal中的变体记录。

union与struct类似，只不过每次只能保存一种值，用来转换最为方便。例如

1
2
3
4
5
6
7
8
9
10
union
{
	unsigned ul;
	float ft;
}u;
u.ft=readNext();
a[i]=u.ul;
//do something
u.ul=a[i];
writeNext(u.ft);

此外，C++中的关键字reinterpret_cast也可以转换，但好像有些问题，请不要使用。

变体记录与union类似，例如

1
2
3
4
5
6
7
8
type
  union=record
  case boolean of
  false:(x:longint);
  true:(ft:single);
  end;
var
  u:union;

二进制文件

在外部排序中，我们需要用二进制文件来保存临时结果。

在Pascal中很方便，只要用file of single类型即可，而且可以直接用read/write，不过必须手动指定文件名。

而在C/C++中，用fread/fwrite更加方便，而且文件打开模式中必须有”b”，如tmpfile函数就使用了”wb+”模式。设置缓冲区也很有用，能减少I/O次数，提高效率。以下代码演示了临时文件的使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int main()
{
	FILE *f=tmpfile();
	if(!f)
		return 1;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		fwrite(&i,sizeof(i),1,f);
	rewind(f);
	while(!feof(f))
	{
		int x;
		fread(&x,sizeof(x),1,f);
		if(!feof(f))
			cout<<x<<' ';
	}
	cout<<endl;
	return 0;
}

使用STL中的堆算法

C++用std::priority_queue可能会出现奇怪的问题，内存也可能会太大。建议使用STL中的堆算法。

1
2
3
4
5
6
7
8
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last,
                Compare comp );
template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last,
                Compare comp );
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );

具体的介绍可以自行查阅资料。

总结

预期难度：提高+/省选-(仅代码)

这题考察了对于综合性问题的解决，难度较大，需要阅读分析给定的资料。

这题的灵感来自《深入理解计算机系统》中的解释，其实网上也有类似的内容，不过我是根据资料自己推出公式的，从想法到最终实现用了大约一个星期。

这不是偶然的——IEEE格式如此设计就是为了浮点数能够使用整数排序函数进行排序。当处理负数时，有一个小的难点，因为它们有开头的1，并且它们是按照降序出现的，但是不需要浮点运算来进行比较也能解决这个问题（参见家庭作业2.84）。

——摘自《深入理解计算机系统》第2章：信息的表示和处理