2025春训第十四场

时隔好久，战斗爽终于复刻了😋，拿个榜一真不容易。

A. Christmas Tree Adapter#

终于有签到题了。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int a, w, v;
7
    cin >> a >> w >> v;
8
    if (a * v <= w) cout << 1 << endl;
9
    else cout << 0 << endl;
10
    return 0;
11
}

B. Cool Phone Numbers#

而且签到题还不止一道。

1
#include <iostream>
2
#include <set>
3

4
using namespace std;
5

6
set<char> st;
7

8
int main() {
9
    string s;
10
    cin >> s;
11
    for (char c : s) {
12
        if (isdigit(c)) st.insert(c);
13
    }
14
    cout << st.size() << endl;
15
    return 0;
16
}

C. Ready for Contest#

竟然有四道。

1
#include <iostream>
2

3
using namespace std;
4

5
bool a[100010][4];
6

7
int main() {
8
    int n, m;
9
    scanf("%d%d", &n, &m);
10
    for (int i = 1; i <= m; ++i) {
11
        int x, y;
12
        scanf("%d%d", &x, &y);
13
        a[x][y] = true;
14
    }
15
    for (int i = 1; i <= n; ++i) {
16
        if (a[i][1] & a[i][2]) printf("%d\n", i);
17
    }
18
    return 0;
19
}

D. Fixing the Tournament#

尽可能把排名低的两两组队，最后如果会输，还需要加上输的那一场。

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
int main() {
7
    int n, r;
8
    cin >> n >> r;
9
    cout << min((int)floor(log2((1 << n) - r + 1)) + 1, n) << endl;
10
    return 0;
11
}

E. Identical Letters#

比较经典的滑动窗口问题，枚举 26 个字母，遍历数组双指针维护到每一个位置时当前字母能构成的最长连续序列的长度，全部取 max 即可。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(0);
7
    cin.tie(0), cout.tie(0);
8
    string s;
9
    int n, m;
10
    cin >> s >> m;
11
    n = s.length();
12
    s = ' ' + s;
13
    int res = 0;
14
    for (char c = 'a'; c <= 'z'; ++c) {
15
        for (int i = 1, j = 1, del = 0; i <= n; ++i) {
16
            if (s[i] != c) del++;
17
            while (j <= i && del > m) if (s[j++] != c) del--;
18
            res = max(res, i - j + 1 - del);
19
        }
20
    }
21
    cout << res << endl;
22
    return 0;
23
}

F. Espresso Made Your Way#

我没有调红温，绝对没有🤮🤮🤮，那个 +13 的绝对不是我😭

设原来一杯的权重为 1，那么第一杯加进来的权重也是 1，再加第二杯的时候，因为前面已经浪费了一杯了，已有的这两杯的混合物变成一杯了，所以可以认为第二杯和前面两杯的量合起来是等价的，权重为 2，同理后面的权重是 4, 8, 16, 32……

所以最后调出来的东西☕️（🥛）占的比例肯定是

\frac{1}{2^n}(k_0 + \sum_{i = 0}^{n - 1}k_{i + 1} 2^i)

其中 n 为浪费的杯数，k 为 0 或 1. 其实求和符号里的就是一个整数的二进制表示，所以整个式子其实等价于 $\frac{k}{2^n}, k \in [0, 2^n] \cap \mathbb{Z}$ 。然后就好说了，枚举 k 验证能不能成立就行。需要注意枚举的范围，应该枚举到 $\log_2{10^{12}}$ ！！！

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
long long c1, m1, c2, m2;
7

8
int main() {
9
    cin >> c1 >> m1 >> c2 >> m2;
10
    if (c1 * m2 > c2 * m1) swap(c1, c2), swap(m1, m2);
11
    if (c1 == 0 || c2 == 0 || m1 == 0 || m2 == 0) cout << 0 << endl;
12
    else {
13
        m1 += c1, m2 += c2;
14
        int i = 0;
15
        while (true) {
16
            __int128_t l = 0, r = (1ll << i);
17
            bool f = false;
18
            while (l <= r) {
19
                __int128_t mid = (l + r) >> 1;
20
                if (mid * m2 > (__int128_t)c2 * (1ll << i)) r = mid - 1;
21
                else if (mid * m1 < (__int128_t)c1 * (1ll << i)) l = mid + 1;
22
                else {
23
                    f = true;
24
                    break;
25
                }
26
            }
27
            if (f) {
28
                cout << i << endl;
29
                return 0;
30
            }
31
            i++;
32
        }
33
    }
34
    return 0;
35
}

这是正着试的办法，还可以反着尝试，更 easy 一些，不需要二分尝试，把 C 和 M 不断除以 2，直到最后一个不相等的位置。

G. Speed Ups#

相对比较好做，线性 dp 维护到每一个加速的位置的最短时间（这里指的是可以踩到这个加速的情况，不包括上一个加速没用完路过这里的情况），然后枚举起点和所有加速的位置，算走到终点的时长取 min.

1
#include <iostream>
2
#include <algorithm>
3
#include <iomanip>
4
#define int long long
5

6
using namespace std;
7

8
struct Node {
9
    int x, m, d;
10
} a[1010];
11
int f[1010];
12

13
signed main() {
14
    int n, l;
15
    scanf("%lld%lld", &n, &l);
16
    for (int i = 1; i <= n; ++i) {
17
        scanf("%lld%lld%lld", &a[i].x, &a[i].m, &a[i].d);
18
    }
19
    sort(a + 1, a + n + 1, [](Node a, Node b) {
20
        return a.x < b.x;
21
    });
22
    for (int i = 1; i <= n; ++i) {
23
        f[i] = 0x3f3f3f3f;
24
        for (int j = 0; j < i; ++j) {
25
            if ((long long)a[j].m * a[j].d <= (a[i].x - a[j].x)) {
26
                f[i] = min(f[i], f[j] + a[j].d + (a[i].x - a[j].x - a[j].m * a[j].d));
27
            }
28
        }
29
    }
30
    double res = 1e18;
31
    for (int i = 0; i <= n; ++i) {
32
        if ((long long)a[i].x + (long long)a[i].m * a[i].d <= l) res = min(res, (double)(f[i] + a[i].d + (l - a[i].m * a[i].d - a[i].x)));
33
        else res = min(res, (double)(f[i]) + (double)(l - a[i].x) / a[i].m);
34
    }
35
    printf("%lf\n", res);
36
    return 0;
37
}

H. Magnetic Attractions#

众所周知，根据高中物理知识，这个区域是一个圆形区域，以 s 为原点， $\vec{sS}$ 方向为 x 轴，垂直的方向为 y 轴重新建一个坐标系，记 S 的新的坐标为 (d, 0).

\frac{s}{x^2 + y^2} = \frac{S}{(x - d)^2 + y^2}

整理可得

(x - \frac{s}{s - S})^2 + y^2 = \frac{sd - sd^2}{s - S}

r^2 = \frac{sd - sd^2}{s - S}

直接套圆的面积公式就能算出来

1
#include <iostream>
2
#include <cmath>
3

4
using namespace std;
5

6
int main() {
7
    double s1, x1, y1, s2, x2, y2;
8
    cin >> s1 >> x1 >> y1 >> s2 >> x2 >> y2;
9
    double d = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
10
    double r2 = pow(s1 * d / (s2 - s1), 2) - s1 * d * d / (s1 - s2), pi = acos(-1);
11
    printf("%lf\n", pi * r2);
12
    return 0;
13
}

I. Hotel Rooms#

单点修改，区间查询，线段树或者树状数组都可以，个人感觉树状数组好写一点，于是就写的树状数组，也是一遍秒了。

1
#include <iostream>
2

3
using namespace std;
4

5
int n, m;
6
int tr[500010];
7
bool f[500010];
8
void add(int u, int val) {
9
    for (; u <= n; u += u & -u) {
10
        tr[u] += val;
11
    }
12
}
13

14
int query(int u) {
15
    int res = 0;
16
    for (; u; u -= u & -u) {
17
        res += tr[u];
18
    }
19
    return res;
20
}
21

22
int main() {
23
    scanf("%d%d", &n, &m);
24
    for (int i = 1; i <= n; ++i) {
25
        add(i, 1);
26
    }
27
    for (int i = 1; i <= m; ++i) {
28
        char s[2];
29
        scanf("%s", s);
30
        if (s[0] == 'A') {
31
            int l, r;
32
            scanf("%d%d", &l, &r);
33
            printf("%d\n", query(r) - query(l - 1));
34
        }
35
        else {
36
            int x;
37
            scanf("%d", &x);
38
            if (!f[x]) f[x] = true, add(x, -1);
39
        }
40
    }
41
    return 0;
42
}

Star's Blog