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