标签归档:Hoj

蒟蒻的Summer Training 2016 Final Contest题解

比赛的时候只出了四个傻逼题,死磕的一个背包题一直TLE,考完才发现是自己脑残非得状压一下,完全是不需要的。结果集训整体下来,自己居然还有rk6,然后就是集训结束了,队伍也定了,昨天也得到确切消息今年可以去一次区域赛,终于。。。从寒假开始学习到现在,付出这么多也值得了吧。说了这么多废话赶快进入正题。

这套题直接挂在了hoj上估计很难看到,所以我也把题目发上来,代码嘛,反正hoj是过了数据太弱啦。如果有什么bug的地方劳烦指出(其实有好多题都是队友和clearY以及老司机教本蒻的!)

A.(逆向搜索+打表+康托展开hash)

Description

Nine tiles, each with a number from 1 to 9 on it, are packed into a 3 by 3 frame. Your task is to arrange the tiles so that they are ordered as:
1 2 3
4 5 6
7 8 9
At each step, you can do the following operation to the tiles: Choose 2 by 2 tiles, rotate the tiles in clockwise order. For example:
1 2 3            4 1 3                1 2 3            1 2 3
4 5 6    =>    5 2 6        or     4 5 6    =>    4 8 5
7 8 9            7 8 9                7 8 9             7 9 6
Write a program to find the minimum number of steps.

Input

Input contains multiple test cases.
Each test case is a description of a configuration of the nine tiles. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and from left to right within a row, where the tiles are represented by numbers 1 to 9. For example:
9 8 7
6 5 4
3 2 1
is described by this list:
9 8 7 6 5 4 3 2 1

Output

Output the minimum number of steps on a single line for each test case.

Sample Input

Sample Output

这道题如果不会做或者TLE一看就是不会做hdu那道八数码,会的话,只要把操作顺序变成逆时针转动即可。

B(单调队列)

Description

Suppose there is a queue, in which we could do some operations as follow:

PUSH X: Means that enqueue a number X (-2^31 < X < 2^31) to the tail of the queue.
POP: Means that dequeue a number from the head of the queue.
MINUS: Means that form each number in the queue to its corresponding inverse number, viz. X = -X.
MAX: Means that return the maximum number in the queue.
Notice that for operations POP, MINUS and MAX, if it is no numbers current in the queue, just ignore them.
Given a sequence of operations, then for each “MAX” operation, if this operation is not ignored, you should output the maximum value it returned.

Input

The first line of input there is one integer T (T ≤ 10), giving the number of test cases in the input. For each test case, the first line contains a number N (N ≤ 2,000,000), representing the quantity of operations. The following N lines give out the detail.

Output

For each “MAX” operation not ignored, output the returned number in a line. Output a blank line between the test cases.

Sample Input

Sample Output

clearY大爷教的。我们可以把所有push进来的数看成放到一个队列内。pop就相当于head指针向后移动,push就直接放进来即可。那么关键就在于minus和max操作。minus的话我们可以打一个标记,代表序列是否翻转。如果在有minus标记的情况下,每push进来一个数,我们需要把它取反,再加入序列。(为什么要这样做呢?)这是由我们的max操作决定的。在有minus标记的情况下,我们需要找出序列中的最小值并取反输出结果,没有标记的话直接找最大值即可。这样我们就把minus从对之前的序列的操作,转化成了对将来加入的数的操作。

所以说接下来的任务就是维护两个单调队列,一个维护最小值,一个最大值。另外在一些操作的时候要注意队列为空的特判,详细见代码。。

 

C(dfs+dp)

Description

There are n positions in the cave. Each position has some value of treasure. There are some roads between the positions. Now your task is to divide the position into two parts such that no two positions connected directly by a road belong to the same part. And you must make the difference between the total value of the first part and the total value between the second part minimum.

Input

For each test case, the first line contains a single integer n (1 ≤ n ≤ 100), the number of positions.
The second line contains n positive integer v1, v2, … vn (1 ≤ v1, v2, …, vn ≤ 20). vi is the value of treasure in position i.
Then following are n lines. Each contains n characters. The jth character of the ith line is ‘1’ if position i and position j are connected. The input test data guarantee you can divide the position into two part such that no two positions connected directly by a road belong to the same part.

Output

For each test case, print the minimum difference between the two parts in a single line.

Sample Input

 

Sample Output

我们先dfs一波搞出所有连通块并标号,因为题目保证一定有解,那么每个连通块必定是可以被二分染色分成两部分。所以我们对每个连通块二分染色,计算出两种颜色的差值为Vi。我们可以把这个看成一个价值。接下来直接dp一波:设dp[i][j]=1为前i个连通块,价值为j的方案存在。等于0自然是不存在。

转移方程:dp[i][j]=dp[i-1][j-Vi] | dp[i-1][j+Vi]

这么写是因为dp[i][j]可能是上一轮加上这个价值或者减去得到的。然后注意一下负下标的处理,然后就好写了。

D(计算几何,需要卡一卡常数)

Description

There are n points in the plane. The points are given by their coordinates. You have a searchlight and you can place it at one of the n points as you like. The area the searchlight lightened is a sector with the chosen point as the center. And the central angle is π/6 (30 degrees), the radius is d. Now you can choose any point and any direction to make the number of points lightened by the searchlight (including the chosen point) maximum.

Input

For each test case, the first line contains two integer n and d, which are described above. Then the following n lines each contains two integer x and y, describing one point. (1 ≤ n ≤ 1000, 0 < d < 40000, -10000 ≤ x, y ≤ 10000).

Output

For each test case, print the maximum number in a single line.

Sample Input

Sample Output

八数码盲目搜素的两种方法

这段时间。。。一直在训练,天天被大佬虐,也没时间和心情写一点垃圾的东西。

课文资料

八数码问题其实可以A*之类的强力(玄学)搜索方法用估计函数解决。但是蒻还没学会A*,所以就先对应两道八数码问题写两种盲目搜索的方式。

其实八数码问题就相当于一个bfs的最短路问题,只不过现在bfs的时候我们需要把一个九宫格的数字映射成一个结点(而且不会和其他状态相同)。这就需要介绍一个康托展开的东西了:康托展开

其实这个东西就相当于当前排列,在所有的全排列中是第几小,从而完成映射(hash).然后按照这个定义就可以写出hash部分的代码了。

然后来看个题。

hdu 1043 Eight(逆向bfs+康托展开+打表)

这道题目是多组数据,而且需要我们打印路径,而如果我们对于每一个输入都进行一次bfs的话就会发现tle了。这是因为这道题目的目标状态是固定的,其实我们从一个状态到目标状态的过程中是会经历很多重复的状态。也就是对于一个起始状态a我们可以搞出他到终点的最少步数,但是输入b状态的时候你有可能重复经历一次这个状态的查询,所以逆向bfs,找出所有状态到目标状态的最短路(因为我们在这个过程中可以记录状态的前驱状态,然后递归回去就可以了)。

 

其实这道题目太特殊了,因为他给出了目标状态。所以才可以这样搞。

hoj 1868 八数码

如果给出目标状态和起始状态,然后询问的话,就不能逆向搞了。我们可以双向搜索。个人理解就是把起点终点都压入队列。如果一个状态被两个方向都找到过,那么就找到最短路啦。注意标记好两个两个方向的不同标记,另外其实八数码可以快速判断是否有解。

方法就是若两个状态的逆序同奇偶,则有解,否则无解。不考虑空格

证明:把八数码看成一维的话,左右移动空格并不会影响逆序。上下移动空格,这就是一个数向前或者向后跳两格,所以逆序要么增加2要么不变。所以同奇偶是保证有解的充要条件。

 

hoj 3200 No Game School(分段完全背包)

Description

BGod is a college student who love computer games, but unfortunately his school just published a rule that Games should disappear in the campus , that means nobody can play computer games in school, including the students dormitory. However, the student don’t take it seriously, that’s why the manager of the school gets so angry that he decided to go to the dormitory to punish the students. You should know the manager any punish those students who is playing games at the moment he enter the room, and leave immediately if nobody is playing game in this room.

BGod is a talented game player , in fact, he is the Carry of a famous Gaming club, so he needs time to practice he’s skills . And luckily , BGod’s roommate PY is a Geek(also a BGod fan), he hacked the manager’s computer and get the timetable of the manager, and tell BGod when will the manager come to their room tomorrow. A big E-sport Event is around the corner, so BGod list m skills he should practice, each skill takes some time to practice and improve BGod’s skill by some points. You should calculate the max total improvement points BGod can get. Note any skills can be practiced any times , including 0.

 

Input

The first line contains a integer T ( T <= 10 ), then T cases follows.

In each case, there are 3 parts of input.

 

The first part contains 3 integers L, n, m in a single line.Range[0, L] is the time BGod decide to practice , n is the times manager would enter his room, m indicate the total number of the skills.

 

The second part contains n integers ti(0 <= ti <= L) in a single line, means the manager would enter his room at ti. Note that ti is giving in the increasing order.

 

The third part has m lines , each line contains two integers ci(ci <= m), vi(vi <= 200), means this skill needs ci minutes to practice and can make vi points improvement.

 

L <= 500

n <= 10

m <= 100

 

Output

For each case, you should output the max points BGod can improve.

Sample

Input Output
2

6 1 3

3

2 3

2 4

2 5

6 2 3

2 4

2 3

2 4

2 5

10

15

 

 

完全背包,但是因为有一些点是manager要检查的,所以我们可以按照检查的时刻,把[0,L]分段处理,计算每个分段容量的完全背包,最后求一遍和即可。李大爷说了一种很简单的方法,直接计算最长区间容量的完全背包即可。恩这是显然的很快的方法。