<<算法竞赛入门经典>> UVaoj第二卷排序检索习题:
340-Master-Minds Hints
每一次首先给出一个模板数列, 然后看接下来输入的数列有中的数有多少是跟模板中的元素位置和值都相同, 有多少是和模板中的数列值相同但是位置不相同, 注意一旦有数字先匹配到了位置相同并且值相同的话就不再参与其他匹配了.
10420-List of Conquests
map大法好!
10474-Where is the Marble
输入N个数, 然后再输入要查找的Q个数, 依次输出Q个数中每个数在N个数中被找到的位置, 找不到就not found.
152-Tree’s a Crowd
一个三维直角坐标系中, 给出所有数的坐标, 然后依次求出每棵树离其他数的最短距离, 最后统计[0,10)的十个区间中的数各有多少([0,1)作为第一个区间), 这个题目当时因为多输出了一个回车各种被卡死, UVaoj里面报错好像从来没有输出错误这个东西…
299-Train Swapping
给出N个数, 求要让序列变为递增序列需要多少步(只能通过交换数组元素邻近的值来更换数组元素的位置), 因为N个数的取值范围是[1,N],所以从位置1开始往后遍历, 碰见ai != i的在数列里面找到 i 然后一个一个地移到前面来, 计算最后所有的步数即可.
120- Stacks of Flapjacks
给出一个N个饼, 最左表示顶层, 最右表示最底层, 每一次翻转都是从第i个饼及以上的饼全部倒置, 然后求至少要翻多少次每次要翻哪些饼才能让饼由上往下递增. 关键点在于每次翻转第i个及以上的饼的时候, 第i个饼以下的饼并不会受影响, 所以从最底层往上开始, 每次都找到要调换到该位置的最大的饼即可. 因为饼的直径可能会是两位数, 所以开始我用scanf(“%c处理各种WA, 貌似最近总是出现类似的问题.
156-Ananagrams
所谓Ananagrams就是两个字符串有相同个数的各种字母, 题目就是求有多少个字符串不是Ananagrams的, 要注意一种情况就是abb和aab并不是Ananagrams, 所以判断Ananagrams的时候最好还是统计每个字符串各个字母的个数.
400-Unix Is
这个题目和之前的大部分题目差不多, 只要使用STL, 都会方便很多. 题意要求是最后一列的字符输出长度为最长字符串的长度, 然后其他列的输出格式都是最长字符串的长度+2(为什么不是最长字符串的长度呢? 因为中间要保持空格), 最后要求列数要尽量多, 以让行数尽量少, 找出最长字符串然后依据题意就可以计算出最多的列数, 然后把所有字符串都塞到set里面, 自动按字母表排序, 然后直接按序输出即可.
123-Searching Quickly
就是把每一个未被忽略的关键词显示出来, 显示的时候显示一整个字符串, 然后关键词大写, 字符串里面词小写, 同一个字符串里面有相同的关键词也要分别输出. 这个地方直接来个multimap, 每一个关键词对应一个字符串, 然后每找到一个关键词就塞到multimap里面去, 正好multimap也自带字典排序, 最后直接输出即可.
10194-Football(aka Soccer)
统计每个国家的比赛数据, 然后排出一个rank输出, 这个地方有一点坑的要死, 因为我用的string做队名, 然而string里面的大于小于号是不支持忽略大小写的比较, 但是字典序是不区分大小写的, 所以这个时候需要把队名转为统一小写或者大写进行比较, 不然就是各种WA到死.
755-487–3279
根据给出的解码表, 然后把输入的电话号码转换成统一的格式并统计各自的数目, 最后将出现次数大于1的按照字典排序输出, map轻松加愉快.
107850-The Mad Numerologist
给出对应的表格, 每个字母都有对应数值, 然后奇数位(第一位的序号为1)只能用元音字母, 偶数位只能用非元音字母, 每个元音字母最多用21遍, 每个非元音字母最多用5遍, 然后给定一个名字的长度, 求如何组合字母才能使总的数值最小, 然后千万要记住名字中的字母在满足之前的条件下还要按字母表排序输出.
这一批的题目总体还是很实在的, 巩固了好多STL方面的东西, 做了还是很有感觉的.