总结
考场估分：\([0, 95] + 100 + 0 + [0, 20] = [100, 215]\)
实际得分：\(40 + 100 + 0 + 20 = 160\)，寄寄寄寄寄寄寄寄寄寄。
\(\texttt{T1 dist}\)
题意
有一条直线 \(y = k\)，两点 \(P\) 和 \(Q\)，求直线上一点 \(R\) 使得 \(\mid PR \mid + \mid RQ \mid\) 的值最小。
分析
将军饮马模板，但是不会/fn/fn/fn
时间复杂度显然 \(\Theta(1)\)。
寄因
挂分：\(\text{60pts}\)
原因：小学就学了的将军饮马，但是我没学/fn/fn/fn/fn/fn
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k;
int x, y, x2, y2;
int dist(int x, int y, int x2, int y2) {
return (x - x2) * (x - x2) + (y - y2) * (y - y2);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> k >> x >> y >> x2 >> y2;
if (y > y2) {
swap(y, y2);
swap(x, x2);
}
if (y <= k && k <= y2) {
cout << dist(x, y, x2, y2) << '\n';
} else if (k < y) {
cout << min(dist(x, k - (y - k), x2, y2), dist(x, y, x2, (k - (y2 - k)))) << '\n';
} else if (k > y2) {
cout << min(dist(x, y, x2, k + k - y2), dist(x, k + k - y, x2, y2)) << '\n';
}
return 0;
}
\(\texttt{T2 shoot}\)
题意
有一堆区间，每个区间内部有一个子区间，询问几次，每次给定一个坐标，问这个坐标在哪个区间里，如果不在区间里输出 Failed，如果已经到过这个区间输出 Again，如果在这个区间的子区间里输出 Perfect，如果在这个区间里输出 Normal。
分析
要么离散化然后线段树，要么直接二分函数，要么手打二分。
时间复杂度均为 \(\Theta(k \log n)\)，但显然后者常数更优。
部分分
对于 \(30\%\) 的数据，\(1 \le n, k \le 1000\)，暴力找区间就行了。
对于另 \(20\%\) 的数据，\(1 \le m, l_i, r_i \le 10^6\)，线段树维护一下。
对于另 \(30\%\) 的数据，\(l_i = x_i, r_i = y_i\)，不用判断 Normal 的情况。
寄因
挂分：\(\text{0pts}\)
原因：没挂。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
#endif
namespace Fastio {
struct Reader {
template <typename T>
Reader& operator>>(T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator>>(char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator>>(char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer {
template <typename T>
Writer& operator<<(T x) {
if (x == 0) {
putchar('0');
return *this;
}
if (x < 0) {
putchar('-');
x = -x;
}
static int sta[45];
int top = 0;
while (x) {
sta[++top] = x % 10;
x /= 10;
}
while (top) {
putchar(sta[top] + '0');
--top;
}
return *this;
}
Writer& operator<<(char c) {
putchar(c);
return *this;
}
Writer& operator<<(char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator<<(const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer() {}
} cout;
} // namespace Fastio
#define cin Fastio ::cin
#define cout Fastio ::cout
#define endl Fastio ::endl
/* --------------- fast io --------------- */ // end
const int kMaxN = 1e5 + 5;
int n, m, k;
struct Node {
int l, r;
int x, y;
friend bool operator<(const Node& a, const Node& b) {
return a.l < b.l;
}
} a[kMaxN];
bool vis[kMaxN];
signed main() {
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 + n + 1);
for (int i = 1; i <= k; i++) {
int x;
cin >> x;
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (a[mid].r < x) {
l = mid + 1;
} else {
r = mid;
}
}
if (x < a[l].l || x > a[l].r) {
cout << "Failed";
} else if (vis[l]) {
cout << "Again";
vis[l] = 1;
} else if (x >= a[l].x && x <= a[l].y) {
cout << "Perfect";
vis[l] = 1;
} else {
cout << "Normal";
vis[l] = 1;
}
cout << '\n';
}
return 0;
}
\(\texttt{T3 max}\)
题意
给定长 \(n\) 的序列 \(a\)，求最大的 \(\forall 1 \le l \le r \le n\)，\(\left|\sum\limits_{i = l}^{r} a_i \right|\)。
分析
分两种情况乱搞讨论，显然对于绝对值只有两种可能：负数或者正数，没了，ST 表维护一下前缀和最大值，可以了。
时间复杂度 \(\Theta(m \log n)\)。
寄因
挂分：\(\text{20pts}\)
原因：打表打的太忘我，代码 \(\text{34.53MB}\)。。。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kMaxN = 2e5 + 5;
int n, q;
ll sum[kMaxN + 5], stmn[kMaxN + 5][20], stmx[kMaxN + 5][20];
int lg2[kMaxN + 5];
ll qmn(int l, int r) {
if (l > r) {
return 1e18;
}
if (l == 0) {
return min(0ll, qmn(l + 1, r));
}
int k = lg2[r - l + 1];
return min(stmn[l][k], stmn[r - (1 << k) + 1][k]);
}
ll qmx(int l, int r) {
if (l > r) {
return -1e18;
}
if (l == 0) {
return max(0ll, qmx(l + 1, r));
}
int k = lg2[r - l + 1];
return max(stmx[l][k], stmx[r - (1 << k) + 1][k]);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= n; i++) {
ll t;
cin >> t;
sum[i] = sum[i - 1] + t;
stmn[i][0] = stmx[i][0] = sum[i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
stmn[i][j] = min(stmn[i][j - 1], stmn[i + (1 << (j - 1))][j - 1]);
stmx[i][j] = max(stmx[i][j - 1], stmx[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
l--;
ll mx = qmx(l, r), mn = qmn(l, r);
cout << mx - mn << '\n';
}
return 0;
}
\(\texttt{T4 skill}\)
题意
有 \(n\) 个二元组 \((A_i, B_i)\)，选择一个二元组的排列，使得：
-
\(\forall 1 \le i < n\)，\(A_i = A_{i + 1} \lor B_i = B_{i + 1}\)。
-
\(\forall 1 < i < n\)，\(\lnot (A_{i - 1} = A_i = A_{i + 1} \lor B_{i - 1} = B_i = B_{i + 1})\)。
如果有解，输出 Yes 并输出字典序最小的排列；否则输出 No。
分析
扬跃顶真，鉴定为：图论凸轮，我们可以把 \((a, b)\) 这个二元组看成一条边，然后找一下欧拉回路就行了，因为要求字典序最小，，如果只有欧拉路径，那么可以在起点与终点之间连一条下标为 \(0\) 的边。
时间复杂度很小的 \(\Theta(n)\)。
寄因
挂分：\(\text{0pts}\)
原因：没挂，只打了暴力，这就是暴力带给我的自信
代码
点击查看咕咕咕
咕咕咕。