本文主要是介绍Codeforces Round 952 (Div. 4) 题解分享，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A. Creating Words
思路
模拟，交换输出即可
code
inline void solve() {string a, b; cin >> a >> b;swap(a[0], b[0]);cout << a << ' ' << b << endl;return;
}B. Maximum Multiple Sum
思路
暴力枚举
数学不会（）
code
inline void solve() {int n; cin >> n;int ans = -1, res = -1;for (int x = 2; x <= n; x ++ ) {int sum = 0;for (int i = 1; i <= n / x; i ++ ) {sum += i * x;}if (sum > res) {res = sum;ans = x;}}cout << ans << endl;return;
}C. Good Prefixes
思路
模拟，从左到右维护前缀和和最大值即可
code
inline void solve() {int n; cin >> n;vector<ll> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];ll sum = 0, maxv = -1;int ans = 0;for (int i = 1; i <= n; i ++ ) {maxv = max(maxv, a[i]);sum += a[i];if (sum - maxv == maxv) ans += 1;}cout << ans << endl;return;
}D. Manhattan Circle
思路
找#最多的行和列即可
code
inline void solve() {int n, m; cin >> n >> m;vector<int> col(m + 1), row(n + 1);int cur1 = 0, cur2 = 0;for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= m; j ++ ) {char tmp; cin >> tmp;if (tmp == '#') {col[j] += 1;if (col[j] > col[cur2]) cur2 = j;row[i] += 1;if (row[i] > row[cur1]) cur1 = i;}}}cout << cur1 << ' ' << cur2 << endl;return;
}E. Secret Box
思路
题目从这里变的开始有一点意思
记一开始给的为 a，b，c
我们选取的是 x，y，z
构成的答案为 (a - x + 1) * (b - y + 1) * (c - z + 1)
其中x，y，z要小于等于对应的边
div4，还是暴力枚举的难度
我们只要sqrtx枚举x，sqrt枚举y就可以了
code
inline void solve() {ll a, b, c, v; cin >> a >> b >> c >> v;ll ans = 0;for (ll x = 1; x <= v / x; x ++ ) {if (v % x == 0) {ll i = x, s = v / i;for (ll y = 1; y <= s / y; y ++ ) {ll j = y, k = s / j;if (s % y == 0) {if (i <= a && j <= b && k <= c) {ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));}swap(j, k);if (i <= a && j <= b && k <= c) {ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));}}}swap(i, s);for (ll y = 1; y <= s / y; y ++ ) {ll j = y, k = s / j;if (s % y == 0) {if (i <= a && j <= b && k <= c) {ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));}swap(j, k);if (i <= a && j <= b && k <= c) {ans = max(ans, (a - i + 1) * (b - j + 1) * (c - k + 1));}}}}}cout << ans << endl;return;
}F. Final Boss
思路
一开始没想到优先队列的做法（）
不过早用早cd这点都知道，那么轮次越少打的伤害越少，反之亦成立
所以可以二分答案
code
const int N = 2e5 + 9;
ll h, n;
PLL a[N];
bool check(ll x) {ll res = 0;for (int i = 1; i <= n; i ++ ) {res += a[i].first;res += (x - 1) / a[i].second * a[i].first;if (res >= h) return true;}return false;
}
inline void solve() {cin >> h >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i].first;for (int i = 1; i <= n; i ++ ) cin >> a[i].second;ll l = 0, r = (ll)4e10 + 9;while (l + 1 != r) {ll mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid;}cout << r << endl;return;
}G. D-Function
思路
进位是一件极其麻烦的事情，但是自己试过以后，发现进位就不能满足题意，输出0
那么我们只需考虑每位上的选择即可，每位上的选择数为 x // k + 1
一点点的容斥原理+快速幂
code
inline void solve() {mod = MOD;int l, r, k; cin >> l >> r >> k;ll ans = qmi(9 / k + 1, r) - qmi(9 / k + 1, l);ans = (ans + mod) % mod;cout << ans << endl;return;
}H1. Maximize the Largest Component (Easy Version)
思路
我们都会做修改哪一行或者哪一列让总数#最多，而这题只是多了一个连通块而已。
我们首先dfs遍历每个每一个连通块，用矩形将它框起来。
矩形的每一条边即对应了遍历到此连通块的行或者列的上下界。
再利用差分将连通块的数量记录即可。
code
inline void solve() {int n, m; cin >> n >> m;vector<vector<char>> mp(n + 1, vector<char>(m + 1));vector<int> row(n + 1), col(m + 1);for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= m; j ++ ) {cin >> mp[i][j];if (mp[i][j] == '#') {row[i] += 1;col[j] += 1;}}}//for (int i = 1; i <= n; i ++ ) cout << row[i] << endl;//for (int i = 1; i <= m; i ++ ) cout << col[i] << endl;vector<vector<int>> vis(n + 1, vector<int>(m + 1));vector<ll> r(n + 3), c(m + 3);int up = 1e9, down = -1e9, left = 1e9, right = -1e9, cnt = 0;function<void(int, int)> dfs = [&](int x, int y) {if (vis[x][y]) return;vis[x][y] = 1;if (mp[x][y] != '#') return;up = min(up, x), down = max(down, x), left = min(left, y), right = max(right, y);cnt += 1;if (x - 1 >= 1) dfs(x - 1, y);if (x + 1 <= n) dfs(x + 1, y);if (y - 1 >= 1) dfs(x, y - 1);if (y + 1 <= m) dfs(x, y + 1);};for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= m; j ++ ) {if (mp[i][j] == '#' && !vis[i][j]) {dfs(i, j);r[up - 1] += cnt, r[down + 2] -= cnt;c[left - 1] += cnt, c[right + 2] -= cnt;//cerr << "cnt:" << cnt << endl;up = 1e9, down = -1e9, left = 1e9, right = -1e9, cnt = 0;}}}ll ans = 0;for (int i = 1; i <= n; i ++ ) r[i] += r[i - 1];for (int i = 1; i <= m; i ++ ) c[i] += c[i - 1];for (int i = 1; i <= n; i ++ ) {ans = max(ans, (ll)(r[i] + m - row[i]));}for (int i = 1; i <= m; i ++ ) {ans = max(ans, (ll)(c[i] + n - col[i]));}cout << ans << endl;return;
}这篇关于Codeforces Round 952 (Div. 4) 题解分享的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
