模拟赛链接
排名：\(\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;
}