概述

简单的测试题3是完整的NOIp Senior，分2天，目前只有PDF版本的题目，所有文件在https://github.com/zhzh2001/Learning-public/tree/master/test上公开。

另外，借助pdf2htmlEX，题目和题解转为HTML版本：

• day1
  • solution
• day2
  • solution

可以尝试在这里提交：fact core_region

1.数列

概述

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

非正解

测试点#1~#3

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

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

期望得分:30

离线方法

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

链表维护

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

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

期望得分:40

std::vector维护

std::vector也可以用来维护数列，其中修改尾部和随机访问操作是$O(1)$的，修改首部操作是$O(n)$的(但是比数组快，有人认为接近于$\sqrt n$)。

期望得分:60(其中测试点#8就利用了std::vector的快速修改首部操作)

分段骗分

综合一个数列、链表和std::vector，按照测试点特征选择方法，其中有的测试点可以用多种方法通过。

期望得分:80(很良心吧)

题目概览

名称

时限仅供参考，请以标程运行时间计算

前言

在算法竞赛中，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优化的方向。我们通常优化了时间，但是也降低了通用性。

思路

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

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

思路

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

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

思路

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

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

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

思路

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

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

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

1.穿越马路

30%

$C,N\le10$

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

60%

$C,N\le500$

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

题目来源或改编自USACO月赛，顺序与难度无关。

题目概述

注意事项

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