D
题目大意：首届 IT Campus “NEIMARK” 奥林匹克的决赛场地被布置为一个矩形区域。你可以认为该场地被划分为 $n$ 行，每行包含 $m$ 个参赛者座位的点位。共有 $k$ 名参赛者注册了决赛，每位参赛者将坐在单独的座位上。现在，组委会需要为这些座位选择具体位置。每个座位占据某一行中的 $m$ 个点位之一。此外，若同一行中多个连续的座位被占据，我们称这样的座位组为一个长凳，组内座位的数量称为长凳的长度。组委会希望选择座位位置使得最长长凳的长度尽可能小。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n, m, k \leq 10^9$，$k \leq n \cdot m$。
思路：
1
2
3
4
5
6
7
8
| void solve() {
ll n, m, k;
cin >> n >> m >> k;
ll tem = k / n + (k % n != 0);
ll tem2 = m - tem + 1;
cout << (tem / tem2 + (tem % tem2 != 0)) << endl;
return;
}
|
E
题目大意：最近，Misha 在 IT Campus “NEIMARK” 的夏令营中学习了新课题 —— 欧几里得算法。当发现 $a \cdot b = \text{lcm}(a, b) \cdot \text{gcd}(a, b)$ 时，他有些惊讶。其中 $\text{gcd}(a, b)$ 是 $a$ 和 $b$ 的最大公约数 (GCD)，而 $\text{lcm}(a, b)$ 是最小公倍数 (LCM)。
数据范围：$1 \leq t \leq 10^3$，$2 \leq n \leq 10^7$，$\sum n \le 10^7$。
思路：
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
| constexpr int M = 1e7 + 2;
bool is_prime[M];
vector<int> primes;
auto init = [] {
ranges::fill(is_prime, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i < M; i++) {
if (is_prime[i]) {
primes.push_back(i);
for (ll j = 1LL * i * i; j < M; j += i) {
is_prime[j] = false;
}
}
}
return 0;
}();
// 函数指针在创建时自动调用
void solve() {
ll n;
cin >> n;
ll ans = 0;
rep(i, 1, n) {
int tem = ranges::upper_bound(primes, n / i) - primes.begin();
ans += max(0, tem);
}
cout << ans << endl;
return;
}
|
F
题目大意：IT Campus “NEIMARK” 的访客不仅是优秀的程序员，更是体魄强健的运动爱好者！有人练习游泳，有人划船，还有人进行攀岩！Igor 大师是当地攀岩界的知名人物。某天，他前往山区攀登一座山峰。作为经验丰富的攀岩者，Igor 决定不沿既有路线，而是利用自己的技巧严格垂直攀登。Igor 找到了一块垂直的矩形山体区域，并将其在脑海中划分为 $n$ 个水平层。随后他将每层用垂直隔板分割为 $m$ 个区段。观察这些区段时，Igor 发现了可供抓握的凸起（以下称为支点）。因此，所选山体区域可表示为 $n \times m$ 的矩形，其中某些单元格包含支点。作为资深程序员，Igor 决定计算有效路线的数量。
数据范围：$1 \leq t \leq 10^3$，$2 \leq n \leq 2000$，$1 \leq m, d \leq 2000$，$\sum n \cdot m \le 4 \cdot 10^6$。
思路：
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
41
42
43
44
45
46
47
48
| const int MOD = 998244353;
void solve() {
int n, m, d;
cin >> n >> m >> d;
vector<string> ma(n);
rep(i, 0, n - 1) cin >> ma[i];
vector<vvi> dp(n, vvi(m, vi(2, 0)));
rep(i, 0, m - 1) {
if (ma[n - 1][i] == 'X') dp[n - 1][i][0] = 1;
}
frep(i, n - 1, 0) {
if (i != n - 1) {
vi pre(m + 1, 0);
rep(j, 1, m) {
pre[j] = pre[j - 1] + 1LL * dp[i + 1][j - 1][0];
pre[j] %= MOD;
pre[j] += 1LL * dp[i + 1][j - 1][1];
pre[j] %= MOD;
}
int bias = sqrt(d * d - 1);
rep(j, 1, m) {
if (ma[i][j - 1] == 'X') dp[i][j - 1][0] = (pre[min(m, j + bias)] - pre[max(0, j - bias - 1)] + MOD) % MOD;
}
}
vi pre(m + 1, 0);
rep(j, 1, m) {
pre[j] = pre[j - 1] + 1LL * dp[i][j - 1][0];
pre[j] %= MOD;
}
int bias = d;
rep(j, 1, m) {
if (ma[i][j - 1] == 'X') {
dp[i][j - 1][1] += (pre[min(m, j + bias)] - pre[j] + MOD) % MOD;
dp[i][j - 1][1] += (pre[j - 1] - pre[max(0, j - bias - 1)] + MOD) % MOD;
dp[i][j - 1][1] %= MOD;
}
}
}
int ans = 0;
rep(i, 0, m - 1) {
ans += dp[0][i][0];
ans %= MOD;
ans += dp[0][i][1];
ans %= MOD;
}
cout << ans << endl;
return;
}
|
G
题目大意：程序员 Gleb 经常访问 IT Campus “NEIMARK” 参加编程训练。Gleb 不仅是程序员，还是一位著名的划船运动员，因此他选择通过划皮划艇沿河流完成部分通勤路程。假设 Gleb 从点 $0$ 出发，必须到达点 $s$（即沿直线划行 $s$ 米）。为增加挑战性，Gleb 决定不离开线段 $[0, s]$。皮划艇的尺寸可忽略不计。Gleb 是实力强劲的程序员！初始时他的力量为 $k$。Gleb 的力量直接影响皮划艇的运动：若当前力量为 $x$，则每次划桨可使皮划艇沿当前方向移动 $x$ 米。Gleb 可以调头并继续向相反方向移动，但此操作十分困难，每次调头后力量会减少 $1$。
数据范围：$1 \leq t \leq 100$，$1 \leq s \leq 10^9$，$1 \leq k \leq 1000$，$k \leq s$，$\sum k \le 2000$。
思路：
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
41
42
43
44
| void solve() {
ll s, k;
cin >> s >> k;
if (s % k == 0) {
cout << k << endl;
return;
}
if (s > k * k) {
cout << max(1LL, k - 2) << endl;
return;
}
vb vis1(s + 5, false), vis2(s + 5, false);
vis1[k] = 1;
int tem = 1;
while (true) {
queue<int> q;
rep(i, 0, s - 1) {
if (vis1[i]) q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();
int tem2 = x + tem * k;
if (tem2 >= 0 && tem2 <= s && !vis1[tem2]) {
vis1[tem2] = true;
q.push(tem2);
}
}
if (vis1[s]) {
cout << k << endl;
return;
}
k = max(k - 1, 1LL);
tem = -tem;
ranges::fill(vis2, false);
rep(i, 0, s - 1) {
if (vis1[i] && i + tem * k >= 0 && i + tem * k <= s) {
vis2[i + tem * k] = true;
}
}
swap(vis1, vis2);
}
return;
}
|
