本文主要是介绍AtCoder Beginner Contest 347 A~F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
AtCoder Beginner Contest 347 A~F - 知乎 (zhihu.com)
Tasks - AtCoder Beginner Contest 347
A.Divisible(循环)
代码
#include<bits/stdc++.h>
using namespace std;void solve() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++) {int a;cin >> a;if (a % k == 0) {cout << a / k << ' ';}}cout << endl;
}int main() {solve();return 0;
}
B.Substring(枚举，set)
代码
#include<bits/stdc++.h>
using namespace std;set<string> St;
void solve() {string s;cin >> s;int n = s.size();for (int i = 0; i < n; i++) {string str = "";for (int j = i; j < n; j++) {str += s[j];St.insert(str);}}cout << St.size() << endl;
}int main() {solve();return 0;
}
C.Ideal Holidays(哈希)
分析
坑点:没有告诉你当天是星期几，那么我们可以认为，只要存在一种方案使得计划全部成立即可，开始是星期几我们可以随意决定。
由于星期数是循环的，即以�+�为一个周期进行循环，那么我们可以利用类似哈希表的思想，让所有的天数通过取模落在�+�天内，并记录所有取模后的结果。
然后，只要满足以下两个条件之一，就表示一定存在合法的方案：
条件1：取模后的最大最小值之差小于�
如下图，由于我们可以决定开始时是星期几，那么只要取模后的区间大小小于等于�(即取模后的最大最小值之差小于�)，那么就可以将区间最小值修改为一周的开始，此时所有取模后的结果均会落在前�天内。
条件2：将数组排序，存在数组中相邻两项之差大于�
如下图，虽然最大最小值之差很大，但由于中间空出了一段长度大于等于�的区间，那么通过循环让这段空出的区间来到后半部分，那么所有计划也会落在前�天内。
如果上述两种情况均不满足，那么就表示当前情况无解。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;vector<int> v;void solve() {ll n, a, b;cin >> n >> a >> b;ll minn = 1e18, maxn = -1e18;for (int i = 0; i < n; i++) {ll t;cin >> t;t--;t %= (a + b);v.push_back(t);maxn = max(maxn, t);minn = min(minn, t);}sort(v.begin(), v.end());for (int i = 1; i < n; i++) {if (v[i] - v[i - 1] > b) {cout << "Yes" << endl;return;}}if (maxn - minn >= a) cout << "No" << endl;else cout << "Yes" << endl;
}int main() {solve();return 0;
}
D.Popcount and XOR(思维)
代码
#include<bits/stdc++.h>typedef long long LL;
using namespace std;int x[105], y[105], c[105];void solve() {LL a, b, C;cin >> a >> b >> C;int pos = 0, cnt = 0;while (C) {if (C & 1) cnt++;c[pos++] = C % 2;C /= 2;}for (int i = 0; i <= 62; i++) {if (c[i] == 1) {if (a > b) {x[i] = 1;a--;} else {y[i] = 1;b--;}}}for (int i = 0; i <= 62; i++) {if (x[i] + y[i] == 0 && a > 0 && b > 0) {a--, b--;x[i] = y[i] = 1;}}if (a != 0 || b != 0) {cout << -1 << endl;return;}LL X = 0, Y = 0;for (int i = 62; i >= 0; i--) {X = X * 2 + x[i];Y = Y * 2 + y[i];}cout << X << ' ' << Y << endl;
}int main() {solve();return 0;
}
E.Set Add Query
代码
#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int N = 2e5 + 5e2;set<int> S;LL n, q, sz[N], pre[N], ans[N];
vector<int> in[N], out[N];void solve() {cin >> n >> q;for (int i = 1; i <= q; i++) {int x;cin >> x;if (S.find(x) == S.end()) {S.insert(x);in[x].push_back(i);} else {S.erase(x);out[x].push_back(i);}sz[i] = S.size();pre[i] = pre[i - 1] + sz[i];}for (int i = 1; i <= n; i++) out[i].push_back(q + 1);for (int i = 1; i <= n; i++) {int len = in[i].size();for (int j = 0; j < len; j++) {ans[i] += pre[out[i][j] - 1] - pre[in[i][j] - 1];}cout << ans[i] << ' ';}cout << endl;
}int main() {solve();return 0;
}
F.Non-overlapping Squares（思维）
分析
对于所有的方案，必然可以将三个网格的位置分为以下六种。
代码（来自官方题解）
//from atcoder Offcial
#include <iostream>
#include <vector>
#include <ranges>
#include <numeric>
#include <algorithm>int main() {using namespace std;static constexpr auto chmax{[](auto &&x, const auto &y) {if (x < y) x = y;return x;}};static constexpr auto max{[](const auto &x, const auto &y) {if (x < y) return y;return x;}};unsigned N, M;cin >> N >> M;// sum[i][j] := the sum of the M x M square whose top-left cell is (i, j)auto sum{[N, M] {vector A(N + 1, vector<unsigned long>(N + 1));for (auto &&row: A | views::take(N))for (auto &&a: row | views::take(N))cin >> a;// Let A[i][j] ← ∑_{i≤k,j≤l} A[k][l]for (unsigned row_index{N}; auto &&row : A | views::reverse){inclusive_scan(rbegin(row), rend(row), rbegin(row), plus<>{});if (row_index < N)ranges::transform(row, A[row_index + 1], begin(row), plus<>{});--row_index;}// sum[i][j] = A[i][j] - A[i+M][j] - A[i][j+M] + A[i+M][j+M]vector sum(N - M + 1, vector<unsigned long>(N - M + 1));for (unsigned i{}; i <= N - M; ++i)for (unsigned j{}; j <= N - M; ++j)sum[i][j] = A[i][j] - A[i + M][j] - A[i][j + M] + A[i + M][j + M];return sum;}()};// cumulative max of sum[i][j] from the top-left// m[i][j] = max_{k≤i,l≤j} sum[k][l]const auto max_UL{[](auto cells) {for (unsigned row_index{}; auto &&row : cells){inclusive_scan(begin(row), end(row), begin(row), max);if (row_index)ranges::transform(row, cells[row_index - 1], begin(row), max);++row_index;}return cells;}};// flip the board horizontallyconst auto h_flip{[](auto &&cells) {for (auto &&row: cells)ranges::reverse(row);return cells;}};// flip the board verticallyconst auto v_flip{[](auto &&cells) {ranges::reverse(cells);return cells;}};const auto upper_left{max_UL(sum)}; // cumulative max from the top-lefth_flip(sum); // flip horizontallyconst auto upper_right{h_flip(max_UL(sum))}; // cumulative max from the top-rightv_flip(sum); // flip verticallyconst auto lower_right{h_flip(v_flip(max_UL(sum)))}; // cumulative max from the bottom-righth_flip(sum); // flip verticallyconst auto lower_left{v_flip(max_UL(sum))}; // cumulative max from the bottom-leftv_flip(sum); // return to the original stateunsigned long ans{};// Fix a squarefor (unsigned i{}; i < N - M + 1; ++i)for (unsigned j{}; j < N - M + 1; ++j) {if (M <= i && i + M < N - M + 1) // three squares arranged vertically; fix the center squarechmax(ans, upper_left[i - M].back() + sum[i][j] + lower_right[i + M].front());if (M <= j && j + M < N - M + 1) // three squares arranged horizontally; fix the center squarechmax(ans, upper_left.back()[j - M] + sum[i][j] + lower_right.front()[j + M]);if (M <= i) { // T-shapedif (j + M < N - M + 1) // bottom leftchmax(ans, upper_left[i - M].back() + lower_right[i][j + M] + sum[i][j]);if (M <= j) // bottom rightchmax(ans, upper_left[i - M].back() + lower_left[i][j - M] + sum[i][j]);}if (M <= j) { // ト-shapedif (i + M < N - M + 1) // bottom rightchmax(ans, lower_left.front()[j - M] + lower_right[i + M][j] + sum[i][j]);if (M <= i) // top rightchmax(ans, lower_left.front()[j - M] + upper_right[i - M][j] + sum[i][j]);}if (i + M < N - M + 1) { // 亠 -shapedif (j + M < N - M + 1) // top-leftchmax(ans, lower_right[i + M].front() + upper_right[i][j + M] + sum[i][j]);if (M <= j) // top-rightchmax(ans, lower_right[i + M].front() + upper_left[i][j - M] + sum[i][j]);}if (j + M < N - M + 1) { // ㅓ -shapedif (i + M < N - M + 1) // top-leftchmax(ans, upper_right.back()[j + M] + lower_left[i + M][j] + sum[i][j]);if (M <= i) // bottom-leftchmax(ans, upper_right.back()[j + M] + upper_left[i - M][j] + sum[i][j]);}}cout << ans << endl;return 0;
}这篇关于AtCoder Beginner Contest 347 A~F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
