全国赛09.集训队试题

1、-青少年信息学中国国家队训练2010-2011竞赛时间：待定提交源程序须加后缀注意：最终测试时，所有编译命令均不打开任何优化开关。对于 Pascal 语言stock.pascolor.pasequation.pas对于 C语言stock.ccolor.cequation.c对于 C+ 语言stock.cppcolor.cppequation.cpp题目名称的数颜色的等式目录stockcolorequation可执行文件名stockcolorequation输入文件名标准输入标准输入标准输入输出文件名标准输出标准输出标准输出每个测试点时限1s0.6s1s测试点数目202020每个测试点分值555

2、是否有部分分N/AN/AN/A题目类型传统型传统型传统型的【问题描述】的热爱炒股，她要求为她编写一个软件，的走势。折线图是具，它通过一张时间与数图像清晰地展示了 经过长时间的观测，某只未来的必备工的价位的函 的走势情况。发现很多都有如下的规律：之前的走势很可能在短时间内重现！如图可以看到这只A 部分的股价和 C 部分的股价的走势如出一辙。通过这个观测，认为他可，他本能找到了一个未来走势的方法。进一步的难住了想试图统计 B 部分的长度与发生这种情况的概率关系，不过由于数据量过于庞大，依赖人脑的力量难以完成，于是找到了编程的你，请你帮他找一找给定重现的间隔（B 部分的长度），有多少个时间段满足首尾

3、部分的走势完全相同呢？当然，首尾部分的长度不能为零。【输入格式】输入的第一行包含两个整数 N、M，分别表示需要统计的总时间以及重现的间隔（B 部分的长度）。接下来 N 行，每行一个整数，代表每一个时间点的股价。【输出格式】输出一个整数，表示满足条件的时间段的个数【样例输入】12 41 2 3 4 8 9 1 2 3 4 8 9【样例输出】6【样例说明】6 个时间段分别是：3-9、2-10、2-8、1-9、3-11、4-12。【数据规模】对于 20%的数据， 4N100。对于 40%的数据， 4N5000。对于 100%的数据，4N50000 1M10 MN 所有出现的整数均不超过 32 位含符

4、号整数。时间限制：1s【解题】题目大意：给定一个由整数组成的序列，求出满足下列要求的（连续）子序列的个数。1、子序列由 ABC 三个相邻部分组成。2、A 部分的长度与 C 部分相等。3、对于 A 部分中任意相邻两项的差与 C 部分中任意相邻两项的差相等4、B 部分的长度给定，但是很小（小于等于 10）本题乍看起来直接按题目描述处理显然较不清晰，可以把原串修改一下。为了描述方便，不妨把原序列称之为 S1，S2SN。将每一项减去前一项，可以得到 S2-S1，S3-S2SN-SN-1。可以称为序列SN。那么原题就转换成了求新序列SN中满足形式类似与 PQP 的子序列的个数，并且|Q|的给定。做完了这

5、个转换工作，乍看之下问题似乎还是难以解决，下面介绍几个此题的做法，分别可以得到不同的分数。方法 1：看到这个形式的问题第一反应就是首先枚举 Q 的位置，然后再枚举 P 的长度，然后检查然后检查对应位置是否匹配。这种做法非常直观，不过时间效率较低，情况下为 O(N3)，期望得分 20 分。方法 2：方法一十分低效因为它做了了许多无用功。对于一中第三步的检查对应位置是否匹配，有许多现成的算法可以使用。很容易可以看出，这个过程的本质就是在计算 P2 与 P1 每一个位置的的 LCP（最长公共前缀）！这个过程很容易可以使用后缀数组优化而做到询问 O(1)回答。不过由于需要枚举 Q 的位置和 P 的长度

6、，时间复杂度仍然只能达到 O(N2)。这样可以使用 O(N2)的动态规划来代替后缀数组来优化编程复杂度。期望得分 4050 分。方法 3：方法 2 的瓶颈是枚举 P 的长度与 Q 的位置，不过按照这个思路继续下去似乎难以优化掉这两重循环，不得不另寻更为巧妙的方法。对于这种性序列上的组合计数问题，很容易想到一个工具：分治！。分治算法在形如快速排序等地方能顺利优化算法，尝试将其运用至本题中。不妨设过程 F(Left,Right)可以统计在区间Left,Right中满足条件的子序列的个数。设Mid 为区间Left,Right的中点由于分治执行，Left,Mid,Mid+1,Right中的子序列，剩下

7、的不需要统计那些属于分两种情况。1、点 MidQ。这种情况由于|Q|非常小，可以直接枚举 Q 的位置，然后使用方法 2 中的算法解决这个问题，此时算法多了一个系数 M，不过整体仍然可以在 O(NMLogN)的复杂度内完成。点 MidQ，这种情况就比较麻烦了，可以表示成如下示意图：2、由于 Mid 的存在，P2 被分割成了 3 份，由于 P1=P2，把 P1也分割成 3 份，经过仔细观察，发现只需要枚举红线的位置即可解决此部分的统计问题。黄色部分的最大匹配值可以通过将整个 Mid 左面的部分倒置后求 LCP。而 Mid 以及绿色部分的匹配值可以直接通过后缀数组+RMQ 求的。知道了绿色与黄色部分

8、的最大值后，那么 Q 的位置个数也可以相应得出，问题得到解决，此部分复杂度为 O(NLogN)。方法三总复杂度为 O(NMLogN)，为一个非常优秀的算法。由于后缀数组配合 RMQ 代码较长，在标程中我使用了扩展 KMP 算法来代替后缀数组实现，而扩展 KMP 时间复杂度为 O(N)，不影响整体复杂度。数颜色【问题描述】了一套 N 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答的提问。会像你发布如下指令：1、Q L R 代表询问你从第 L 支画笔到第 R 支画笔笔。2、R P Col 把第 P 支画笔替换为颜色 Col。有几种不同颜色的画为了满足的要求，你知道你需要干什么了吗？【输入

9、格式】第 1 行两个整数 N，M，分别代表初始画笔的数量以及个数。第 2 行 N 个整数，分别代表初始画笔排中第 i 支画笔的颜色。会做的事情的第 3 行到第 2+M 行，每行分别代表分。会做的一件事情，格式见题【输出格式】对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第 R 支画笔有几种不同颜色的画笔。【样例输入】6 51 2 3 4 5 5Q 1 42 61 2Q 1 4Q 2 6【样例输出】4434【数据规模】对于 40%数据，只包含第一类操作（无修改操作），且。除此之外的 20%的数据，N，M1000对于 100%的数据，N10000，M10000，修

10、改操作不多于 1000 次，所有的输入数据中出现的所有整数均大于等于 1 且不超过 106。时间限制：0.6s【解题】题目大意：给定一个序列，设计一种数据结构，需要支持：1、修改一个数字。2、询问一个区间内有多少个互不相同的数字。这是一道数据结构题，数据结构题一般来说代码量较大，而给分又有明显的阶段性，可以从数据规模处获得一些解题的想法，下面就此。对于 20%的小数据，只要朴素地用数组来模拟操作就可以了。40%的数据：对于原来的序列没有任何的修改操作，这就给了做数据结构题的一些提示：可以离线来回答这些询问！离线回答询问的好处就是可以对那些询问排序。可以这样思考，一个出现的权值为在只要让在回答每

11、个询问时，询问的区间中每种数1，否则为 0，这样就可以用线段树或者树状数组等工具来这个和，这里我使用的是树状数组。离线的建立事件点：就是这样，来看看具体如何解决：1、对于原始序列中的每一个数，分别建立一个事件，事件点为这个数在序列中的位置，发生这个事件时查询这个数字之前有没有入过树状数组（将这个数所在的位置的权值+1）。如果相同的数字之前插入过树状数组，那么2、对于每一个询问操作，其删除（将这个数所在的位置的权值-1） 询问区间的末端点作为这个事件的时间，然后直接在树状数组中查询此区间中所有数字的和。不难发现在这个区间中，对于相同的数，只有最后一个数字的权值为 1，其他的权值都是零。40 分得

12、到解决。对于满分算法，须首先设计一种支持询问的方法，可以这原数列做一个转换，对于原数列中的数 Si，样做：它转换为最大的 j(ji)，使得 Si=Sj。如果不存在这样的 j，那么令其为-1。这样的转换显然是可以再线性时间内完成的。作了这样的转换以后，惊讶的发现这时我们要查询L,R内有多少不同的数，只要看在新序列中的对应区间内有多少数字小于 L（说明这些数上次出现的位置不在区间L,R中，也就是说是第一次回答提问了。而询问一个区间内有多少数字小于 L出现），这样就能这个问题是个经典的线段树应用：建立一颗线段树，线段树的每个节点中储存一个数组，数组内将该节点所代表的区间中的数从小到大排序，不难发现这

13、颗线段树可以用类似归并排序的方法建立，这样对于询问，数字小于 L，然后相加即可。但是本题有修改操作，如果就可以在每个区间二分，看看有多少要修改序列中数字，只要将节点中的数组修改为平衡树。你还需要得知一个点的之前的与其相同点是多少，同样可以使用平衡树来。最终使用类似线段树的方法完成，将数据结构变为树套树的结构。本题最终在 O(NLog2N) 的时间复杂度内完成，代码量很大，对代码编写的功底有一定的要求，思考过程也需要经过多次的转变才能得到，而且设置了几段部分分，可以说是对选手的全面。的等式【问题描述】a1x1+a2y2+anxn=B 存在非负整突然对等式很感，他正在数解的条件，他要求你编写一个程

14、序，给定 N、an、以及 B 的取值范围，求出有多少 B 可以使等式存在非负整数解。【输入格式】输入的第一行包含 3 个正整数，分别表示 N、BMin、BMax 分别表示数列的长度、B 的下界、B 的上界。输入的第二行包含 N 个整数，即数列an的值。【输出格式】输出一个整数，表示有多少 b 可以使等式存在非负整数解。【样例输入】2 5 103 5【样例输出】5【数据规模】对于 20%的数据，N5，1BMinBMax10。 对于 40%的数据，N10，1BMinBMax106。对于 100%的数据，N12，0ai4*105，1BMinBMax1012。时间限制：1s【解题】本题是本是比赛三题中

15、较为简单的一道，由于题面的描述较为简单，这里就不再复述一遍了。这是一类特殊的背包问题，还是按照不同的数据规模来讲解此题：20%的数据最为简单，使用回溯算法小，可以轻松通过大约 20%的数据。枚举所有的 ai，由于 N、b 都非常40%的测试数据也相当简单，由于 b 的数量较小，这就和平时使用的动态规划算法没有什么区别，这就是经典的不限制的背包问题，动态规划方程：Fi,j=Fi-1,j-ai or Fi,j，最后只要统计一下 Fn,j就可以得出结果了，这样就通过了 40%的测试数据。对于此类背包问题，其实还有不少的优化的技巧可以使用，这里我介绍一种区间背包的优化算法：传统的动态规划算法低效的原因

16、，是因为他没有充分利用背包问题的特性。可以发现，大部分 F 数组的组成很多情况下都是连续的，即一段都是False，一段都是 True。利用这个特点，把 F 数组的结构作如下修改：可以使用一个二元组(Left,Right)来表示Left,Right这个区间是全部为 True 的，然后 F 数组就是有很多的这样的二元组组成的数组，转移的时候也差不多，我 (Left,Right) 转 移到 (Left,Right+ai)、(Left+ai,Right+ai)、(Left+2*ai,们只要从 Right+2*ai).(Left+k*ai,Right+k*ai)，然后把相加的相并即可。这种结构对程序效率

17、的时显然的，虽然具体的时间复杂度和数据相关，但是情况要下也不会比原来的常规的动态规划来得慢，不失为一种优秀的算法。不过本题中 h 的范围比较大，而这种取巧的动态规划算法不是本题的重点。我也没有写过标程，因此无法得知其期望时间复杂度，预计效果可能不是特别理想，这里只是介绍一下这个方法。对于 100%的数据，观察数据范围可以发现 ai 的范围只有 105，这显然是本题的突破口。单纯的数论似乎对本题没有很好的效果，只能继续回到老，回想以前对于多重背包的解决方法，其运用到本题上面：可以按照模分类。设 Gi：达到背包容量模 a1 为 i 的时候，背包的容量最少是多少，不难发现吗，求出 G 的值以后，就不难得出最终的。初始值 G0=0，更新的话就是 Gi+(aj)=Min(G(i+aj) mod a1,Gi+aj)很容易想到，可以使用不停的迭代来更新 G 数组的值。直接用 For 循环来迭代效率似乎相当低下，再次类比以前的算法，发现这个和最短路算法非