16/11/4 题解

  • 内容
  • 评论
  • 相关
  • 题目描述

题目名称:统计难题

题目来源:HDOJ

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

输入

数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.

输出

对于每个提问,给出以该字符串为前缀的单词的数量.

样例输入

banana

band

bee

absolute

acm

 

ba

b

band

Abc

样例输出

2

3

1

0

  • 考核知识点

Map容器

  • 常见误区

  • 解题思路

将字符串所有的前缀都找出来,用map存入,相同前缀叠加,最后输出你所需要的前缀个数即可

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210243 徐成东

    院系 :计算机学院(软件学院)

    专业班级: 15计科2班

 

 

 

 

  • 题目描述

题目名称:产生冠军

题目来源:HDOJ

有一群人,打乒乓球比赛,两两捉对撕杀,每两个人之间最多打一场比赛。
球赛的规则如下:
如果A打败了B,B又打败了C,而A与C之间没有进行过比赛,那么就认定,A一定能打败C。
如果A打败了B,B又打败了C,而且,C又打败了A,那么A、B、C三者都不可能成为冠军。
根据这个规则,无需循环较量,或许就能确定冠军。你的任务就是面对一群比赛选手,在经过了若干场撕杀之后,确定是否已经实际上产生了冠军。

输入

输入含有一些选手群,每群选手都以一个整数n(n<1000)开头,后跟n对选手的比赛结果,比赛结果以一对选手名字(中间隔一空格)表示,前者战胜后者。如果n为0,则表示输入结束。

输出

对于每个选手群,若你判断出产生了冠军,则在一行中输出“Yes”,否则在一行中输出“No”。

样例输入

3

Alice Bob

Smith John

Alice Smith

5

a c

c d

d e

b e

a d

0

样例输出

Yes

No

  • 考核知识点

这道题可以用模拟来做也可以用STL来做,但是首先你要知道什么情况下会产生冠军。

  • 常见误区

如果你是用模拟方法来做,那么注意判断是否产生冠军时要严密一点,漏掉任意一点就会Wa。

  • 解题思路

这道题判断冠军是否产生那你就看只赢不输的人有几个,如果只有一个的话那么就会有冠军产生,否则也就是只赢不输的人没有或者是有多个就不会产生冠军。知道了题意接下来就是选择怎么写代码来实现,我这有两种方法,都分别说一下。第一个方法我是用模拟做的,我把所有出现过的名字都存放在一个字符数组ch[1005][20]里,那么每个名字就对应着这个字符数组里特定的下标,同时我又用到一个整型的set数组,里面用来存放每个人对应的胜负状态,这个时候其实ch数组和set数组的下标是有联系的,相同的下标代表着同一个人的信息,分别有名字信息和胜负状态。最后只要遍历一下set数组就可以知道是否产生了冠军。第二种方法是用STL做的,就是用了两个set容器,一个用来放所有参加比赛的人的个数,另一个用来放比赛输过的人的个数,只要参加比赛的人的个数比输过比赛的人的个数多1,那么冠军就可以产生。

  • 参考答案(附关键注释)
  • 第一种模拟方法

  • 第二种STL
    • 整理者

    学号姓名 :151210242 陶林娟

    院系 :计算机学院(软件学院)

    专业班级: 15计科2班

 

 

 

  • 题目描述

题目名称:Card Trick

题目来源:HDOJ

The magician shuffles a small pack of cards, holds it face down and performs the following procedure:

  • The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.
  • Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.
  • Three cards are moved one at a time…
  • This goes on until the nth and last card turns out to be the n of Spades.

This impressive trick works if the magician knows how to arrange the cards beforehand (and

knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 13.

输入

On the first line of the input is a single positive integer, telling the number of test cases to follow. Each case consists of one line containing the integer n.

输出

For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc…

样例输入

2

4

5

样例输出

2 1 4 3

3 1 4 5 2

  • 考核知识点

STL队列的使用

  • 常见误区

  • 解题思路

题目意思:一个魔术师,手里有n个扑克牌,扑克牌从1-n。给定一个n,要求输出一个循环队列,在最上面翻1张牌,放在最后,然后最上面的一张牌是1,然后将那张牌舍弃;在最上面翻2张牌,依次放在最后,最上面为2,然后将2舍弃,以此类推到n;求这样一个循环队列。逆向思维,根据题意可得舍弃1 需要向下放一张牌,2需要向下放两张牌,以此类推可总结出规律,即每存编号为i的纸牌需要向下放i次,所以可借助队列来实现此过程

  • 参考答案(附关键注释)

队列:

数组:

  • 整理者

学号姓名 :151210118  黄峥

院系 :计算机学院(软件学院)

专业班级:15计科1班

 

 

 

 

 

 

 

  • 题目描述

题目名称:Train Problem I

题目来源:HDOJ

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.

1 2 3

输入

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

输出

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.

样例输入

3 123 321

3 123 312

样例输出

Yes.

in

in

in

out

out

out

FINISH

No.

FINISH

 

[hint]Hint[/hint]

For the first Sample Input, we let train 1 get in, then train 2 and train 3.So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1.In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3.

Now we can let train 3 leave.But after that we can't let train 1 leave before train 2, because train 2 is at the top of the railway at the moment.

So we output "No.".

  • 考核知识点

栈的基本操作

  • 常见误区

每次新的数据输入时,一定要保证栈为空!

  • 解题思路

用字符串输入一组数据o1和o2,每次让o1的元素依次进栈并且与o2的元素进行比较,如果不相等,那么就让o1里的元素继续进栈,然后再次与o2中元素进行比较。用一个数组作为标记数组,该数组初值全赋为-1,每进栈一次,让该数组下表+1,并标记为1,每出栈一次,下表+1,并标记为0.

  • 参考答案(附关键注释)
    • 整理者

    学号姓名 :151210209  赵永旗

    院系 :计算机学院(软件学院)

    专业班级:15计科2班

     

 

 

 

 

 

 

  • 题目描述
    题目名称:Pirate’s Code

题目来源:HDOJ

Davy Jones has captured another ship and is smiling contently under the sun. Today is a good day for him. He will get more souls to serve on his crew. The day, however, looks so nice, the sun shining brightly above all and the ocean spilled calmly around, that he decides to be merciful and give some chance to the wretched seamen of the captured ship. He decides to play the following game. He will line a group of captives in front of him, and then write a number of his choice on each man’s forehead. After that, he wants to check if the set of numbers is 3-free. What does it mean for a set to be 3-free? It means that there are no 3 numbers in the set that form an increasing arithmetic progression (weird games have damned Jones, aye), i.e., a sequence of numbers such that the difference of any two successive members of the sequence is a positive constant, such as {1 2 3}, {4 6 8}, or {-2, 1, 4}. If the the set of numbers on men’s foreheads is 3-free, the group is free, too (what an irony). However, if not, those who have the numbers of the lexicographically first triple that proves (i.e. is a witness) that the set is not 3-free will serve on Jones’ crew for an eternity. And you ... You will be Jones’ assistant in this game. Checking each group whether it is 3-free or not. And you’d better check right or you will end up on Jones’ crew as well. A triple (a1, a2, a3) is an increasing arithmetic progression if a2-a1=a3-a2, and a2-a1>0. A triple (a1, a2, a3) is lexicographically smaller than (b1, b2, b3) if a1 < b1, or a1 = b1 and a2 < b2, or a1 = b1, a2 = b2 and a3 < b3. Note that you will be looking at triples (a1, a2, a3) of increasing order, i.e. a1 ≤ a2 ≤ a3. The numbers on men’s foreheads need not be in increasing order though.

输入

Input consists of a single line with the numbers written on the captured men’s foreheads. Thefirst number of the line denotes how many men are there in the group(it will not exceed 10000) and should not be included in the sequence.

输出

Output should consist of a single line. If the sequence of numbers in the input is 3-free, output “Sequence is 3-free.” If the sequence is not 3-free, output “Sequence is not 3-free. Witness: w1, w2, w2.” (note the intervals after the first dot and the colon), where w1, w2, w3 is the lexicographically first witness that the sequence is not 3-free.

样例输入

4 1 5 6 8

7 1 3 5 2 -7 0 -1

样例输出

Sequence is 3-free.

Sequence is not 3-free. Witness: -7,-1,5.

  • 考核知识点

map容器的应用

  • 常见误区

数据处理不全面

  • 解题思路

首先理解题意中的关键字“3-free”数表示的含义,即为相邻的三个数不能够构成公差大于零等差数列。理解啦这个含义后我们概述一下题意:让你判断一组数据中是否存在满足这种关系的数据,如果不存在则这组数据不为“3-free”数,否者的话按一定的格式输出者三个数。

  • 参考答案(附关键注释)

首先提供一种用一般数组求解的算法:(时间超限)

用set数组优化最后查找中间值的过程:

用map容器优化最后查找中间值的过程:

  • 整理者

学号姓名 :151210114 崔梦梦

院系 :计算机学院(软件学院)

专业班级: 15计科1班

 

 

 

 

 

 

 

  • 题目描述

题目名称:Ignatius and the Princess II

题目来源:HDOJ

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."

 

"Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3...N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it's easy to see the second smallest sequence is 1,2,3...N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It's easy, isn't is? Hahahahaha......"

Can you help Ignatius to solve this problem?

输入

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub's demand. The input is terminated by the end of file.

输出

For each test case, you only have to output the sequence satisfied the BEelzebub's demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

样例输入

6 4

11 8

样例输出

1 2 3 5 6 4

1 2 3 4 5 6 7 9 8 11 10

  • 考核知识点

STL中next_permutation函数的应用

  • 常见误区

  • 解题思路

题目的意思是给出一个从小到大的序列认为它是最小的而从大到小的序列是最大的,题目要求输出第m小的序列,这个题目使用STL中的next_permutation函数,这个函数的意思是将输入的一个序列排列成比它大的下一个序列,所以初始化一个最小的序列使用这个函数循环m-1次就是第m小的序列。

  • 参考答案(附关键注释)

  •  
    • 整理者

    学号姓名 :151360205  徐帅武

    院系 :信息工程学院

    专业班级: 15物联2班

 

 

评论

0条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注