模拟赛链接

排名：\(\text{rank 1}\)
分数：\(100+100+70+20=290\)
终于有一次模拟赛不掉分了。

T1：最后一课 / dist

题目描述：

在一个平面直角坐标系上，给定一条直线 \(y=k\) 和两个点 \(P(x_1,y_1),Q(x_2,y_2)\)，求经过水平线的两点的最短距离。（\(k,x_1,y_1,x_2,y_2\le5\times10^8\)）

思路：

先考虑最简单的情况，两个点分别在直线两侧，我们知道两点之间线段最短，那么就直接连一条线段即可。
另一种情况两个点在直线同侧，这样就变成了一个经典的题目：将军饮马。我们可以对其中一个点做的对称轴为该直线的对称，再将两点连线，就可以了。

代码：

#include <bits/stdc++.h>

using namespace std;

long long k, xp, yp, xq, yq;

int main() {
  freopen("dist.in", "r", stdin);
  freopen("dist.out", "w", stdout);
  cin >> k >> xp >> yp >> xq >> yq;
  (yp >= k) == (yq >= k) && (yq -= (yq - k) * 2);
  cout << (xp - xq) * (xp - xq) + (yp - yq) * (yp - yq);
  return 0;
}

T2：日常 / shooot

题目描述

Kiana 正在基地里打靶。在一条长度为 \(m\) 的线段上，有 \(n\) 个靶子，第 \(i\) 个靶子的覆盖了 \([l_i,r_i]\) 这一段区间，且靶子之间不存在交（注意交为一个点也算有交）。对于第 \(i\) 个靶子，其中的 \([x_i, y_i]\) 这一段区间被标成了红色。

接下来，Kiana 进行了 \(k\) 次射击，会发射一发子弹打在线段的某个位置。对于每次射击，基地的人工智能--你需要输出对应的结果。具体的，假如射到了已经射过的靶子，输出 Again，假如没有射在靶子上，输出 Failed 。假如不符合以上两条，且打到了红色区域，则输出 Perfect ，否则输出 Normal。（\(1 \le n, k \le 10^5, 1 \le l_i \le x_i \le y_i \le r_i \le m \le 10^9\)）

思路：

看到这么多区间，还有多次询问点的状态，很容易想到二分（也可以想到线段树），由于这题的区间没有交集，所以很好处理。先二分找到这个点所在的区间，在看它是否在这个区间里，然后模拟即可。

代码：

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5;

int n, m, k;
bool vis[kMaxN];

struct Line {
  int l, x, y, r;
  bool operator<(const Line &y) const {
    return l < y.l;
  }
} a[kMaxN];

int main() {
  freopen("shoot.in", "r", stdin);
  freopen("shoot.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].l >> a[i].x >> a[i].y >> a[i].r;
  }
  sort(a + 1, a + 1 + n);
  for (int p, p1; k; k--) {
    cin >> p;
    p1 = upper_bound(a + 1, a + 1 + n, (Line){p, -1, -1, -1}) - a - 1;
    if (a[p1].r < p) {
      cout << "Failed\n";
    } else if (vis[p1]) {
      cout << "Again\n";
    } else if (a[p1].x <= p && p <= a[p1].y) {
      cout << "Perfect\n", vis[p1] = 1;
    } else {
      cout << "Normal\n", vis[p1] = 1;
    }
  }
  return 0;
}