2011年省赛选拔之个人代码能力检测解题报告

2011年省赛选拔之个人代码能力检测-by zhendeluzi

A) Surprising Strings

考虑到数据量比较小,可以直接暴力判断每个可能的D。
对于给定的D,生成所有的D-pair,放在一个容器里面,然后问题就在于判断这个容器有没有重复元素。
可以先sort这个容器然后使用unique函数,判断unique后的有效元素(unique返回最后一个有效元素的迭代器)个数跟unique之前是否相等即可。

D = O(n)。
sort的时间复杂度为O(nlogn),unique的时间复杂度为O(n)。

所以总的时间复杂度 = O(n * nlogn)

B) Compound Words

题目没有给出字符串的长度所以复杂度不是很好估计。
假设字符串长度m = 20。那么可以用以下算法来解决:

首先用数组A存储所有的字符串。

对于每个字符串都判断一次它是否可以由两个其他字符串组成:
1、将所有的字符串拆分成两半(O(m))
2、然后分别判断拆分后的前半部分和后半部分是否存在于A中。(复杂度1)
3、如果2中两次判断均存在,则这个字符串可以由其他两个字符串组成。

于是总的复杂度 = O(m * n * 复杂度1)

现在问题的关键就在于复杂度1,对于字符串检索,效率最高的无疑是trie或者hash表,二者均为O(m),稍低一点的可以用map容器或者stl函数binary_search,二者复杂度均为O(m * nlogn)的预处理+O(m * logn)的查询。

所以总的时间复杂度 = O(m ^ 2 * n)或者O(m ^ 2 * nlogn)

C) Choose Your Words Carefully

1、每次都读入一个string(读入字符串时会使用空白符(空格、Tab、换行等)作为分隔符,考虑到这些空白符均不属于words,因为可以这样读入)。
2、然后遍历这个string,一旦碰到非数字字母的字符(或到达字符串结尾),就把之前遍历过的字符串temp的出现次数增加1,同时将temp置空。
统计次数时可以使用map,每次修改次数的复杂度为logn。
3、然后遍历一遍map找出最多的出现次数,输出<n> occurences
4、再次遍历map输出次数等于n的字符串。

由于map内部是二叉搜索树(大多数实现是红黑树),因此遍历过程中的字符串就是按照字母序的,无需再次排序。

设整个文本长度为n,单词个数为m(m <= n),则:
统计字符串时的时间复杂度 = O((n / m) * logm),统计次数时的时间复杂度 = O(nlogn)

因为n总是不小于m的,
所以总的时间复杂度 = O(nlogn)

D) Three Sides Make a Triangle

.... 没过= =
解题报告传送门:/acmhome/solutionReportList.do?&method=solutionReportDetail&id=30

E) Digits

首先,x1是一个整形,x0作为字符串输入即可。然后按照递推公式递推下去。
具体实现时可以需要对x0 = 1做特判。

由于{x}数列是按照log10递减的,因此:

总的时间复杂度 = O(log(10, x0))

F) Image Transformation

将r、g、b值读入后,灰度值 = (r + g + b) / 3,按照格式输出即可。

时间复杂度 = O(n * m)

G) Filling Out the Team

读入速度、重量、力量值,然后按照题目要求输出即可。

时间复杂度 = O(1)

H) 无限的路

对于给定的两个点p1、p2,如果二者在同一条线上,使用两点距离公式计算出距离输出。
如果二者不在同一条线上,我们假设p1是起点p2是终点:

1、求出p1右下方的点P1(p1.x + p1.y, 0);
2、求出p2左上方的点P2(0, p2.x + p2.y);
P1, P2之间有P2.y - P1.x - 1条45°的直线,他们的长度分别为l1 = sqrt(2) * k (k = P1.x + 1...P2.y - 1)
P1, P2之间有P2.y - P1.x条从(P1.x, 0)到(0, P1.x + 1)的直线,他们长度分别为l2 = sqrt(k + (k + 1) * (k + 1)) (k = P1.x ... P2.y - 1);

最后结果为l1 + l2 + dist(p1, P1) + dist(p2, P2),其中dist(x, y)表示x、y的直线距离。

时间复杂度 = O((x2 + y2) - (x1 + y1))

I) Find the Clones

使用map统计每个字符串出现的次数,然后再用map统计每个次数出现了多少次,最后输出即可。

设字符串长度为m,则:

时间复杂度 = O(m * nlogn)

J) Java vs C++

类似于C题,把变量名拆分为多个单词,然后拆分的过程中,如果出现了_,就记录变量名是c风格的,如果出现了大写字母就记录变量名是java风格的。
最后如果变量名既是c风格又是java风格则输出Error,否则一个单词一个单词输出。
如果要输出为c风格的,就在除了第一个单词以外的单词之前加上下划线;
如果要输出为java风格的,就把输了第一个单词以外的单词的首字母改成大写。

我不清楚数据里面有没有类似于a____b这样的,在拆分变量名为单词的过程中(参考C题),如果temp为空的时候遇到了分隔符,则直接输出Error来处理这种情况。
对于____这种,如果最后words数组为空,则输出Error。

另外,拆分变量的时候,如果碰到大写字母,要把temp初始化为这个大写字母对应的小写字母而不是空。

设变量名长度为m,则:

时间复杂度 = O(m)


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.