A. Shashliks
算两次，一次优先做 a，一次优先做 b，取 max 为答案
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int k, a, b, x, y;
cin >> k >> a >> b >> x >> y;
int ans = -1;
ans = std::max<int>(std::max<int>((k - a + x) / x, 0) + std::max<int>((k - std::max<int>((k - a + x) / x, 0) * x - b + y) / y, 0),
std::max<int>((k - b + y) / y, 0) + std::max<int>((k - std::max<int>((k - b + y) / y, 0) * y - a + x) / x, 0));
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
B. Good Start
当初始放置的两块板子能对齐时，要看中间的宽度能否整除另一条平行的边。
若没对齐，两块板子中间的差距必须是边的倍数才行，直接对两边差值整除判断即可。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int w, h, a, b, x1, x2, y1, y2;
cin >> w >> h >> a >> b >> x1 >> y1 >> x2 >> y2;
bool flag = 0;
if (x1 == x2) {
if (abs(y1 - y2) % b == 0) flag = 1;
}
else if (y1 == y2) {
if (abs(x1 - x2) % a == 0) flag = 1;
}
else if ((x1 - x2) % a == 0 || (y1 - y2) % b == 0) {
flag = 1;
}
if (flag) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
C. Smilo and Minecraft
纯思维，观察 note 中的 t3 的解释，可以发现炸一次之后，其余所有位置的金都能取到，所以转换为在哪个位置炸一次对答案影响最小，通过二维前缀和解决。
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
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> g(n + 1, vector<char>(m + 1));
vector<vector<int>> s(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
if (g[i][j] == 'g') {
s[i][j] += 1;
}
}
}
int ans = -1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '.') {
int l = max(i - k, 0);
int r = min(i + k - 1, n);
int u = max(j - k, 0);
int d = min(j + k - 1, m);
int tmp = s[n][m] - (s[r][d] + s[l][u] - s[r][u] - s[l][d]);
ans = max(ans, tmp);
}
}
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|
D. Cheater
纯思维。
输的牌不消失，即可以反复赢对方一张小牌，所以当前缀中最小的那张牌能赢一次后，对应前缀全部能赢，所以将后缀中最大的值交换到当前位置前缀中的最小值是一定更优的，会使前缀种的最小值变大。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e5 + 7, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), k(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> k[i];
}
vector<int> premn(n + 1), sufmx(n + 1);
premn[0] = 0, sufmx[n - 1] = n - 1;
for (int i = 1; i < n; i++) {
if (a[i] < a[premn[i - 1]]) {
premn[i] = i;
} else {
premn[i] = premn[i - 1];
}
}
for (int i = n - 2; i >= 0; i--) {
if (a[i] > a[sufmx[i + 1]]) {
sufmx[i] = i;
} else {
sufmx[i] = sufmx[i + 1];
}
}
auto count = [&]() {
int res = 0;
int i = 0, j = 0, cnt = 0;
while (cnt < n && i <= n && j <= n) {
if (a[i] > k[j]) {
res++;
i++;
} else {
j++;
}
cnt++;
}
return res;
};
int ans = count();
int l = ans + 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
swap(a[premn[mid - 1]], a[sufmx[mid]]);
// cout << "mid:" << mid << " ans:" << count() << endl;
if (count() >= mid) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
swap(a[premn[mid - 1]], a[sufmx[mid]]);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
|