ABC393题解
AtCoder Beginner Contest 393
A
算法标签: 模拟
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
if (s1 == "sick" && s2 == "fine") cout << 2 << "\n";
else if (s1 == "fine" && s2 == "sick") cout << 3 << "\n";
else if (s1 == "fine" && s2 == "fine") cout << 4 << "\n";
else cout << 1 << "\n";
return 0;
}
B
算法标签: 模拟
思路
每次找到 B B B的位置, 以 B B B为中心向两侧扩展, 然后删除该位置
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
cin >> s;
int res = 0;
while (s.find('B') != -1) {
int u = s.find('B');
int n = s.size();
for (int i = 1; i <= n; ++i) {
if (u - i < 0 || u + i >= n) continue;
if (s[u - i] == 'A' && s[u + i] == 'C') res++;
}
s[u] = ' ';
}
cout << res << "\n";
return 0;
}
C
算法标签: 哈希映射, 哈希表
思路
注意计算哈希值的时候转化成 l o n g l o n g long \, long longlong
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <utility>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 5e5 + 10;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
unordered_set<LL> s;
int res = 0;
while (m--) {
int u, v;
cin >> u >> v;
if (u == v) {
res++;
continue;
}
LL hash1 = (LL)u * N + v;
LL hash2 = (LL)v * N + u;
if (!s.count(hash1) && !s.count(hash2)) {
s.insert(hash1);
s.insert(hash2);
}
else res++;
}
cout << res << "\n";
return 0;
}
D
算法标签: 贪心, 模拟
思路
因为最后一定是一段 1 1 1连接到一起, 因此设 1 1 1的数量是 c n t cnt cnt, 最后 1 1 1的起始位置 l l l, 那么终点坐标就是 l + c n t − 1 l + cnt - 1 l+cnt−1, 设初始时每个 1 1 1的位置是 a i a_i ai, 那么目标就是最小化
a n s = min { ∑ i = 1 n ∣ a i − ( l + i − 1 ) ∣ } ans =\min\left \{ \sum _{i = 1} ^ {n} |a_i - (l + i - 1)| \right \} ans=min{i=1∑n∣ai−(l+i−1)∣}
整理后得到
a n s = min { ∑ i = 1 n ∣ a i − i − ( l − 1 ) ∣ } ans =\min\left \{ \sum _{i = 1} ^ {n} |a_i - i - (l - 1)| \right \} ans=min{i=1∑n∣ai−i−(l−1)∣}
设 b i = a i − i b_i = a_i - i bi=ai−i, x = l − 1 x = l - 1 x=l−1, 那么原式变为
a n s = min { ∑ i = 1 n ∣ b i − x ∣ } ans =\min\left \{ \sum _{i = 1} ^ {n} |b_i - x| \right \} ans=min{i=1∑n∣bi−x∣}
x x x取中位数就是最小值
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n;
string s;
vector<int> nums;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> s;
int k = 1;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
nums.push_back(i - k);
k++;
}
}
sort(nums.begin(), nums.end());
int x = nums[nums.size() / 2];
LL res = 0;
for (int val : nums) res += abs(val - x);
cout << res << "\n";
return 0;
}
E
算法标签: 倍数, 数论, g c d gcd gcd, 调和级数
思路
首先看 A i A_i Ai的最大值范围不超过 1 0 6 10 ^ 6 106, 也就是答案 g c d ≤ 1 0 6 gcd \le 10 ^ 6 gcd≤106, 因此可以枚举 g c d gcd gcd, 题目要求 k k k个元素中必须包含 A i A_i Ai, 设 d = g c d d = gcd d=gcd, 必须满足 d ∣ A i d | A_i d∣Ai, 并且在剩余元素中至少有 k − 1 k - 1 k−1个 d d d的倍数
设 c n t [ x ] cnt[x] cnt[x]表示 A A A中 x x x出现的次数, m u l [ x ] mul[x] mul[x]表示 A A A中 x x x倍数出现的次数, 那么有 m u l [ x ] = c n t [ x ] + c n t [ 2 x ] + c n t [ 3 x ] + . . . + c n t [ n x ] mul[x] = cnt[x] + cnt[2x] + cnt[3x] + ... + cnt[nx] mul[x]=cnt[x]+cnt[2x]+cnt[3x]+...+cnt[nx], 调和级数枚举每个 x x x的倍数, 时间复杂度 O ( n ln n ) O(n \ln n) O(nlnn), 可以放缩为 O ( n log n ) O(n \log n) O(nlogn)
算法过程
- 首先枚举 d d d
- 然后检查 m u l [ d ] ≥ k mul[d] \ge k mul[d]≥k, 如果满足条件, 更新 d d d的倍数的 A i A_i Ai的答案
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1.2E6 + 10, M = 1e6 + 10;
int n, k;
int w[N], cnt[N], mul[N];
int res[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
cnt[w[i]]++;
}
// 调和级数枚举所有数倍数出现的次数
for (int i = 1; i < M; ++i) {
for (int j = i; j < M; j += i) {
mul[i] += cnt[j];
}
}
for (int d = 1; d < M; ++d) {
if (mul[d] < k) continue;
for (int x = d; x < N; x += d) {
res[x] = max(res[x], d);
}
}
for (int i = 1; i <= n; ++i) cout << res[w[i]] << "\n";
return 0;
}
F
算法标签: 离线, 树状数组, 离散化, 动态规划, L I S LIS LIS
思路
注意到, 查询数量和序列长度都是
2
×
1
0
5
2 \times 10 ^ 5
2×105,
O
(
n
2
)
O(n ^ 2)
O(n2)的直接做法会超时
L
I
S
LIS
LIS问题有一个树状数组优化做法, 设
f
[
j
]
f[j]
f[j]表示以
j
j
j结尾的最长上升子序列的长度, 更新方式
f
[
a
[
j
]
]
=
max
k
<
a
[
i
]
{
f
[
k
]
}
+
1
f[a[j]] = \max _{k < a[i]} \left \{ f[k] \right \} + 1
f[a[j]]=maxk<a[i]{f[k]}+1, 取
m
a
x
max
max的过程可以使用树状数组优化
树状数组求最长上升子序列问题
树状数组求 L I S LIS LIS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
int n, w[N];
vector<int> nums;
int tr[N];
int get(int val) {
return lower_bound(nums.begin(), nums.end(), val) - nums.begin() + 1;
}
void disc() {
for (int i = 1; i <= n; ++i) nums.push_back(w[i]);
sort(nums.begin(), nums.end());
for (int i = 1; i <= n; ++i) w[i] = get(w[i]);
}
int lowbit(int val) {
return val & -val;
}
void update(int u, int val) {
for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}
int get_max(int u) {
int res = 0;
for (int i = u; i; i -= lowbit(i)) res = max(res, tr[i]);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> w[i];
disc();
int res = 1;
for (int i = 1; i <= n; ++i) {
int curr = get_max(w[i] - 1) + 1;
res = max(res, curr);
update(w[i], curr);
}
cout << res << "\n";
return 0;
}
因为当前问题是离线问题, 因此可以将查询顺序打乱, 考虑将查询按照 R R R从小到大排序依次处理, 每次处理完 a [ i ] a[i] a[i]后计算 R = i R = i R=i的所有询问, 时间复杂度 O ( ( N + Q ) l o g M ) O((N + Q) log M) O((N+Q)logM), M M M是树状数组大小
树状数组做法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, q;
int w[N];
struct Query {
int x, id;
};
vector<Query> qs[N];
int tr[N << 1], ans[N];
// 离散化
void disc() {
vector<int> nums;
for (int i = 1; i <= n; ++i) nums.push_back(w[i]);
for (int i = 1; i <= n; ++i) {
for (auto [x, id] : qs[i]) {
nums.push_back(x);
}
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (int i = 1; i <= n; ++i) {
w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin() + 1;
}
for (int i = 1; i <= n; ++i) {
for (Query &q : qs[i]) {
q.x = lower_bound(nums.begin(), nums.end(), q.x) - nums.begin() + 1;
}
}
}
int lowbit(int val) {
return val & -val;
}
void update(int u, int val) {
for (int i = u; i < N * 2; i += lowbit(i)) {
tr[i] = max(tr[i], val);
}
}
int get_max(int u) {
int res = 0;
for (int i = u; i > 0; i -= lowbit(i)) {
res = max(res, tr[i]);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> w[i];
for (int i = 1; i <= q; ++i) {
int r, x;
cin >> r >> x;
// 记录最大值范围和查询id
qs[r].push_back({x, i});
}
disc();
for (int i = 1; i <= n; ++i) {
int curr = get_max(w[i] - 1) + 1;
update(w[i], curr);
for (Query q : qs[i]) {
ans[q.id] = get_max(q.x);
}
}
for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
return 0;
}
动态规划 + 二分做法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, q, w[N];
struct Query {
int r, x, id;
int ans;
} qs[N];
bool cmp_r(Query &q1, Query &q2) {
return q1.r < q2.r;
}
bool cmp_id(Query &q1, Query &q2) {
return q1.id < q2.id;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> w[i];
for (int i = 1; i <= q; ++i) {
int r, x;
cin >> r >> x;
qs[i] = {r, x, i};
}
sort(qs + 1, qs + q + 1, cmp_r);
vector<int> f;
f.push_back(0);
int qi = 1;
for (int i = 1; i <= n; ++i) {
// 第一个大于等于w[i]的位置
auto it = lower_bound(f.begin(), f.end(), w[i]);
if (it == f.end()) f.push_back(w[i]);
else *it = w[i];
while (qi <= q && qs[qi].r == i) {
qs[qi].ans = upper_bound(f.begin(), f.end(), qs[qi].x) - f.begin() - 1;
qi++;
}
}
sort(qs + 1, qs + q + 1, cmp_id);
for (int i = 1; i <= q; ++i) cout << qs[i].ans << "\n";
return 0;
}
G
先鸽, 因为是黑题, 有时间补上
集算法之大成！助力oier实现梦想！
更多推荐
26
0- 0
已为社区贡献6条内容
所有评论(0)