2020-01-16
数据结构
思维

Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has 𝑛 friends, numbered from 1 to 𝑛.

Recall that a permutation of size 𝑛 is an array of size 𝑛 such that each integer from 1 to 𝑛 occurs exactly once in this array.

2020-01-16
思维
二分

You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.

You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every $k \in [1, m]$ $b_k = \max(a_{i, k}, a_{j, k})$ .

Your goal is to choose $𝑖$ and $𝑗$ so that the value of min$\min \limits_{k = 1}^{m} b_k$ is maximum possible.

2020-01-16
最大流
网络流

There is a square grid of size 𝑛×𝑛. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs min(ℎ,𝑤) to color a rectangle of size ℎ×𝑤. You are to make all cells white for minimum total cost.

The square is large, so we give it to you in a compressed way. The set of black cells is the union of 𝑚 rectangles.

2020-01-16
随机数
贪心

You are given an array of 𝑛 integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

2020-01-16
普通DP

There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs $\max(h, w)$ to color a rectangle of size $h \times w$. You are to make all cells white for minimum total cost.

2020-01-15
构造
二分图

You are given a graph with 3⋅𝑛 vertices and 𝑚 edges. You are to find a matching of 𝑛 edges, or an independent set of 𝑛 vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

2020-01-07
数据结构
思维

Filled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have 𝑛 lectures. Hyunuk has two candidate venues 𝑎 and 𝑏. For each of the 𝑛 lectures, the speaker specified two time intervals [𝑠𝑎𝑖,𝑒𝑎𝑖] (𝑠𝑎𝑖≤𝑒𝑎𝑖) and [𝑠𝑏𝑖,𝑒𝑏𝑖] (𝑠𝑏𝑖≤𝑒𝑏𝑖). If the conference is situated in venue 𝑎, the lecture will be held from 𝑠𝑎𝑖 to 𝑒𝑎𝑖, and if the conference is situated in venue 𝑏, the lecture will be held from 𝑠𝑏𝑖 to 𝑒𝑏𝑖. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval [𝑥,𝑦] overlaps with a lecture held in interval [𝑢,𝑣] if and only if max(𝑥,𝑢)≤min(𝑦,𝑣).

2020-01-07
图论

You are given 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛, such that for each 1≤𝑖≤𝑛 holds 𝑖−𝑛≤𝑎𝑖≤𝑖−1.

Find some nonempty subset of these integers, whose sum is equal to 0. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.

2019-12-28
2-SAT

In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. 𝑛 complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the 𝑖-th complaint, one of the radio fans has mentioned that the signals of two radio stations 𝑥𝑖 and 𝑦𝑖 are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.

2019-12-28
构造

You are given 𝑛 integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the 𝑛 numbers may not be chosen.