题目链接：The Chosen One

比赛链接：ICPC Asia Nanning 2017

题意

$t$ 组样例，每组给出一个整数 $n(2\le n\le 10^{50})$，求不大于 $n$ 的最大的 $2$ 的整数次幂。

大数运算之 Java BigInteger 的基本用法

在程序设计竞赛中会遇到高精度运算的问题，C++没有高精度运算，只能手动模拟人工运算，手动实现高精度，而 java.math 包中的 BigInteger 提供了高精度的基本运算，因此竞赛中常用 Java 解决高精度运算问题。

当然如果比赛支持 python 就当我没说。

2019 杭电多校 5 1004

题目链接：HDU 6627

比赛链接：2019 Multi-University Training Contest 5

Problem Description

You are given two integers $N,C$ and two integer sequences $a$ and $b$ of length $N$. The sequences are indexed from $1$ to $N$.

Please solve the following equation for $x$:

$∑_{i=1}^N|a_i\cdot x + b_i| = C$, where $|v|$ means the absolute value of $v$.

2019 杭电多校 8 1009

题目链接：HDU 6665

比赛链接：2019 Multi-University Training Contest 8

Problem Description

Calabash is the servant of a landlord. The landlord owns a piece of land, which can be regarded as an infinite 2D plane.

One day the landlord set up two orthogonal rectangular-shaped fences on his land. He asked Calabash a simple problem: how many nonempty connected components is my land divided into by these two fences, both finite and infinite? Calabash couldn’t answer this simple question. Please help him!

Recall that a connected component is a maximal set of points not occupied by the fences, and every two points in the set are reachable without crossing the fence.

2019 杭电多校 8 1011

题目链接：HDU 6667

比赛链接：2019 Multi-University Training Contest 8

Problem Description

Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be $n$ classes participating in this festival, where the ith class has $a_i$ students and will make $b_i$ cups of milk tea.

Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can’t drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea?

题目链接：POJ 1753

Problem Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it’s black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

Choose any one of the 16 pieces.

Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example:

bwbw

wwww

bbwb

bwwb

Here “b” denotes pieces lying their black side up and “w” denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw

bwww

wwwb

wwwb

The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

题目链接：POJ 2251

Description

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?

题目链接：HDU 2553

Problem Description

在 $N*N$ 的方格棋盘放置了 $N$ 个皇后，使得它们不相互攻击（即任意 $2$ 个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 $45$ 角的斜线上。

你的任务是，对于给定的 $N$，求出有多少种合法的放置方法。

2019 杭电多校 5 1005

题目链接：HDU 6628

比赛链接：2019 Multi-University Training Contest 5

Problem Description

A sequence of length $n$ is called a permutation if and only if it’s composed of the first $n$ positive integers and each number appears exactly once.

Here we define the “difference sequence” of a permutation $p_1, p_2,…,p_n$ as $p_2−p_1,p_3−p_2,…,p_n−p_{n−1}$. In other words, the length of the difference sequence is $n−1$ and the $i$-th term is $p_{i+1}−p_i$

Now, you are given two integers $N,K$. Please find the permutation with length $N$ such that the difference sequence of which is the $K$-th lexicographically smallest among all difference sequences of all permutations of length $N$.

2019 杭电多校 7 1011

题目链接：HDU 6656

比赛链接：2019 Multi-University Training Contest 7

Problem Description

Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you are now the game designer of this game. He decided to annoy these Kejin players a little bit, and give them the lesson that RMB does not always work.

This game follows a traditional Kejin rule of “when you are level i, you have to pay $a_i$ RMB to get to level $i+1$”. Cuber QQ now changed it a little bit: “when you are level $i$, you pay $a_i$ RMB, are you get to level $i+1$ with probability $p_i$; otherwise you will turn into level $x_i (x_i\le i)$”.

Cuber QQ still needs to know how much money expected the Kejin players needs to ``ke’’ so that they can upgrade from level $l$ to level $r$, because you worry if this is too high, these players might just quit and never return again.