# 蒟蒻的Summer Training 2016 Final Contest题解

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.

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.

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.

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.

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

hdu 1043 Eight（逆向bfs+康托展开+打表）

hoj 1868 八数码

# 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