湖南大学第十六届程序设计竞赛（重现赛）题解

七月 17, 2021

ACM - C++

湖南大学第十六届程序设计竞赛（重现赛）题解

2021/7/15

A Triangles

链接：https://ac.nowcoder.com/acm/contest/18196/A

There are 3 kinds ofTriangles: acute triangles, right triangles and obtuse triangles.A triangle with an obtuse angle (the obtuse angle is greater than 90 degrees and less than 180 degrees) is an obtuse triangle (obviously only one angle can be obtuse angle). The three internal angles of a triangle are all acute angles (the acute angle is greater than zero and less than 90 degrees), which is called "acute triangle"; one internal angle is right angle (the right angle is equal to 90 degrees), which is called "right triangle".

Given the coordinates of three verticesof a triangle,write a program to judge the kind of the triangle. Note that three points may not form a triangle (for example, two or three vertices coincide, or three points are collinear).

输入描述:

1
2

The first line contains one integerN（N ≤ 10,000）, the number oftriangles.
The following N lines, each line contains six integersin the following format:x1 y1 x2 y2 x3 y3 Where (xi,yi)  i=1,2,3 arethe coordinates of three verticesof the triangle.-10,000≤ xi,yi ≤ 10,000 i=1,2,3

输出描述:

OutputN lines. For each triangle, output one line.If the three points do not form a triangle, output "invalid"(Without quotation marks)If three points form an obtuse triangle, output "obtuse"(Without quotation marks)If three points form an acute triangle, output "acute"(Without quotation marks)If three points constitute a right triangle, output "right"(Without quotation marks)

示例1

输入

4
0 0 2 0 1 2
0 0 0 1 1 0
0 0 1 0 -1 -1
0 0 1 0 2 0

输出

acute
right
obtuse
invalid

题目大意

大概意思就是给定三个点的直角坐标，问你能不能构成三角形，如果能构成三角形则判断是锐角直角还是钝角三角形。

解题思路

先判断能不能构成三角形，由于在一个平面上，因此只要三点不共线、不共点，就一定能组成三角形。

先判断是否有共点，由于我们后面要用到三角形的边长，所以这里我们直接判断三条边是否都不等于 0 就行。设三边长 a b c ,即 $(a!=0 \space\&\&\space b!=0\space\&\&\space c!=0)$
再判断有没有三点共线，比较笨的方法就是求三条直线然后代入另外一个点坐标进去，判断是否在直线上。聪明一点就是判断是否有两个直线的斜率相同，即两条直线平行。

再判断是什么三角形：利用三角形的性质

\begin{cases} a^2+b^2<c^2\space 钝角三角形\\ a^2+b^2=c^2\space 直角三角形\\ a^2+b^2>c^2\space 锐角三角形 \end{cases}

代码

#include <bits/stdc++.h>
using namespace std;

bool pd(long long x1, long long y1, long long x2, long long y2, long long x3, long long y3)
{
  if (x2 - x1 != 0)
  {
    if (y3*(x2 - x1) == ((y2 - y1) * x3 + y1*(x2 - x1)-(y2 - y1)*x1))
      return true;
    else
      return false;
  }
  else
  {
    if (x3 == x1)
      return true;
    else
      return false;
  }
}

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    long long x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    bool tmp = 0;
    if (pd(x1, y1, x2, y2, x3, y3) && pd(x2, y2, x3, y3, x1, y1) && pd(x1, y1, x3, y3, x2, y2))
      tmp = 1;
    long long a, b, c;
    a = (y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1);
    b = (y3 - y1) * (y3 - y1) + (x3 - x1) * (x3 - x1);
    c = (y3 - y2) * (y3 - y2) + (x3 - x2) * (x3 - x2);
    if (!tmp && a != 0 && b != 0 && c != 0 && (sqrt(a) + sqrt(b) > sqrt(c)) && (sqrt(a) + sqrt(c) > sqrt(b)) && (sqrt(c) + sqrt(b) > sqrt(a)))
    {
      long long q, w, e;
      q = min(a, min(b, c));
      e = max(a, max(b, c));
      w = a + b + c - q - e;
      if (q + w == e)
        cout << "right\n";
      else if (q + w < e)
        cout << "obtuse\n";
      else
        cout << "acute\n";
    }
    else
      cout << "invalid\n";
  }
}

B Yuki with emofunc and playf

链接：https://ac.nowcoder.com/acm/contest/18196/B

题目描述

Today HNU is holding the hucpc2021, yuki is very excited and wants to attend this amazing contest. Unfortunately, the contest needs a team to participate, yuki can register a team only himself. However, yuki too weak and he does not want to compete with other teams only himself. Therefore poor yuki asks volunteers for help. After the volunteer's introduction, yuki knows two genius persons called emofunc and playf already registered a team, poor yuki finds them and tells them about his embarrassing situation. Emofunc and playf are generous and kind-hearted mans, they are so glad and decide to let yuki join their team. After 5 hours of exciting competition, there is no doubt that emofunc and playf win the champion in hucpc2021! Yuki is a really lucky dog because he has done nothing in the whole competition, poor yuki is so curious why emofunc and playf so strong and asks them for some life experiences. Emofunc and playf are very generous mans so they tell yuki a lot. After that, yuki knows emofunc and playf not only are very genius and study hard but also are magicians.

Yuki has an apple and there are $N$ participants in hucpc2021, he wants to share the apple to every participants, so he decides to divide the apple into $N$ pieces. But yuki is shocked after he knows the magic power of emofunc and playf. Playf's magic power can copy an item into ten and emofunc's magic power can copy an item into what number he wants, but emofunc lies to yuki and he says his magic power only can copy an item into x (emofunc always pretend he so weak). Yuki knows both the magic power of emofunc and playf then he decides not to divide the apple and he wants to bother emofunc and playf.

Yuki has two choices and assumes he has $k$ apple(s) now:

Bother playf. Give all the apples yuki has to playf, then playf uses his magic and returns 10∗k{10*k}10∗k apples to yuki, which is mean yuki has $10 * k$ apples now.
Bother emofuc. Give an apple to emofuc, then emofunc uses his magic and returns x{x}x apples to yuki, which is mean yuki has $x-1+k$ apples now.

Yuki wants to minimize the total number of times of bother emofunc and playf, and let the total number of apples can be divided into N{N}N equal parts without split into pieces (image all apples are same), in other words, yuki has $k$ apples now and $k$ can be divided by $N$ . It is so difficult to yuki and yuki wants your help, can you tell the minimum number of total times to bother emofunc and playf to yuki?

输入描述:

1 2	A line contains two integers N{N}N,x{x}x are mentioned in the description. 1≤N≤1000000,1≤x≤1000000000

输出描述:

1	A line of an integer indicated the minimum number of total times to bother emofunc and playf, if there is no such way to satisfy yuki's require then output -1

示例1

输入

4 7

输出

示例2

输入

3 3

输出

示例3

输入

50 1

输出

示例4

输入

3 1

输出

-1

题目大意

给出数字n和x，初始的k=1。可以进行以下两种操作

$k=k * 10$
$k=k+x-1$

问最少操作多少次使得k是n的倍数，如果永远不能，则输出-1。

解题思路

让k是n的倍数，即满足 $k\%n==0$ ，倒推一下得到两种操作

$k=(k * 10)\%n$
$k=(k+x-1)\%n$

我们直接对问题进行bfs搜索最短操作数就行，范围是 $[0,n)$ ，起点为1，终点为0。

注意n=1时答案为0

代码

#include <bits/stdc++.h>
using namespace std;

queue<pair<int, int>> q;
int n, x;
int way_1(int k)
{
  return (k * 10) % n;
}
int way_2(int k)
{
  return (x - 1 + k) % n;
}
int flag[1000005];
void bfs()
{
  q.push(make_pair(1, 0));
  int cnt = 0;
  bool p = 0;
  while (!q.empty())
  {
    int tmp = q.front().first;
    int tmp2 = q.front().second;
    q.pop();
    int a = way_1(tmp), b = way_2(tmp);
    cnt = tmp2 + 1;
    if (a == 0 || b == 0)
    {
      p = 1;
      break;
    }
    if (flag[a] == 0)
      q.push(make_pair(a, cnt)), flag[a] = 1;
    if (flag[b] == 0)
      q.push(make_pair(b, cnt)), flag[b] = 1;
  }
  if (p)
    cout << cnt << endl;
  else
    cout << -1 << endl;
}

int main()
{
  cin >> n >> x;
  if (n != 1)
    bfs();
  else
    cout << 0 << endl;
}

D Queuing

链接：https://ac.nowcoder.com/acm/contest/18196/D

There has already been a long line in front of the cafeteria before the school bell rang.

When the cafeteria opens, everyone in the queue rushes to one of the n windows in the cafeteria at a speed close to the speed of light, forming a new n queue.

This process follows the following rules:

Each person rushes to the $\space i_{th}\space (1\leq i\leq n)$ window independently with a probability of $\cfrac{1}{n}$ ;
If A is in front of B at the beginning, and A and B rush to the same window, then A is still in front of B.

Playf is now ranked m in the team, which means that there are m-1 people ahead of Playf. Playf wants to know the expectation of rank of him in the new queue after the cafeteria opens.

输入描述:

1 2	One line, two integers n and m. 1<=n,m<=1e9

输出描述:

1	One line, a floating point number, indicates the expectation of Playf' rank in the new queue. At least accurate to 1e-6.

示例1

输入

2 3

输出

1	2.00000000

说明

There are 8 possibilities with equal probability

示例1

输入

2 4

输出

1	2.50000000

题目大意

给你n,m，n代表有n个窗口，m代表一开始前面有m-1个人，Playf排第m个。刚开始m个人全在第一个窗口，每个人有 $\cfrac{1}{n}$ 的概率去任意一个窗口，同时如果一开始A在B前面，A和B同时去一个窗口时，A还在B的前面。

问你换位后Playf在队伍中排位的期望。

解题思路

其实就是概率论的内容，可以看出来这是个二项分布，期望也就是np，这里的n是试验次数（除了Playf的人的个数），p是概率，对应关系为： $n\rightarrow m-1, p \rightarrow \cfrac{1}{n}$ ，由于求的是playf的排名期望，因此n对应的是playf前面的人的个数，所以此时除了playf的所有人的排名期望为 $\cfrac{m-1}{n}$ ，由于求的是playf的排名期望，加 1 即可（因为playf排在最后。

最后的公式为 $\cfrac{m-1}{n}+1$

代码

#include <bits/stdc++.h>
using namespace std;
long long n, m;
int main()
{
  cin >> n >> m;
  printf("%.10lf\n", (1.0 + (double)(m - 1) / (double)n));
}

F Team

链接：https://ac.nowcoder.com/acm/contest/18196/F

题目描述

2021 HNU programing competition is coming. Everyone is very exciting and want to participate in the competition.

We all know that this competition is a team competition, with three people in one team.

Playf is a poor guy who is very weak in programing, He wants to participate in the competition although he is very stupid. Fortunately, he knew two genius persons called Yuki and Emo, and they are so warm-hearted to let playf join them.

Everyone has a programming ability value. The ability value of a team is the sum of the ability value of three people. Now we know the ability value of Yuki, Emo and Playf. Playf wants to know the ability value of his team. Can you tell him ?

输入描述:

The first line contains an integer a indicating the programing ability value of Yuki

The second line contains an integer b indicating the programing ability value of Emo

The third line contains an integer c indicating the programing ability value of Playf

2^62≤a,b≤2^63,0≤c≤2

输出描述:

1	One integers indicating the ability value of Their team.

示例1

输入

1
2
3

9223372036854775808
9223372036854775808
0

输出

1	18446744073709551616

题目大意

输入a,b,c求a+b+c

2^62<=a,b<=263,0<=c<=2

解题思路

高精度加法或

usigned long long表示范围是[0,2^{64-1]，而a+b+c的结果是[2}63,2^64+2]刚好超过3个数字，用unsigned long long存储后特判一下即可。（pow不能存2^64）

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    unsigned long long a,b,c;
    cin >> a >> b >> c;
    if(a+b+c-3<=(18446744073709551612))
     cout << a+b+c;
    else{
        int t = (a%100+b%100+c-3)%10;
        if(t==3)cout <<"18446744073709551616\n";
        if(t==4)cout <<"18446744073709551617\n";
        if(t==5)cout <<"18446744073709551618\n";
    }
}

G Binbin's string

链接：https://ac.nowcoder.com/acm/contest/18196/G

题目描述

One day, Binbin picked up a string S at the beach, but she likes string T. Therefore, she needs to take some action on the string to make the string S become the string T. She has two kind of operation to modify the string. The first operation is to delete Y characters after the X-th position of the string (including the X-th character).The second operation is to insert the string A after the X-th position of the string, if you want to insert it at the beginning, just insert A after the 0th position.

For example, there is a string S="iwannaac", choose the first operation, delete 2 characters after the 7th character, it will become "iwanna"; then choose the second operation, insert the string after the 6th character "wa", it will become "iwannawa".

How many operations does Binbin need to take at least to turn the string S into a string T ?

1≤∣S∣,∣T∣≤100000, |S| represents the length of the string S. |T| represents the length of the string T.

输入描述:

1 2	The first line contains a string S consisting of lowercase letters. The second line contains a string T consisting of lowercase letters.

输出描述:

1	Output a number, indicating the minimum number of operations required to turn the string into the target string

示例1

输入

1 2	binbindisliketowearskirts binbinliketowearskirts

输出

示例2

输入

1 2	binbinliketowearskirts binbinliketowearlolita

输出

题目大意

给你两个字符串s1,s2 能对s1进行如下两种操作：

删除s1中连续的一段字符
在s1的某一位置添加一段字符

问最少操作多少次能把s1转换成s2

解题思路

有点有趣的题目hhh，思路就是，对于任意的字符串，最多操作两次就能把s1转换为s2，具体操作就是直接把s1删除后添加s2，也就是把整个s1替换成s2，两个操作。

因此我们只需要判断是否能通过一次删除或添加将s1变成s2。注意s1==s2的情况。

代码

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
  string s1, s2, tmp;
  cin >> s1 >> s2;
  if (s1.length() > s2.length())
    swap(s1, s2);
  int k = 0, p = 0;
  int s, e;
  for (int i = 0; i < s2.length() && k < s1.length(); i++)
  {
    if (s1[k] != s2[i])
    {
      s = i;
      break;
    }
    k++;
  }
  k = s1.length() - 1;
  for (int i = s2.length() - 1; i > 0; i--)
  {
    if (s1[k] != s2[i])
    {
      e = i;
      break;
    }
    k--;
  }
  tmp = "";
  for (int i = 0; i < s2.length(); i++)
  {
    if (i < s || i > e)
      tmp += s2[i];
  }
  if (s1 == s2)
    cout << 0 << endl;
  else if (tmp != s1)
    cout << 2 << endl;
  else
    cout << 1 << endl;
}

I Binbin and Balls

链接：https://ac.nowcoder.com/acm/contest/18196/I

题目描述

Binbin gets a special material ball. As everyone knows, Binbin is a curious girl, so she decides to study the hardness of the ball. She finds a building with n storeys. Every time she chooses a floor f arbitrarily and throws a ball down from the f floor. The ball may be intact, but it may also be broken. If the ball is broken, it cannot be used again. Unfortunately, Binbin only has two balls, she wants to find the largest x that if she throws the ball down from the x floor, the ball will not be broken. Also, she wants to know in the worst case, how many times she needs to throw at least to find the value of x.

Note: It is certain that if a ball will be broken after dropped from x-th floor, it will also be broken after dropped from y-th floor where y>x.

输入描述:

1 2	The first line contains an integer T (1<=T<=1e5)– the number of test cases. In the next T lines, each line contains an integer n (1<=n<=1e18) – the number of storeys of the building.

输出描述:

1	Output T lines. Each line contains an integer – the minimum number of times Binbin needs to throw in the worst case.

示例1

输入

1
2
3

2
1
5

输出

1
2

1
3

题目大意

给你两个相同的球，让你从n层楼中多次扔下去，求最差情况下找到让这个球从尽量高的层数扔下去不碎的层数的次数。

解题思路

设这个最少次数为 T ，则满足：在第T层扔下去时如果球碎掉，则这个层数在1~T-1之间，需要再扔T-1次，同理

如果没碎，就从T+T-1层往下扔，碎了就在T~2T-2之间······

推理得：最差情况下最多能保证得到1+2+3+4+·····+T楼的答案（全部包含），即 $\cfrac{(T+1)T}{2}$ 层楼的答案，我们让这个式子大于等于n，即 $\cfrac{(T+1)T}{2}\ge n$ ，化简后得到 $T^2+T-2n\ge0$ ，因为 $T\ge0$ ，求得T的最小值为：

\cfrac{-1\pm \sqrt{1+8n}}{2}

直接输出即可。

代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    long long n;
    cin >> n;
    long long ans =ceil((sqrt(1 + 8 * n) - 1) / 2);
    cout << ans << endl;
  }
}

查看评论