AtCoder beginner contest 374

建议查看中文题面，不要问为什么*(问就是，英文题面就是复制过来的，中文体面精简些)

A.Takahashi san 2

Takahashi san 2

题目描述

KEYENCE has a culture of addressing everyone with the suffix “-san,” regardless of roles, age, or positions.
You are given a string $S$ consisting of lowercase English letters.
If $S$ ends with san, print Yes; otherwise, print No.

判断字符串末尾是否有 san 这个后缀

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::string s;
  std::cin >> s;
  std::string t = s.substr(s.size() - 3);
  std::cout << (t == "san" ? "Yes" : "No") << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

B.Unvarnished Report

Unvarnished Report

题目描述

You are given two strings $S$ and $T$, consisting of lowercase English letters.
If $S$ and $T$ are equal, print $0$; otherwise, print the position of the first character where they differ.
Here, if the $i$-th character exists in only one of $S$ and $T$, consider that the $i$-th characters are different.

More precisely, if $S$ and $T$ are not equal, print the smallest integer $i$ satisfying one of the following conditions:

  • $1\leq i\leq |S|$, $1\leq i\leq |T|$, and $S_i\neq T_i$.
  • $|S| < i \leq |T|$.
  • $|T| < i \leq |S|$.

Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively, and $S_i$ and $T_i$ denote the $i$-th characters of $S$ and $T$, respectively.

给定字符串 $S$ 和 $T$,若字符串 $S$ 和字符串 $T$ 完全相等,则输出 $0$ 否则输出 $S$ 和 $T$ 第一个不相同的位置.

解题思路

首先判断两个字符串是否相同,

若相同直接输出 $0$

否则用 $for$ 遍历一次字符串

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  std::string s, t;
  std::cin >> s >> t;
  if (s == t) {
    std::cout << 0 << endl;
    return;
  }
  for(int i = 0; i < std::max(s.size(), t.size()); i++) {
    if (s[i] != t[i]) {
      std::cout << i + 1 << endl;
      break;
    }
  }
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

C.Separated Lunch

Separated Lunch

题目描述

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have $N$ departments, and the number of people in the $i$-th department $(1\leq i\leq N)$ is $K_i$.

When assigning each department to Group $A$ or Group $B$, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group $A$ and Group $B$ do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group $A$, and the total number of people in departments assigned to Group $B$.

给出一个数 $n$, 和一个长度为 $n$ 的数组 $K$, 将这个数组划分为 $A$ , $B$两个部分,使得这两个部分的和 $S_{A}$ 和 $S_{B}$ 中的最大值最小

数据范围:
$2 \leq n \leq 20$,
$1 \leq K_{i} \leq 10^{8}$

解题思路

瞄一眼中文题面, 有点像 $01$ 背包, 但是你可以发现数据范围好像不能用背包，有没有其他方法呢?

好像 $n$ 的范围比较小，我们可以使用 $dfs$ 来搜索每一种情况，最多为 $2^{20}$,那么怎么判断哪种情况最优?只需要满足 $S_{A}$和 $S_{B}$ 的差值最小，答案即为差值最小时的最大值。

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, w = 0;
  std::cin >> n;
  std::vector<int> a(n);
  for(int i = 0; i < n; i++) {
    std::cin >> a[i];
    w += a[i];
  }


  std::vector<int> f(n, 0);
  int mi = inf, ans = inf;
  std::function<void(int)> dfs = ([&](int u) {
    if (u >= n) {
      int s = 0;
      for(int i = 0; i < n; i++) {
        if (f[i]) {
          s += a[i];
        }
      }
      if (mi >= abs(w - s - s)) {
        mi = abs(w - s - s);
        ans = std::min(ans, std::max(s, w - s));
      }
      return;
    }
    f[u] = 1;
    dfs(u + 1);
    f[u] = 0;
    dfs(u + 1);
  });

  dfs(0);

  std::cout << ans << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}

D.Laser Marking

Laser Marking

题目描述

There is a printing machine that prints line segments on the $xy$-plane by emitting a laser.

  • At the start of printing, the laser position is at coordinate $(0, 0)$.

  • When printing a line segment, the procedure below is followed.

    • First, move the laser position to one of the endpoints of the line segment.
      • One may start drawing from either endpoint.
    • Then, move the laser position in a straight line from the current endpoint to the other endpoint while emitting the laser.
      • It is not allowed to stop printing in the middle of a line segment.

  • When not emitting the laser, the laser position can move in any direction at a speed of $S$ units per second.

  • When emitting the laser, the laser position can move along the line segment being printed at a speed of $T$ units per second.

  • The time required for operations other than moving the laser position can be ignored.

Takahashi wants to print $N$ line segments using this printing machine.
The $i$-th line segment connects coordinates $(A_i, B_i)$ and $(C_i, D_i)$.
Some line segments may overlap, in which case he needs to print the overlapping parts for each line segment separately.

What is the minimum number of seconds required to complete printing all the line segments when he operates the printing machine optimally?

在一个平面上给出 $n$ 条线段的起始点$(A_{i}, B_{i})$和终点$(C_{i}, D_{i})$ 现在要使用激光打印机打印这些线段,在打印线段时的移动速度为每秒 $T$ 个单位长度, 不打印的时候的移动速度为每秒 $S$ 个单位长度, 问打印这些线段的最短时间为多少？

解题思路

由于一个线段可以从两个端点中的任意一个开始打印，看来这个题又和上面一个题一样使用 $dfs$ ,循环初始到达线段,先移动到其中一个端点,再移动到另一个端点，答案记录下来，再$dfs$, $dfs$函数中的参数 $x$, $y$, $u$, $v$ 表示在此之前是从点$(x,y)$ 移动到了 $(u,v)$.其实 $dfs$ 只传当前位置就行了,只是个人方便识别.

参考代码

hypot()函数详解：
hypot(x, y) 返回的是浮点型数据类型,值为 $\sqrt{x^{2} + y^{2}}$ 即将$x, y$作为直角三角形的两条直角边的斜边。
hypot(x,y,z) 返回类型同上值为 $\sqrt{x^{2} + y^{2} + z^{2}}$

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, s, t;
  std::cin >> n >> s >> t;
  std::vector<int> A(n), B(n), C(n), D(n);
  for(int i = 0; i < n; i++)
    std::cin >> A[i] >> B[i] >> C[i] >> D[i];

  std::vector<bool> vis(n, false);
  double ans = INFINITY, w = 0;
  auto check = [&]() -> bool {
    for(int i = 0; i < n; i++) if (!vis[i]) return false;
    return true;
  };

  std::function<void(int, int, int, int)> dfs = ([&](int x, int y, int u, int v) -> void {
    if (check()) {
      ans = std::min(ans, w);
//      std::cout << ans << endl;
      return;
    }

    for(int i = 0; i < n; i++) {
      if (!vis[i]) {
        vis[i] = true;
        auto t1 = std::hypot(u - A[i], v - B[i]) / s;
        auto t2 = std::hypot(u - C[i], v - D[i]) / s;
        auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
        w += tt, w += t1;
        dfs(A[i], B[i], C[i], D[i]);
        w -= t1, w += t2;
        dfs(C[i], D[i], A[i], B[i]);
        w -= t2, w -= tt;
        vis[i] = false;
      }
    }
  });

  for(int i = 0; i < n; i++) {
    vis[i] = true;
    auto t1 = std::hypot(A[i], B[i]) / s;
    auto t2 = std::hypot(C[i], D[i]) / s;
    auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
    w = t1 + tt;
    dfs(A[i], B[i], C[i], D[i]);
    w = t2 + tt;
    dfs(C[i], D[i], A[i], B[i]);
    vis[i] = false;
  }
  std::cout << fix(16) << ans << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  solve();
  return 0;
}