资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解题思想1 显然，此题可以用排序的方法来解决，根据n的范围，可以看出，O(nlogn)的算法是可以接受的。,解题思想2 维护一个二叉树，以数的大小作为节点的权值，以数的重复次数作为节点的附加信息。之后中序遍历即可。 看起来，树内的节点个数应该不到n，所以可能表现不错，其算法复杂度依然为O(nlogn),实际数据规模 挺小的，全部数据都是送分的。,1,分析 这个题目实在不能说是一道TG组的好题。实际上，个人认为题目最大的意义在于：提供了10个测试排序算法的不怎么特别好的数据。话说回来，此题是送分题，但是送分题送的这么水，考察的也就只有OIers的细心程度了。在考试的时候，要相信有简单的题目，要相信有直接的算法。在我的身边就有几个同学因为这个题目与一等失之交臂，这是最可惜的事情。,2,第二个题目 expand题目转述 给定一个字符串，如果某个-左边同为数字或同为字母，并且右边的Ascii码严格大于左边的Ascii码，则在原串中删去-，并在该位置上插入左右字符之间的字符。其中插入字符有3个参数。参数p1=1 = 字母为小写 =2 = 字母为大写 =3 = 字母、数字都用*代替参数p2 = 同一字母填充的个数参数p3 =1 按ascii递增填充， =2 按ascii递减填充。其中原串的长度不大于100。,3,解题思想 直接模拟，按照题目的大意转述即可。代码复用率要尽量高一些。尽量直接读入之后输出。,实际数据规模 数据规模不大，但是各种情况都考虑了一些。,分析 该题目实在是为了提高总分而用的。测试数据没有保证第一位不是-,4,第三个题目 game题目转述 给出一行m个有序的数，每次取数可以从左端或右端取，第i次取数的权值为2i，每次取出的数的值乘上权值累加，使得总得分最大。游戏进行n次。n,m=80，操作的数FB，则FBCEAG，ecc=maxBF,ID。也就是说，如果路径和公共段有交集，实际计算max时，只需要计算路径在公共段上的部分的ecc，然后和公共段两端的路径长取一遍MAX就行了。,10,下面证明，使得ecc取到最小的core必然和公共段有交集。设没有交集，则必然有一条直径和这个core没有交集，此core的ecc就至少严格大于公共段长度+除去公共段的半条路径长度，然而，公共段上的点到其他点的最长距离，最大不会大于这个长度，这与ecc最小矛盾！通过上面的论述，得出core只与公共段有关，也就是说引理成立。所以在计算时任选一条直径即可，因为任意一条路径都覆盖了公共段。到了这里，写出O(N2)的算法应该不难了。通过一次DFS，可以求出所有点之间的连通路。此算法类似LCA，复杂度为O(N2*A)，其中A=ECC(B)，所以尽量沿直径伸展core即可，直到不能向前伸展（长度超过了s）。这类似于凸包求最远点对。实现时维护首尾指针统计即可。这样的实现是O(n)的。,12,
展开阅读全文