3月19号比赛题解

  • 内容
  • 评论
  • 相关

Ranklist

  • 题目描述

题目名称:Kblack loves flag

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=5995

Kblack loves flags, so he has infinite flags in his pocket.

One day, Kblack is given an n∗m chessboard and he decides to plant flags on the chessboard where the position of each flag is described as a coordinate (x,y), which means that the flag is planted at the xth line of the yth row.

After planting the flags, Kblack feels sorry for those lines and rows that have no flags planted on, so he would like to know that how many lines and rows there are that have no flags planted on.

Well, Kblack, unlike you, has a date tonight, so he leaves the problem to you. please resolve the problem for him.

输入

You should generate the input data in your programme.

We have a private variable x in the generation,which equals to seed initially.When you call for a random number ranged from [l,r],the generation will trans x into (50268147x+6082187) mod 100000007.And then,it will return x mod (r−l+1)+l.

The first line contains a single integer T refers to the number of testcases.

For each testcase,there is a single line contains 4 integers n,m,k,seed.

Then,you need to generate the k flags' coordinates.

For i=1⋯k,firstly generate a random number in the range of [1,n].Then generate a random number in the range of [1,m].

You can also copy the following code and run "Init" to generate the x[],y[] (only for C++ players).

<pre>

const int _K=50268147,_B=6082187,_P=100000007;

int _X;

inline int get_rand(int _l,int _r){

_X=((long long)_K*_X+_B)%_P;

return _X%(_r-_l+1)+_l;

}

int n,m,k,seed;

int x[1000001],y[1000001];

void Init(){

scanf("%d%d%d%d",&n,&m,&k,&seed);

_X=seed;

for (int i=1;i<=k;++i)

x[i]=get_rand(1,n),

y[i]=get_rand(1,m);

}

</pre>

(1≤T≤7),(1≤n,m≤1000000),(0≤k≤1000000),(0≤seed<100000007)

输出

For each testcase,print a single line contained two integers,which respectively represent the number of lines and rows that have no flags planted.

样例输入

2

4 2 3 233

3 4 4 2333

样例输出

2 1

1 0

  • 考核知识点

函数的调用

  • 常见误区

使用map,或者set来计数会超时,需要用到数组打表。

  • 解题思路

将出现的行存到一个标记数组中,列存到一个数组中,最后计算出没有被标记的行的总和和列的总和。

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

    学号姓名 :151210118  黄峥

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

    专业班级: 15计科1班

 

 

 

 

  • 题目描述

题目名称:Fire Net

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1045

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

QQ图片20170323210554

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

输入

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

输出

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

样例输入

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

0

样例输出

5

1

5

2

4

  • 考核知识点

深度优先搜索

  • 常见误区

对一个点所考虑的因素太多,会顾及这点的上下左右的所有情况,而导致复杂度增加。不会判断障碍物以及已经放过碉堡的位置。

  • 解题思路

对于一点,只需看他的上方和左方是否满足能放置的条件,若满足,又可以选择放或者不放。用深搜来遍历所有可能出现的情况,单独写一个函数来判断此位置是否可以放置碉堡,这样思路就会很清晰。

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

    学号姓名 :141210104  邓超

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

    专业班级: 14计科1班

 

 

 

 

 

  • 题目描述

题目名称:Nightmare

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1072

Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.

Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.

Here are some rules:

  1. We can assume the labyrinth is a 2 array.
  2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
  3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
  4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
  5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
  6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.

Ignatius昨晚做了一个恶梦,梦见在一个带有定时炸弹的迷宫里,迷宫有一个出口,Ignatius只有在炸弹爆炸前到达出口,才能出去。炸弹开始设定的时间是6分钟,为了避免炸弹因为震动而爆炸,Ignatius必须移动的很慢,只能走离他最近的前后左右(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute),每走一步花费1分钟。

其中有些地方是炸弹的重置区,可以把炸弹重置为6.

给你Ignatius的位置和迷宫让你判断他是否能走出迷宫:

能 输出走出迷宫花费的最少时间;

否 输出-1;

迷宫:

“2” 代表入口

“1” 可以走

“0” 是墙,不能走:

“4” 代表重置区:如果刚好走到4,准备reset引爆时间。但是走到该点时引爆时间  刚好变为0,则不能重新设置

“3” 代表出口如果刚好走到3,炸弹引爆时间变为0,则算走不出迷宫。

输入

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth. There are five integers which indicate the different type of area in the labyrinth: 0: The area is a wall, Ignatius should not walk on it. 1: The area contains nothing, Ignatius can walk on it. 2: Ignatius' start position, Ignatius starts his escape from this position. 3: The exit of the labyrinth, Ignatius' target position. 4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.

输出

For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.

样例输入

3

3 3

2 1 1

1 1 0

1 1 3

4 8

2 1 1 0 1 1 1 0

1 0 4 1 1 0 4 1

1 0 0 0 0 0 0 1

1 1 1 4 1 1 1 3

5 8

1 2 1 1 1 1 1 4

1 0 0 0 1 0 0 1

1 4 1 0 1 1 0 1

1 0 0 0 0 3 0 1

1 1 4 1 1 1 1 1

样例输出

4

-1

13

  • 考核知识点

广度优先搜索加剪枝

  • 常见误区

没有考虑4只能走一次,或者可以走回路这种情况

  • 解题思路

在n×m的地图上,0表示墙,1表示空地,2表示人,3表示目的地,4表示有定时炸弹重启器。定时炸弹的时间是6,人走一步所需要的时间是1。每次可以上、下、左、右移动一格。当人走到4时如果炸弹的时间不是0,可以重新设定炸弹的时间为6。如果人走到3而炸弹的时间不为0时,成功走出。求人从2走到3的最短时间。这个题中每个结点都是可以重复访问的,但其实,炸弹重置点不要重复走,因为,走到炸弹重置点时时间就会被设置为最大时间,当重新返回时时间又设成最大,但此时已走的步数肯定增加了,所以如果存在较优解的话那么肯定在第一次到这点后就可以找到较优解,这也是代码中剪枝的原理,只是将这种思想扩展到普通点而已。

QQ图片20170323210855

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

    学号姓名 :151210132 许娜

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

    专业班级: 15计科1班

 

 

 

 

 

  • 题目描述

题目名称:WisKey的眼神

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=1577

WisKey的眼镜有500多度,所以眼神不大好,而且他有个习惯,就是走路喜欢看着地(不是为了拣钱哦^_^),所以大家下次碰见他的时候最好主动打下招呼,呵呵.
但是Rabbit总是喜欢扮神秘,一天WisKey去食堂排队等着买饭,突然收到一道短消息,是Rabbit发的,”呵呵,又看见你了,你没看到我吧”.WisKey马上拉长脖子扫描食堂,可是就是看不到,再发短信问Rabbit在哪,Rabbit回信曰”我已经在寝室了”.WisKey无语....
假设食堂是个正方形,食堂中心坐标为(0,0),长度为2*L, WisKey保证在食堂内.
因为是吃饭高峰期,所以每个点上都站着人,当某些人处在同一直线上时就有可能被前面的人挡住.
聪明的ACMer请你帮帮WisKey,告诉他能不能看见Rabbit.

11111

输入

输入L,sx,sy,px,py; L<=1000,sx,sy是WisKey的坐标,px,py是Rabbit的坐标. 以L=0为结束.

输出

对于每组输入数据,能看见输出”Yes”,看不见输出”No”. Rabbit不在食堂输出”Out Of Range”.

样例输入

5 0 0 1 1

5 0 0 2 0

5 0 0 6 6

5 0 0 -1 -1

0

样例输出

Yes

No

Out Of Range

Yes

 

  • 考核知识点

判断两个数是否有公约数

  • 常见误区

Wiskey的起始位置不一定在原点;判断Rabbit是否在食堂时,应对其坐标取绝对值。

  • 解题思路

先判断L是否等于0。若不为0,判断Rabbit是否在食堂内。若Rabbit在食堂内,将Wiskey放在原点,计算出Rabbit相对应的新坐标(x1,y1)。易得,Wiskey在原点时,Rabbit在任一象限的结果是相同的,所以得到Rabbit在第一象限对应的坐标(x,y)。当满足x=1或者y=1时,所有点都能够被Wiskey看到;当满足x=0且y!=1或者y=0且x!=1时,所有点都不能够被Wiskey看到。若上述情况均不满足,则判断x,y是否有公约数,若有,则不能够被看到,反之,能够被看到。

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

    学号姓名 :161360248  吴显宁

    院系 :信息工程学院

    专业班级: 16物联2班

 

 

 

 

 

  • 题目描述

题目名称:Skip the Class

题目来源:http://acm.hdu.edu.cn/showproblem.php?pid=6015

Finally term begins. luras loves school so much as she could skip the class happily again.(wtf?)
Luras will take n lessons in sequence(in another word, to have a chance to skip xDDDD).
For every lesson, it has its own type and value to skip.
But the only thing to note here is that luras can't skip the same type lesson more than twice.
Which means if she have escaped the class type twice, she has to take all other lessons of this type.
Now please answer the highest value luras can earn if she choose in the best way

.输入n组科目和对应的价值,每种科目的价值不得相加超过两次,求可以得到的最大价值

输入

The first line is an integer T which indicates the case number. And as for each case, the first line is an integer n which indicates the number of lessons luras will take in sequence. Then there are n lines, for each line, there is a string consists of letters from 'a' to 'z' which is within the length of 10, and there is also an integer which is the value of this lesson. The string indicates the lesson type and the same string stands for the same lesson type. It is guaranteed that—— T is about 1000 For 100% cases, 1 <= n <= 100,1 <= |s| <= 10, 1 <= v <= 1000

输出

As for each case, you need to output a single line. there should be 1 integer in the line which represents the highest value luras can earn if she choose in the best way.

样例输入

2

5

english 1

english 2

english 3

math 10

cook 100

2

a 1

a 2

样例输出

115

3

  • 考核知识点

结构体使用,贪心。

  • 常见误区

科目的价值不可超过两次 。

  • 解题思路

将n组数据的价值进行降序排序。给每种科目数量用map进统计,当科目数小于等于二时,就把价值加到要求的最大价值。

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

    学号姓名 :161210217  王玉芹

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

    专业班级: 16计科2班

 

 

Cache_-69fc0878d395f892.

评论

0条评论

发表评论

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