蒟蒻的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

发表评论

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