2025春个人训练赛第二场

A. Intentional Blank Page

签到

python

n = int(input())
res = 0
for _ in range(n):
    a = int(input())
    if a % 2 == 1:
        res += 1
print(res)

B. Full House

签到

python

s = list(input())
s.sort()
if s[0] == s[1] and s[1] == s[2] and s[2] != s[3] and s[3] == s[4] or s[0] == s[1] and s[1] != s[2] and s[2] == s[3] and s[3] == s[4]:
    print('YES')
else:
    print('NO')

C. Duck Stress Balls

不断的取最多的三个，因为数据很小可以直接开优先队列暴力模拟。

cpp

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> q;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int c;
    cin >> c;
    for (int i = 1; i <= c; ++i) {
        int t;
        cin >> t;
        q.emplace(t);
    }
    while (q.size() >= 3) {
        auto a = q.top(); q.pop();
        auto b = q.top(); q.pop();
        auto c = q.top(); q.pop();
        a--, b--, c--;
        if (a) q.emplace(a);
        if (b) q.emplace(b);
        if (c) q.emplace(c);
    }
    if (q.empty()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

D. Twin Numbers

比较类似数位 DP，可以直接统计从 0 到上界和 0 到下界的 twin numbers 数量，然后作差，单独检查下界。拆解后的问题变成了 0 到 n twin numbers 的数量。

如果 n 位数是奇数，那么所有位数和他相等的数里面不存在 twin numbers，所有低一位或者多位的都比他小，答案直接是 $10^{⌊ \frac{n}{2} ⌋}$ 。
如果是偶数，考虑从高位到低位两位一组枚举数位
- 如果两位不想等，那么这一位无论填什么只要合法那么之后一定不会顶到上界，直接补一个 $当前位能填数的个数 \cdot 10^{填完当前之后剩下的位数}$ 就返回答案。
- 如果相等，假定都是 c，那么还有顶上界的可能，单独拎出来不定上界的 $c \cdot 10^{填完后剩下的位数}$ 加进去答案，然后接着枚举。

具体实现的时候我这份代码如果因为不相等直接 return 了会比所有的两两都相等多算一个 00，于是我给后者补了个 1。

cpp

#include <iostream>

using namespace std;

const int MOD = 10007;

int power(int n, int p) {
    int res = 1, base = n;
    while (p) {
        if (p & 1) res = res * base % MOD;
        base = base * base % MOD;
        p >>= 1;
    }
    return res;
}

int work(string s) {
    if (s.length() & 1) return power(10, s.length() / 2);
    else {
        int res = 0;
        for (int i = 0; i < s.length(); i += 2) {
            if (s[i] == s[i + 1]) {
                res = (res + (s[i] - '0') * power(10, s.length() - i - 2 >> 1)) % MOD;
            }
            else {
                int t;
                if (s[i] <= s[i + 1]) t = s[i] - 48 + 1;
                else t = s[i] - 48;
                res = (res + t * power(10, s.length() - i - 2 >> 1)) % MOD;
                return res;
            }
        }
        return (res + 1) % MOD;
    }
}

bool check(string s) {
    if (s.length() & 1) return false;
    else for (int i = 0; i < s.length(); i += 2) {
        if (s[i] != s[i + 1]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string l, r;
    cin >> l >> r;
    cout << ((work(r) - work(l) + check(l)) % MOD + MOD) % MOD << endl;
    return 0;
}

E. Simple House

显然答案是单调的，可以二分一个缩放倍率。然后考虑如何检查，先假定是和坐标轴不平行的一般情况，考虑到左上角那条边和左下角那条边越往右间距越大，目标矩形越靠左越能给宽留更多空间，直接在这个角的两条边上二分左下角和左上角的横坐标，检验也很简单，算出四个角的坐标，检查是否在大矩形内。如果和坐标轴平行直接就不用二分了，左下角重叠，检验一下右上角有没有出去就行。

非常恶心的是这个题的精度，好像浮点数加减会丢精度，导致最后本来和边界重叠的点会被判到距离边界外面一点点，我尝试加了个微小的负的偏移量（经检验 1e-6 正好，太小就会 wa），然后就莫名其妙就过了。

cpp

#include <iostream>
#include <cmath>
#include <iomanip>
#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<LD, LD> PDD;

const LD eps = 1e-18;
PDD a[4], b;

int sign(LD a) {
    if (fabs(a) < eps) return 0;
    else if (a > 0) return 1;
    else return -1;
}

int dcmp(LD a, LD b) {
    if (fabs(a - b) < eps) return 0;
    else if (a > b) return 1;
    else return -1;
}

LD cross(PDD a, PDD b) {
    return a.x * b.y - a.y * b.x;
}

PDD operator -(PDD a, PDD b) {
    return {a.x - b.x, a.y - b.y};
}

PDD operator +(PDD a, PDD b) {
    return {a.x + b.x, a.y + b.y};
}

PDD operator *(PDD a, LD b) {
    return {a.x * b, a.y * b};
}


bool check(LD m) {
    LD l = a[1].x, r = min(a[0].x, a[2].x);
    PDD p;
    if (!dcmp(l, r)) {
        p = a[0];
        if (dcmp(p.y + m * b.y, a[1].y) <= 0 && dcmp(p.x + m * b.x, a[2].x) <= 0) return true;
        else return false;
    }
    else {
        // cout << "checking " << fixed << setprecision(10) << m << ", ";
        while (l + 1e-12 < r) {
            LD mid = (l + r) / 2;
            PDD np = a[1] + (a[0] - a[1]) * ((mid - a[1].x) / (a[0].x - a[1].x)), nq = a[1] + (a[2] - a[1]) * ((mid - a[1].x) / (a[2].x - a[1].x));
            if (dcmp(nq.y - np.y, m * b.y) >= 0) r = mid;
            else l = mid + eps;
        }
        l = (l + r) / 2;
        LD t = (l - a[1].x) / (a[0].x - a[1].x);
        p = a[1] + (a[0] - a[1]) * t;
        PDD np1 = p, np2 = p, np3 = p;
        np1.y += m * b.y;
        np2.x += m * b.x, np3.x += m * b.x;
        np2.y += m * b.y;
        // cout << p.x << ' ' << p.y << endl;
        // cout << np1.x << ' ' << np1.y << endl;
        // cout << np2.x << ' ' << np2.y << endl;
        // cout << np3.x << ' ' << np3.y << endl;
        // // cout << cross(a[2] - a[1], np1 - a[1]) << endl;
        // // cout << (a[2] - a[1]).first << ' ' << (a[2] - a[1]).second << ' ' << (np1 - a[1]).first << ' ' << (np1 - a[1]).second ;
        // cout << fixed << setprecision(12) << cross(a[2] - a[1], np1 - a[1]) << ' ';
        // cout << fixed << setprecision(12) << cross(a[3] - a[2], np2 - a[2]) << ' ';
        // cout << fixed << setprecision(12) << cross(a[0] - a[3], np3 - a[3]) << ' ';
        // cout << endl;
        if (sign(cross(a[2] - a[1], np1 - a[1]) - 1e-6) <= 0 && sign(cross(a[3] - a[2], np2 - a[2]) - 1e-6) <= 0 && sign(cross(a[0] - a[3], np3 - a[3]) - 1e-6) <= 0) {
            // cout << "ok" << endl;
            return true;
        }
        else {
            // cout << "no" << endl;
            return false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    for (int i = 0; i < 4; ++i) cin >> a[i].x >> a[i].y;
    cin >> b.x >> b.y;
    LD l = 0, r = 2e4;
    while (l + (LD)(1e-12) < r) {
        LD mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    l = (l + r) / 2;
    cout << fixed << setprecision(10) << b.x * b.y * l * l << endl;
    return 0;
}

F. Pathfinder and Wolves

这就是纯图论板子了，从所有 wolf 出发，跑一个多起点的 bfs，找到每个点的最小距离。然后跑最大生成树，找到所有起点到终点路径上最小值的最大值。

cpp

#include <iostream>
#include <queue>
#include <cstring>
#include <tuple>

using namespace std;

const int N = 1010;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
char mp[N][N];
int dis[N][N], d[N][N];
bool vis[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    queue<pair<int, int>> q;            
    for (int i = 1; i <= n; ++i) cin >> (mp[i] + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mp[i][j] == 'W') {
                q.emplace(i, j);
                vis[i][j] = true;
            }
        }
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (1 <= tx && tx <= n && 1 <= ty && ty <= m && !vis[tx][ty]) {
                dis[tx][ty] = dis[x][y] + 1;
                vis[tx][ty] = true;
                q.emplace(tx, ty);
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    d[1][1] = dis[1][1];
    priority_queue<tuple<int, int, int>> pq;
    pq.emplace(d[1][1], 1, 1);
    while (!pq.empty()) {
        auto [_, x, y] = pq.top();
        pq.pop();
        if (vis[x][y]) continue;
        vis[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (1 <= tx && tx <= n && 1 <= ty && ty <= m && d[tx][ty] < min(dis[tx][ty], d[x][y])) {
                d[tx][ty] = min(d[x][y], dis[tx][ty]);
                pq.emplace(d[tx][ty], tx, ty);
            }
        }
    }
    cout << d[n][m] << endl;
    return 0;
}

2025春个人训练赛第二场 ​

A. Intentional Blank Page ​

B. Full House ​

C. Duck Stress Balls ​

D. Twin Numbers ​

E. Simple House ​

F. Pathfinder and Wolves ​