2026寒假集训个人训练赛第十七场

A. 珂朵莉与数字#

可以二分答案，但是小心爆 long long，我就这么 wa 的……

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6

7
LL n, p;
8

9
LL check(LL mid) {
10
    __int128_t res = 1;
11
    for (int i = 0; i < p; ++i) {
12
        res *= mid;
13
        if (res > n) return false;
14
    }
15
    return true;
16
}
17

18
int main() {
19
    ios::sync_with_stdio(0);
20
    cin.tie(0), cout.tie(0);
21
    int T;
22
    cin >> T;
23
    while (T--) {
24
        cin >> n >> p;
25
        LL l = 0, r = n;
26
        while (l < r) {
27
            LL mid = l + r + 1 >> 1;
28
            if (check(mid)) l = mid;
29
            else r = mid - 1;
30
        }
31
        cout << l << endl;
32
    }
33
    return 0;
34
}

B. 珂朵莉与序列#

排个序，这样就可以把前面的和后面的拆开去绝对值，然后维护一个前缀和和后缀和即可 $O(1)$ 得出一个位置的答案。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 100010;
8
pair<LL, LL> a[N];
9
LL pre[N], suf[N], res[N];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n;
15
    cin >> n;
16
    for (int i = 1; i <= n; ++i) cin >> a[i].first, a[i].second = i;
17
    sort(a + 1, a + n + 1);
18
    for (int i = n; i; --i) suf[i] = suf[i + 1] + a[i].first;
19
    for (int i = 1; i <= n; ++i) {
20
        pre[i] = pre[i - 1] + a[i].first;
21
        res[a[i].second] = a[i].first * i - pre[i] + suf[i] - a[i].first * (n - i + 1);
22
    }
23
    for (int i = 1; i <= n; ++i) cout << res[i] << ' ';
24
    cout << endl;
25
    return 0;
26
}

C. 珂朵莉与字符串#

线性 DP，维护 $f_{i, j}$ 表示 S 的前 i 位配对了 chtholly 中的前 j 个的方案数，根据当前位的 $S_i$ 考虑状态转移。很可恶的一点是这个题会爆 long long，所以我用 Python 重写了一遍成功过了。

1
s = input()
2
n = len(s)
3
f = [[1, 0, 0, 0, 0, 0, 0, 0, 0]]
4
for i in range(1, n + 1):
5
    c = s[i - 1]
6
    f.append(f[-1].copy())
7
    if c == 'c':
8
        f[i][1] += f[i - 1][0]
9
    elif c == 'h':
10
        f[i][2] += f[i - 1][1]
11
        f[i][4] += f[i - 1][3]
12
    elif c == 't':
13
        f[i][3] += f[i - 1][2]
14
    elif c == 'o':
15
        f[i][5] += f[i - 1][4]
16
    elif c == 'l':
17
        f[i][6] += f[i - 1][5]
18
        f[i][7] += f[i - 1][6]
19
    elif c == 'y':
20
        f[i][8] += f[i - 1][7]
21
print(f[n][8])

D. 珂朵莉与面积#

数学题，直接用公式算就行了，方法应该不唯一。就是两个三角形 + 扇形的面积做差或者求和。我这里三角形面积就用了 $\frac{\text{底} \times \text{高}}{2}$ ，扇形用了 $\frac{1}{2}\alpha r^2$ .

1
#include <iostream>
2
#include <cmath>
3
#include <iomanip>
4
#define PI 3.141592653589793
5

6
using namespace std;
7

8
double work(double a) {
9
    double t = acos(a);
10
    if (t > PI / 2) t = PI - t;
11
    return PI / 2 - t + fabs(sin(t) * cos(t));
12
}
13

14
int sign(double n) {
15
    if (fabs(n) < 1e-7) return 0;
16
    else if (n > 0) return 1;
17
    else return -1;
18
}
19

20
int main() {
21
    ios::sync_with_stdio(0);
22
    cin.tie(0), cout.tie(0);
23
    double l, r;
24
    cin >> l >> r;
25
    cout << fixed << setprecision(3) << fabs(work(l) * sign(l) - work(r) * sign(r)) << endl;
26
    return 0;
27
}

E. 最大数#

直接线段树即可，或者用无旋 Treap 也可以做。

1
#include <iostream>
2

3
using namespace std;
4

5
typedef long long LL;
6
const int N = 200010;
7
LL tr[N * 4], D;
8
int n;
9

10
void pushup(int u) {
11
    tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
12
}
13

14
void modify(int u, int l, int r, int p, LL v) {
15
    if (l == r) tr[u] += v;
16
    else {
17
        int mid = l + r >> 1;
18
        if (p <= mid) modify(u << 1, l, mid, p, v);
19
        else modify(u << 1 | 1, mid + 1, r, p, v);
20
        pushup(u);
21
    }
22
}
23

24
LL query(int u, int l, int r, int ql, int qr) {
25
    if (ql <= l && r <= qr) return tr[u];
26
    else {
27
        int mid = l + r >> 1;
28
        LL res = 0;
29
        if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
30
        if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
31
        return res;
32
    }
33
}
34

35
int main() {
36
    ios::sync_with_stdio(0);
37
    cin.tie(0), cout.tie(0);
38
    cin >> n >> D;
39
    LL t = 0;
40
    int m = 0;
41
    for (int i = 1; i <= n; ++i) {
42
        char op;
43
        LL val;
44
        cin >> op >> val;
45
        if (op == 'A') {
46
            modify(1, 1, n, ++m, (val + t) % D);
47
        }
48
        else {
49
            cout << (t = query(1, 1, n, m - val + 1, m)) << endl;
50
        }
51
    }
52
    return 0;
53
}

F. Cable master#

又是一道经典的模板题。答案满足单调性，二分答案即可。

1
#include <iostream>
2
#include <algorithm>
3
#include <iomanip>
4

5
using namespace std;
6

7
typedef long long LL;
8
const int N = 10010;
9
LL a[N];
10
int n, k;
11

12
LL get() {
13
    static string s;
14
    cin >> s;
15
    int idx = s.find('.');
16
    if (idx == EOF) return stoi(s);
17
    else return stoi(s.substr(0, idx) + s.substr(idx + 1));
18
}
19

20
bool check(int mid) {
21
    LL cnt = 0;
22
    for (int i = 1; i <= n; ++i) cnt += a[i] / mid;
23
    return cnt >= k;
24
}
25

26
int main() {
27
    ios::sync_with_stdio(0);
28
    cin.tie(0), cout.tie(0);
29
    cin >> n >> k;
30
    for (int i = 1; i <= n; ++i) {
31
        a[i] = get();
32
    }
33
    int l = 0, r = 10000000;
34
    while (l < r) {
35
        int mid = l + r + 1 >> 1;
36
        if (check(mid)) l = mid;
37
        else r = mid - 1;
38
    }
39
    cout << l / 100 << '.' << setw(2) << setfill('0') << l % 100 << endl;
40
    return 0;
41
}

G. Splitting the Field【Normal】#

考虑到分出的两块不可能重叠，那么直接分别按一个维度排序，枚举分割点对所有可能的答案取 min 即可，排序后预处理前缀、后缀的 max 和 min 即可 $O(n)$ 枚举答案。

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

4
using namespace std;
5

6
typedef long long LL;
7
const int N = 50010;
8
pair<LL, LL> a[N];
9
LL pre_mx[N], pre_mn[N], suf_mx[N], suf_mn[N];
10
LL res;
11
int n;
12

13
void work() {
14
    sort(a + 1, a + n + 1);
15
    pre_mn[0] = suf_mn[n + 1] = 1000000001;
16
    for (int i = 1; i <= n; ++i) {
17
        pre_mx[i] = max(pre_mx[i - 1], a[i].second);
18
        pre_mn[i] = min(pre_mn[i - 1], a[i].second);
19
    }
20
    for (int i = n; i; --i) {
21
        suf_mx[i] = max(suf_mx[i + 1], a[i].second);
22
        suf_mn[i] = min(suf_mn[i + 1], a[i].second);
23
    }
24
    for (int i = 2; i <= n; ++i) {
25
        if (a[i - 1].first != a[i].first) {
26
            res = min(res, (pre_mx[i - 1] - pre_mn[i - 1]) * (a[i - 1].first - a[1].first) + (suf_mx[i] - suf_mn[i]) * (a[n].first - a[i].first));
27
        }
28
    }
29
}
30

31

32
int main() {
33
    ios::sync_with_stdio(0);
34
    cin.tie(0), cout.tie(0);
35
    cin >> n;
36
    LL mnx = 1000000001, mny = 1000000001, mxx = 0, mxy = 0;
37
    for (int i = 1; i <= n; ++i) {
38
        auto &[x, y] = a[i];
39
        cin >> x >> y;
40
        mnx = min(mnx, x), mny = min(mny, y);
41
        mxx = max(mxx, x), mxy = max(mxy, y);
42
    }
43
    res = (mxx - mnx) * (mxy - mny);
44
    work();
45
    for (int i = 1; i <= n; ++i) {
46
        swap(a[i].first, a[i].second);
47
    }
48
    work();
49
    cout << (mxx - mnx) * (mxy - mny) - res << endl;
50
    return 0;
51
}

H. Dishwashing#

考虑到如果一个前缀已经不合法了，往后加元素一定也不可能合法，所以答案具有单调性。另外检查一段前缀是否合法很好写，所以可以考虑二分答案。

想要检查一个前缀是否合法，只需要模拟一遍他的流程。Bessie 放出的所有栈从栈顶到栈底一定单调递增，从左到右的所有栈中的元素一定单调递增，否则 Elsie 不可能取出一个有序的序列。拿到一个新的盘子时，检查能不能直接被取走，如果不能就二分到第一个比他大的栈放到栈顶即可。每次放完都贪心的让 Elsie 尝试取。最后如果取完了就是可行，否则不可行。

1
#include <iostream>
2
#include <stack>
3
#include <algorithm>
4

5
using namespace std;
6

7
const int N = 100010;
8
int a[N], b[N], n;
9
stack<int> q[N];
10

11
bool check(int m) {
12
    int j = 1, k = 1, len = 0;
13
    for (int i = 1; i <= m; ++i) b[i] = a[i];
14
    sort(b + 1, b + m + 1);
15
    for (int i = 1; i <= m && j <= m; ++i) {
16
        if (a[i] == b[j]) j++;
17
        else {
18
            int l = k, r = len + 1;
19
            while (l < r) {
20
                int mid = l + r >> 1;
21
                if (q[mid].top() > a[i]) r = mid;
22
                else l = mid + 1;
23
            }
24
            if (l == len + 1) q[++len].emplace(a[i]);
25
            else q[l].emplace(a[i]);
26
        }
27
        while (j <= m && k <= len && b[j] == q[k].top()) {
28
            q[k].pop();
29
            j++;
30
            if (q[k].empty()) k++;
31
        }
32
    }
33
    for (int i = 1; i <= m; ++i) while (!q[i].empty()) q[i].pop();
34
    return j == m + 1;
35
}
36

37
int main() {
38
    ios::sync_with_stdio(0);
39
    cin.tie(0), cout.tie(0);
40
    cin >> n;
41
    for (int i = 1; i <= n; ++i) cin >> a[i];
42
    int l = 1, r = n;
43
    while (l < r) {
44
        int mid = l + r + 1 >> 1;
45
        if (check(mid)) l = mid;
46
        else r = mid - 1;
47
    }
48
    cout << l << endl;
49
    return 0;
50
}

Star's Blog