WuTao's Blog

比赛链接：2019 年百度之星·程序设计大赛 - 初赛四
题目链接：HDU-6719 Strassen

C++ 没写出来

于是直接上 Java 暴力。

好像可以用 __int128。

题目链接：POJ 2398

Problem Description

Mom and dad have a problem: their child, Reza, never puts his toys away when he is finished playing with them. They gave Reza a rectangular box to put his toys in. Unfortunately, Reza is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for Reza to find his favorite toys anymore.

Reza’s parents came up with the following idea. They put cardboard partitions into the box. Even if Reza keeps throwing his toys into the box, at least toys that get thrown into different partitions stay separate. The box looks like this from the top:

We want for each positive integer t, such that there exists a partition with t toys, determine how many partitions have t, toys.

题目链接：POJ 2318

Problem Description

Calculate the number of toys that land in each bin of a partitioned toy box.

Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John’s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

2019 杭电多校 10 1007

题目链接：HDU 6697

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

Problem Description

The closest pair of points problem is a well-known problem of computational geometry. In this problem, you are given $n$ points in the Euclidean plane and you need to find a pair of points with the smallest distance between them.

Now, Claris, the brilliant one who has participated in programming contests for several years, is trying to solve a harder problem named the closest pair of segments problem, which also has a quite simple description as above.

However, the problem seems even too hard for Claris and she is asking you for help.

Now $n$ segments are lying on the Euclidean plane, you are asked to pick two different segments and then pick a point on the two segments respectively to minimize the distance between these two points.

For simplicity, any two given segments share no common point, and you don’t need to show her the two chosen points, but the distance between them instead.

2019 杭电多校 10 1005

题目链接：HDU 6695

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

Problem Description

The annual welcome party of the Department of Computer Science and Technology is coming soon! Many students have been applying to show up at the welcome party, and every one of them can choose to sing a song or play crosstalk. This troubles the chief director a lot: how to arrange the program list, such that every student can have a chance to show up on the stage, and the satisfactory value of audiences is maximized?

To cope with this problem, the director proposes a model. In this model, every student has two attributes: the singing ability and crosstalking ability. The satisfactory value of audiences to singings is the maximum singing ability among all students that choose to sing a song; similarly, the satisfactory value to crosstalks is the maximum crosstalking ability among all students that choose play crosstalk. The strange thing is, the overall satisfactory value to the whole party is negatively related to the absolute difference between the satisfactory values to singings and crosstalks. The problem is, what is the minimum possible absolute difference between the satisfactory values of the two types of programs?

Note that:

• every student should choose exactly one type of programs to play;
• at least one student should sing a song, and at least one student should play crosstalk.

2019 杭电多校 10 1003

题目链接：HDU 6693

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

Problem Description

Oipotato loves his girlfriend very much. Since Valentine’s Day is coming, he decides to buy some presents for her.

There are $n$ presents in the shop, and Oipotato can choose to buy some of them. We know that his girlfriend will possibly feel extremely happy if she receives a present. Therefore, if Oipotato gives $k$ presents to his girlfriend, she has $k$ chances to feel extremely happy. However, Oipotato doesn’t want his girlfriend to feel extremely happy too many times for the gifts.

Formally, for each present $i$, it has a possibility of $P_i$ to make Oipotato’s girlfriend feel extremely happy. Please help Oipotato decide what to buy and maximize the possibility that his girlfriend feels extremely happy for exactly one time.

题目链接：POJ 3805

Problem Description

Numbers of black and white points are placed on a plane. Let’s imagine that a straight line of infinite length is drawn on the plane. When the line does not meet any of the points, the line divides these points into two groups. If the division by such a line results in one group consisting only of black points and the other consisting only of white points, we say that theline “separates black and white points”.

Let’s see examples in Figure 3. In the leftmost example, you can easily find that the black and white points can be perfectly separated by the dashed line according to their colors. In the remaining three examples, there exists no such straight line that gives such a separation.

In this problem, given a set of points with their colors and positions, you are requested to decide whether there exists a straight line that separates black and white points.

题目链接：UVA 10256

题意

有n个红点和m个蓝点,问是否存在一条直线能够分开红点和蓝点。

2019 杭电多校 1 1013

题目链接：HDU 6590

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

Problem Description

After returning with honour from ICPC(International Cat Programming Contest) World Finals, Tom decides to say goodbye to ICPC and start a new period of life. He quickly gets interested in AI.

In the subject of Machine Learning, there is a classical classification model called perceptron, defined as follows:

Assuming we get a set of training samples: $D={(\boldsymbol{x_1},y_1),(\boldsymbol{x_2},y_2),…,(\boldsymbol{x_N},y_N)}$, with their inputs $\boldsymbol{x}\in \mathbb{R}^d$, and outputs $y\in \{−1,1\}$. We will try to find a function $f(\boldsymbol{x})=sign(\sum_{i=1}^d w_i\cdot x_i+b)=sign(\boldsymbol{w^T} \cdot \boldsymbol{x}+b)$ so that $f(\boldsymbol{x_i})=y_i,i=1,2,…,N$.

$\boldsymbol{w}, \boldsymbol{x}$ mentioned above are all d-dimensional vectors, i.e. $\boldsymbol{w}=(w_1,w_2,…,w_d), \boldsymbol{x}=(x_1,x_2,…,x_d)$. To simplify the question, let $w_0=b$, $x_0=1$, then $f(\boldsymbol{x})=sign(\sum_{i = 0}^d w_i\cdot x_i)=sign(\boldsymbol{w^T}\cdot \boldsymbol{x})$. Therefore, finding a satisfying function $f(\boldsymbol{x})$ is equivalent to finding a proper $\boldsymbol{w}$.

To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).

Accoding to PLA, we will randomly generate $\boldsymbol{w}$.

If $f(\boldsymbol{x})=sign(\boldsymbol{w^T}\cdot \boldsymbol{x})$ fails to give any element $(\boldsymbol{x_i},y_i)\in D$ the right classification, i.e. $f(\boldsymbol{x_i})\neq y_i$, then we will replace $w$ with another random vector. We will do this repeatedly until all the samples $\in D$ are correctly classified.

As a former-JBer, Tom excels in programming and quickly wrote the pseudocode of PLA.

  w := a random vector
  while true do
      flag:=true
      for i:=1 to N do
          if f(x[ i ]) != y[ i ] then
              flag:=false
              break
      if flag then
          break
      else
          w := a random vector
  return w

But Tom found that, in some occasions, PLA will end up into an infinite loop, which confuses him a lot. You are required to help Tom determine, when performed on a given sample set $D$, if PLA will end up into an infinite loop. Print Infinite loop! if so, or Successful! otherwise.

We only consider cases when $d=2$ for simplification.

Note:

$$sign(x)= \begin{cases} -1& x < 0 \\ 0& x = 0 \\ 1& x > 0 \end{cases}$$

题目链接：POJ 2187

Description

Bessie, Farmer John’s prize cow, has just won first place in a bovine beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 … 10,000. No two farms share the same pair of coordinates.

Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.