2024牛客暑期多校训练营9 (opens new window)

A - Image Scaling

Question

给你一个由 $\tt{.}$和 $\tt{x}$组成的 $n\times m$矩阵。所有的 $\tt{x}$构成一个子矩阵，您要提取它并尽可能缩小，同时保持边长整数和长宽比不变。输出最终矩阵。保证矩阵中至少有一个 $\tt{x}$。

• $1\le n, m\le 500$

Solution

签到题

找到 x 矩形的长宽，然后取 gcd

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<vector<char>> a(n + 1, vector<char>(m + 1));
    int nn = 0, mm = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'x') cnt += 1;
        }
        if (cnt) nn += 1, mm = max(mm, cnt);
    }
    int g = __gcd(nn, mm);
    nn /= g, mm /= g;
    for (int i = 1; i <= nn; i++) {
        for (int j = 1; j <= mm; j++) {
            cout << 'x';
        }
        cout << '\n';
    }
    return 0;
}

K - Kill The Monsters

Question

森林里有$n$只怪物。第$i$只的防御值为$a_i$。

您可以进行以下攻击：

• 降低所有怪物的防御值$1$。

• 选择一个怪物，让它的防御值$a_i$为$\lfloor\frac{a_i}{k}\rfloor$，其中$k$是给定的。

求使每个怪物的防御值小于或等于$0$所需的最少操作次数。

• $1\le n \le 10^5$，$1\le a_i,k\le 10^9$

Solution

显然，我们先使用第二种攻击方式，然后使用第一种攻击方式

我们需要用第二种攻击方式把所有的怪物血量控制在一个数 $x$ 之下或者等于 $x$，然后使用 $x$ 次第一种攻击方式

假设 $x$ 从大到小枚举，那么用一个优先队列维护当前所有怪物的防御值，对于 $a_i>x$ 的使用第二种攻击方式

那么如何确定 $x$ 的集合，其实就是所有怪物可能的血量，最大可能的集合大小为 $n\log M$ ，$M$ 为 $a_i$ 的最大值

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int INF = 0x3f3f3f3f;
signed main() {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    if (k == 1) {
        cout << *max_element(a.begin() + 1, a.end()) << endl;
        return 0;
    }

    vector<int> p;
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        while (x) { p.push_back(x); x /= k; }
    }
    p.push_back(0);
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    reverse(p.begin(), p.end());
    int ans = INF, cnt = 0;
    int pos = 1;
    priority_queue<int> pq;
    for (int i = 1; i <= n; i++) pq.push(a[i]);
    for (auto x : p) {
        while (!pq.empty() && pq.top() > x) {
            cnt += 1;
            int tmp = pq.top(); pq.pop();
            pq.push(tmp / k);
        }
        ans = min(ans, x + cnt);
    }

    cout << ans << endl;
    return 0;
}

I - Interesting Numbers

Question

小 G 正在寻找一种具有以下特征的特殊类型的数字：它们有 $n$位数字。将数字对半分割，可以得到两个完全平方数，可能还有前导零。可以保证 $n \equiv 0 \bmod 2$

现在小 G 想知道在 $[L, R]$范围内有多少个这样的数。

两半的长度必须相同。

Solution

显然，这个问题可以转化为求 $[1,N]$ 有多少个数满足要求

设 $len$ 为 $N$ 的长度

• 如果 $N$ 的高 $len/2$ 不是一个平方数，高 $len/2$ 位的方案数为 $\lceil\sqrt{\frac{N}{10^{len/2}}}\rceil$ ，低 $len/2$ 位的方案数为 $\lceil\sqrt{10^{len/2}}\rceil$
• 否则，答案需要加上 $\sqrt{N\bmod 10^{len/2}}+1$

由于 $len$ 可能达到 $60$，所以难点在高精度，当然，也可以用 python 实现

Code

from math import ceil, floor, sqrt

def check (x):
    xq = int(sqrt(x))
    return xq * xq == x

def calc(N, lenth):
    ret = 0
    high = N // (10 ** (lenth // 2))
    low = N % (10 ** (lenth // 2))
    ret = ceil(sqrt(high)) * ceil(sqrt(10 ** (lenth // 2)))

    if check(high):
        ret += floor(sqrt(low)) + 1
    
    return ret


n = int(input())
l, r = map(int, input().split())

lenth = len(str(r))
ans = calc(r, lenth) - calc(l - 1, lenth)
print(ans)