2024牛客暑期多校9
2024牛客暑期多校训练营9 (opens new window)
# A - Image Scaling
# Question
给你一个由 和 组成的 矩阵。所有的 构成一个子矩阵,您要提取它并尽可能缩小,同时保持边长整数和长宽比不变。输出最终矩阵。保证矩阵中至少有一个 。
# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# K - Kill The Monsters
# Question
森林里有只怪物。第只的防御值为。
您可以进行以下攻击:
降低所有怪物的防御值。
选择一个怪物,让它的防御值为,其中是给定的。
求使每个怪物的防御值小于或等于所需的最少操作次数。
- ,
# Solution
显然,我们先使用第二种攻击方式,然后使用第一种攻击方式
我们需要用第二种攻击方式把所有的怪物血量控制在一个数 之下或者等于 ,然后使用 次第一种攻击方式
假设 从大到小枚举,那么用一个优先队列维护当前所有怪物的防御值,对于 的使用第二种攻击方式
那么如何确定 的集合,其实就是所有怪物可能的血量,最大可能的集合大小为 , 为 的最大值
# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# I - Interesting Numbers
# Question
小 G 正在寻找一种具有以下特征的特殊类型的数字:它们有 位数字。将数字对半分割,可以得到两个完全平方数,可能还有前导零。可以保证
现在小 G 想知道在 范围内有多少个这样的数。
两半的长度必须相同。
# Solution
显然,这个问题可以转化为求 有多少个数满足要求
设 为 的长度
- 如果 的高 不是一个平方数,高 位的方案数为 ,低 位的方案数为
- 否则,答案需要加上
由于 可能达到 ,所以难点在高精度,当然,也可以用 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
上次更新: 2024/09/14, 12:53:16