1.数列

概述

维护多个数列,要求每个数列支持修改首部、尾部,支持随机访问。而且时间复杂度应该为O(1)O(1)O(logn)O(\log n)(需要卡常?)

非正解

测试点#1~#3

如果只有一个数列,那么问题就非常简单了。

只要维护一个头指针和尾指针,开始时在数组中间。这样可以轻松地插入、删除、随机访问了。

期望得分:30

离线方法

有了处理一个数列的方法,我们只需对所有操作排序,依次处理每个数列即可。

链表维护

我们可以维护nn个链表,那么插入、删除操作都是O(1)O(1)的,但是随机访问是O(n)O(n)的。

可以使用std::list,也可以自己实现链表。

期望得分:40

std::vector维护

std::vector也可以用来维护数列,其中修改尾部和随机访问操作是O(1)O(1)的,修改首部操作是O(n)O(n)的(但是比数组快,有人认为接近于n\sqrt 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/printfcin/coutfread/fwrite,Pascal中的read/writeblockread/blockwrite。也有一些低级的平台有关的I/O方式,Windows和Linux(Unix)都提供了内存映射文件,效率更加高。

在算法竞赛中,I/O通常用文本文件,而数据只有整数、浮点数和字符串三种。把十进制的字符串转换成整数或浮点数需要一定的时间,而分离出字符串也需要一定的时间,这就是I/O优化的方向。我们通常优化了时间,但是也降低了通用性

阅读全文 »

思路

这题也有很多方法,其实并不用可并堆。类似于上一种方法,计算出dfs序和每个点的深度,然后按深度降序排序。对于每个点,需要删除深度相差超过L的点,并加入当前点,在子树中统计答案。而这些用树状数组就可以了(单点修改+区间查询)。时间复杂度O(NlogN)O(N\log N)

当然,还有一种更加巧妙的方法。用倍增求出2i2^i步祖先,然后就可以找到第一个距离超过L的祖先,用差分区间加,最后就能算出答案。时间复杂度也是O(NlogN)O(N\log N),下面提供了官方题解中的这种方法的代码供参考。

阅读全文 »

思路

应该可以发现,这题可以用贪心。有两个值需要满足比较麻烦,我们考虑对询问和牧草按照口感(绿色值)排序。这样,对于一个询问(Ai,Bi),只要从口感大于等于Bi的牧草中选出价格最小的且大于等于Ai的牧草,这样可以证明是最优的。如果没有符合条件的牧草,就是无解。

用multiset来维护牧草的价格很方便,支持所有操作,当然价格可以重复。时间复杂度O(NlogN)O(N\log N)

阅读全文 »

思路

这题其实有很多方法,但是我最先想到的是按照奶牛的高度排序处理。而且这种方法也可以做被困在干草堆(金)。当然按照位置排序也是可以的。

首先按照奶牛的高度降序排序,在处理一只奶牛时,把大于等于它的高度的2倍的奶牛的位置放进set中,再判断一下set中的位置在当前奶牛两边的位置是否小于等于d,计入答案即可。

时间复杂度O(NlogN)O(N\log N),与其他方法相同,但常数比单调队列大。因为后者只要用到sort,比set常数小得多。

阅读全文 »

思路

这题要求的是带负权边的最短路,显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏O(NM)O(NM),而且众所周知,USACO总是卡SPFA的。尽管这题数据比较老,因此SPFA+SLF可以水过,但是正解并不是如此。

顺便说一下,用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解),在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中,几乎和Dijkstra不相上下。

可以发现,图有一个很强的性质:对于无向边,边权总是正的,因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通,因此把无向边联通块缩点后,得到的就是DAG。这样就可以在块内使用Dijkstra,块间利用拓扑排序更新答案。时间复杂度O(MlogN)O(M\log N)

阅读全文 »

1.穿越马路

30%

C,N10C,N\le10

这么小的数据,应该随便怎么搜索都可以吧。我没有写过。

60%

C,N500C,N\le500

直接二分图最大匹配,用匈牙利算法,应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是N3N^3的,应该很容易得到这个分。

阅读全文 »

题目来源或改编自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
部分分

注意事项

  1. 请注意题目的数据大小,根据情况适当地使用输入/输出优化。
  2. 数据范围中,如果没有说明,前面的数据满足后面的要求
  3. 对于有部分分的题目,如果你只做了其中一问,也要按照格式要求输出所有内容;否则无法保证得分。
阅读全文 »