备战2025区域赛组队训练赛第 18 场

B. Call of Accepted#

基本上就是中缀表达式求值，开两个栈模拟即可，还是挺好写的。

1
#include <iostream>
2
#include <sstream>
3
using namespace std;
4

5
const int N = 200;
6

7
int w(char c) {
8
    if (c == '+' || c == '-') return 1;
9
    else if (c == '*') return 2;
10
    else if (c == 'd') return 3;
11
    else return 0;
12
}
13

14
pair<int, int> st1[N];
15
char st2[N], tp1, tp2;
16

17
void calc() {
18
    auto a = st1[tp1 - 1], b = st1[tp1];
19
    char c = st2[tp2--];
20
    tp1--;
21
    if (c == '+') a.first += b.first, a.second += b.second;
22
    else if (c == '-') a.first -= b.second, a.second -= b.first;
23
    else if (c == '*') {
24
        int t[] = {a.first * b.first, a.second * b.second, a.first * b.second, a.second * b.first};
25
        a = {min(min(t[0], t[1]), min(t[2], t[3])), max(max(t[0], t[1]), max(t[2], t[3]))};
26
    }
27
    else if (c == 'd') {
28
        a = {a.first, a.second * b.second};
29
    }
30
    else cout << "awa" << endl;
31
    st1[tp1] = a;
32
}
33

34
int main() {
35
    ios::sync_with_stdio(0);
36
    cin.tie(0), cout.tie(0);
37
    string s;
38
    while (cin >> s) {
39
        tp1 = tp2 = 0;
40
        stringstream ss(s);
41
        char c;
42
        int num;
43
        while (ss.peek() != EOF) {
44
            if (isdigit(ss.peek())) {
45
ss >> num;
46
st1[++tp1] = {num, num};
47
            }
48
            else {
49
ss >> c;
50
if (c == '(') st2[++tp2] = c;
51
else if (c == '+' || c == '-') {
52
    while (tp2 && w(st2[tp2]) >= 1) {
53
        calc();
54
    }
55
    st2[++tp2] = c;
56
}
57
else if (c == '*') {
58
    while (tp2 && w(st2[tp2]) >= 2) {
59
        calc();
60
    }
61
    st2[++tp2] = c;
62
}
63
else if (c == 'd') {
64
    while (tp2 && w(st2[tp2]) >= 3) {
65
        calc();
66
    }
67
    st2[++tp2] = c;
68
}
69
else {
70
    while (st2[tp2] != '(') {
71
        calc();
72
    }
73
    tp2--;
74
}
75
            }
76
        }
77
        while (tp2) calc();
78
        printf("%d %d\n", st1[tp1].first, st1[tp1].second);
79
    }
80
    return 0;
81
}

D. Made In Heaven#

第 k 短路，可以用 A*，估值函数用反图 Dijkstra 从终点跑出来的最短路，第 k 次搜到终点的时候走过的路径就是第 k 短路。

我 A* 没有判断不连通又爆时间又爆空间的，改完就对了。

1
#include <iostream>
2
#include <cstring>
3
#include <queue>
4
#include <tuple>
5

6
using namespace std;
7
const int N = 1010, M = 10010;
8

9
int head[N], head_rev[N], ver[M * 2], ne[M * 2], w[M * 2], tot;
10
int dis[N];
11
bool vis[N];
12

13
int n, m, s, e, k;
14
int v[N];
15
int t;
16

17
void add(int *head, int x, int y, int z) {
18
    ver[++tot] = y;
19
    ne[tot] = head[x];
20
    head[x] = tot;
21
    w[tot] = z;
22
}
23

24
void dijkstra(int s) {
25
    priority_queue<pair<int, int>> q;
26
    memset(dis, 0x3f, sizeof(dis));
27
    memset(vis, 0, sizeof(vis));
28
    dis[s] = 0;
29
    q.emplace(-dis[s], s);
30
    while (!q.empty()) {
31
        int x = q.top().second;
32
        q.pop();
33
        if (vis[x]) continue;
34
        vis[x] = true;
35
        for (int i = head_rev[x]; i; i = ne[i]) {
36
            int y = ver[i];
37
            if (dis[y] > dis[x] + w[i]) {
38
dis[y] = dis[x] + w[i];
39
q.emplace(-dis[y], y);
40
            }
41
        }
42
    }
43
}
44

45
void solve() {
46
    memset(head, 0, sizeof(head));
47
    memset(head_rev, 0, sizeof(head_rev));
48
    memset(v, 0, sizeof(v));
49
    tot = 0;
50
    scanf("%d%d%d%d", &s, &e, &k, &t);
51
    for (int i = 1; i <= m; ++i) {
52
        int x, y, z;
53
        scanf("%d%d%d", &x, &y, &z);
54
        add(head, x, y, z);
55
        add(head_rev, y, x, z);
56
    }
57
    dijkstra(e);
58
    priority_queue<pair<int, int>> q;
59
    q.emplace(-dis[s], s);
60
    while (!q.empty()) {
61
        auto [cost, x] = q.top();
62
        q.pop();
63
        v[x]++;
64
        if (v[x] > k) continue;
65
        if (x == e) {
66
            if (-cost > t) {
67
printf("Whitesnake!\n");
68
return;
69
            }
70
            if (v[x] == k) {
71
printf("yareyaredawa\n");
72
return;
73
            }
74
        }
75
        for (int i = head[x]; i; i = ne[i]) {
76
            int y = ver[i];
77
            if (v[y] > k) continue;
78
            q.emplace(cost + dis[x] - w[i] - dis[y], y);
79
        }
80
    }
81
    printf("Whitesnake!\n");
82
}
83

84
int main() {
85
    while (scanf("%d%d", &n, &m) != EOF) {
86
        solve();
87
    }
88
    return 0;
89
}

E. The cake is a lie^补#

刚开始数据有问题，没有填数据，过样例的都过了。后来我调对了，重判的时候被卡掉了，时间限制 1s，我跑 1.5s，绝望.jpg。

$O(n^3 \log n)$ 做法#

先说一下被卡掉的思路。

枚举一条弦，假定圆心在中垂线上，初始化认为这条弦是直径；
遍历所有的点，统计当前在圆内的点数，同时根据在圆内和圆外和在直径两侧分成四块，正弦定理求出来包含三个点的圆的半径，按半径分别排序；
朝一个方向扩展圆，双指针遍历这个方向圆外点和另一个方向的圆内点，随着并入外面的点，里面的点会被排出圆外，同时要维护圆内的点数；
恢复到直径，朝反方向在扩展；
在以上过程中如果点数 > s，就直接更新答案；
继续枚举其他弦。

代码是这样的，真的只差一点就过去了。

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#include <vector>
5
#include <iomanip>
6
#define x first
7
#define y second
8
using namespace std;
9
typedef pair<int, int> PII;
10
const int N = 310;
11
const double eps = 1e-7;
12
PII a[N];
13
double b[N], c[N], d[N], e[N];
14

15
PII operator -(const PII &a, const PII &b) {
16
    return {a.x - b.x, a.y - b.y};
17
}
18

19
PII operator +(const PII &a, const PII &b) {
20
    return {a.x + b.y, a.y - b.y};
21
}
22

23
int operator *(const PII &a, const PII &b) {
24
    return a.x * b.y - a.y * b.x;
25
}
26

27
int operator &(const PII &a, const PII &b) {
28
    return a.x * b.x + a.y * b.y;
29
}
30

31
double getlen(const PII &a) {
32
    return sqrt(a.x * a.x + a.y * a.y);
33
}
34

35
double calc_r(const PII &a, const PII &b, const PII &c) {
36
    PII t1 = b - a, t2 = c - a, t3 = c - b;
37
    return getlen(t3) / ((t1 * t2) / getlen(t1) / getlen(t2)) / 2;
38
}
39

40
void solve() {
41
    int n, s, R;
42
    cin >> n >> s;
43
    for (int i = 1; i <= n; ++i) {
44
        cin >> a[i].x >> a[i].y;
45
    }
46
    cin >> R;
47
    if (n < s) {
48
        cout << "The cake is a lie.\n";
49
        return;
50
    }
51
    else if (s == 1) {
52
        cout << R << ".0000\n";
53
        return;
54
    }
55
    double res = 100000;
56
    bool f = true;
57
    for (int i = 2; i <= n; ++i) {
58
        if (a[i] != a[1]) {
59
            f = false;
60
            break;
61
        }
62
    }
63
    if (f) {
64
        cout << R << ".0000\n";
65
        return;
66
    }
67
    for (int i = 1; i <= n; ++i) {
68
        for (int j = i + 1; j <= n; ++j) {
69
            auto &p = a[i], &q = a[j];
70
            int t = 0, l1 = 0, l2 = 0, l3 = 0, l4 = 0;
71
            for (int k = 1; k <= n; ++k) {
72
int dot = (a[k] - a[i]) & (a[k] - a[j]);
73
if (dot <= 0) {
74
    t++;
75
}
76
double r = calc_r(p, q, a[k]);
77
if (fabs(r) >= eps) {
78
    if (dot <= 0) {
79
        if (r > 0) b[++l1] = r;
80
        else c[++l2] = fabs(r);
81
    }
82
    else {
83
        if (r > 0) d[++l3] = r;
84
        else e[++l4] = fabs(r);
85
    }
86
}
87
            }
88
            if (t >= s) {
89
res = min(res, getlen(p - q) / 2);
90
continue;
91
            }
92
            sort(b + 1, b + l1 + 1);
93
            sort(c + 1, c + l2 + 1);
94
            sort(d + 1, d + l3 + 1);
95
            sort(e + 1, e + l4 + 1);
96
            int bk = t;
97
            for (int k = 1, l = 1; k <= l4; ++k) {
98
double r = e[k];
99
t++;
100
while (l <= l1 && b[l] < r) l++, t--;
101
if (t >= s) res = min(res, r);
102
            }
103
            t = bk;
104
            for (int k = 1, l = 1; k <= l3; ++k) {
105
double r = d[k];
106
t++;
107
while (l <= l2 && c[l] < r) l++, t--;
108
if (t >= s) res = min(res, r);
109
            }
110
        }
111
    }
112
    cout << fixed << setprecision(4) << res + R << '\n';
113
}
114

115
int main() {
116
    ios::sync_with_stdio(0);
117
    cin.tie(0), cout.tie(0);
118
    int T;
119
    cin >> T;
120
    while (T--) {
121
        solve();
122
    }
123
    return 0;
124
}

$O(n^2 \log n \log (1e12))$ 做法#

后来搜了题解之后学会了更快的做法，我的第一版思路和这个做法类似，但是我没有想到处理圆心的方法。

二分半径；枚举所有的圆，依次固定每一个圆，求所有的和他间距在 2r 以内的圆（包括他自己）和他的交点的极角，离散化极角，做差分前缀和，覆盖最多的一块如果不小于 s 为合法，否则不合法，最后成功 363ms 过了。

1
#include <iostream>
2
#include <cmath>
3
#include <algorithm>
4
#include <vector>
5
#include <iomanip>
6
#define x first
7
#define y second
8
using namespace std;
9
typedef pair<int, int> PII;
10
const int N = 310;
11
const double eps = 1e-8;
12
PII a[N];
13
pair<double, int> b[N * 2];
14
double dis[N][N], ang[N][N];
15
int n, s, R;
16

17
int dcmp(double a, double b) {
18
    if (fabs(a - b) < eps) return 0;
19
    else if (a < b) return -1;
20
    else return 1;
21
}
22

23
PII operator -(const PII &a, const PII &b) {
24
    return {a.x - b.x, a.y - b.y};
25
}
26

27
PII operator +(const PII &a, const PII &b) {
28
    return {a.x + b.y, a.y - b.y};
29
}
30

31
int operator *(const PII &a, const PII &b) {
32
    return a.x * b.y - a.y * b.x;
33
}
34

35
int operator &(const PII &a, const PII &b) {
36
    return a.x * b.x + a.y * b.y;
37
}
38

39
double getlen(const PII &a) {
40
    return sqrt(a.x * a.x + a.y * a.y);
41
}
42

43
double getangle(const PII &a) {
44
    return atan2(a.y, a.x);
45
}
46

47
bool check(double r) {
48
    for (int i = 1; i <= n; ++i) {
49
        int l = 0;
50
        for (int j = 1; j <= n; ++j) {
51
            if (dcmp(dis[i][j], r * 2) <= 0) {
52
double t = acos(dis[i][j] / 2 / r);
53
b[++l] = {ang[i][j] - t, 1};
54
b[++l] = {ang[i][j] + t, -1};
55
            }
56
        }
57
        sort(b + 1, b + l + 1, [](pair<double, int> a, pair<double, int> b) {
58
            return dcmp(a.first, b.first) == 0 ? a.second > b.second : dcmp(a.first, b.first) < 0;
59
        });
60
        int t = 0;
61
        for (int i = 1; i <= l; ++i) {
62
            t += b[i].second;
63
            if (t >= s) return true;
64
        }
65
    }
66
    return false;
67
}
68

69
void solve() {
70
    cin >> n >> s;
71
    for (int i = 1; i <= n; ++i) {
72
        cin >> a[i].x >> a[i].y;
73
    }
74
    for (int i = 1; i <= n; ++i) {
75
        for (int j = 1; j <= n; ++j) {
76
            dis[i][j] = getlen(a[j] - a[i]);
77
            ang[i][j] = getangle(a[j] - a[i]);
78
        }
79
    }
80
    cin >> R;
81
    if (n < s) {
82
        cout << "The cake is a lie.\n";
83
        return;
84
    }
85
    // cout << check(0.3) << endl;
86
    double l = 0.0, r = 10000;
87
    while (l + eps < r) {
88
        double mid = (l + r) / 2;
89
        if (check(mid)) r = mid;
90
        else l = mid;
91
    }
92
    cout << fixed << setprecision(4) << l + R << '\n';
93
}
94

95
int main() {
96
    ios::sync_with_stdio(0);
97
    cin.tie(0), cout.tie(0);
98
    int T;
99
    cin >> T;
100
    while (T--) {
101
        solve();
102
    }
103
    return 0;
104
}

F. Fantastic Graph ^欠#

上下界网络流，待学。

G. Spare Tire ^欠#

数学题，待补。

I. Lattice’s basics in digital electronics ^欠#

大模拟，待补。

K. Supreme Number#

我们打表发现只有这几个数，所以问题就直接解决了。

1
1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317

Star's Blog

B. Call of Accepted#

D. Made In Heaven#

E. The cake is a lie补#

O(n3log⁡n)O(n^3 \log n)O(n3logn) 做法#

O(n2log⁡nlog⁡(1e12))O(n^2 \log n \log (1e12))O(n2lognlog(1e12)) 做法#

F. Fantastic Graph 欠#

G. Spare Tire 欠#

I. Lattice’s basics in digital electronics 欠#