概述
简单的测试题3是完整的NOIp Senior,分2天,目前只有PDF版本的题目,所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。
另外,借助pdf2htmlEX,题目和题解转为HTML版本:
可以尝试在这里提交:fact core_region
简单的测试题3是完整的NOIp Senior,分2天,目前只有PDF版本的题目,所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。
另外,借助pdf2htmlEX,题目和题解转为HTML版本:
可以尝试在这里提交:fact core_region
维护多个数列,要求每个数列支持修改首部、尾部,支持随机访问。而且时间复杂度应该为O(1)或O(logn)(需要卡常?)
如果只有一个数列,那么问题就非常简单了。
只要维护一个头指针和尾指针,开始时在数组中间。这样可以轻松地插入、删除、随机访问了。
期望得分:30
有了处理一个数列的方法,我们只需对所有操作排序,依次处理每个数列即可。
我们可以维护n个链表,那么插入、删除操作都是O(1)的,但是随机访问是O(n)的。
可以使用std::list,也可以自己实现链表。
期望得分:40
std::vector也可以用来维护数列,其中修改尾部和随机访问操作是O(1)的,修改首部操作是O(n)的(但是比数组快,有人认为接近于√n)。
期望得分:60(其中测试点#8就利用了std::vector的快速修改首部操作)
综合一个数列、链表和std::vector,按照测试点特征选择方法,其中有的测试点可以用多种方法通过。
期望得分:80(很良心吧)
项目名称 | 数列 | 斐波那契数的长度 | 区间质数 | 新挑战 |
---|---|---|---|---|
英文名称 | list | fiblen | prime | newchal |
可执行文件名称 | list.exe | fiblen.exe | prime.exe | newchal.exe |
输入文件 | list.in | fiblen.in | prime.in | newchal.in |
输出文件 | list.out | fiblen.out | prime.out | newchal.out |
每个测试点时限 | 3s | 1s | 1s | 1s |
内存限制 | 512MiB^size | 512MiB | 16MiB | 512MiB |
测试点数量 | 10 | 10 | 10 | 10 |
每个测试点分值 | 10 | 10 | 10 | 10 |
时限仅供参考,请以标程运行时间计算
在算法竞赛中,I/O有时是影响效率的瓶颈。I/O优化可以被模板化,与具体问题无关,是常数优化的重要方式之一。看到网上有很多关于这方面的文章,我也想来自己研究一下。
NOI系列目前支持的语言有C,C++和Pascal,其中C++可以直接使用C的绝大多数功能(但也有例外),因此下面只考虑C++和Pascal两种语言。通常,每种语言都提供了几种平台无关的I/O方式,如C++中的scanf/printf,cin/cout,fread/fwrite,Pascal中的read/write,blockread/blockwrite。也有一些低级的平台有关的I/O方式,Windows和Linux(Unix)都提供了内存映射文件,效率更加高。
在算法竞赛中,I/O通常用文本文件,而数据只有整数、浮点数和字符串三种。把十进制的字符串转换成整数或浮点数需要一定的时间,而分离出字符串也需要一定的时间,这就是I/O优化的方向。我们通常优化了时间,但是也降低了通用性。
这题要求的是带负权边的最短路,显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏O(NM),而且众所周知,USACO总是卡SPFA的。尽管这题数据比较老,因此SPFA+SLF可以水过,但是正解并不是如此。
顺便说一下,用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解),在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中,几乎和Dijkstra不相上下。
可以发现,图有一个很强的性质:对于无向边,边权总是正的,因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通,因此把无向边联通块缩点后,得到的就是DAG。这样就可以在块内使用Dijkstra,块间利用拓扑排序更新答案。时间复杂度O(MlogN)。
题目来源或改编自USACO月赛,顺序与难度无关。
项目名称 | 穿越马路 | 2048 | 瓶颈 | GPS的决斗 |
---|---|---|---|---|
文件名 | helpcross.* | 2048.* | bottleneck.* | gpsduel.* |
时间限制 | 1s | 2s | 1s | 3s |
空间限制 | 512MB | 512MB | 512MB | 512MB |
优化选项 | 无 | 无 | 无 | -O2 |
测试点数量 | 10 | 20 | 10 | 10 |
测试点分数 | 10 | 5 | 10 | 10 |
比较方式 | SPJ | 全文 | 全文 | SPJ |
部分分 | 有 | 无 | 无 | 有 |