Codeforces practice C++ 2024/9/11

D. Mathematical Problem

Codeforces Round 954 (Div. 3)

原题链接：https://codeforces.com/contest/1986/problem/D

题目标签分类：brute force，dp，greedy，implementation，math，two pointers

题目难度：1400

题目大意：

给你一个长度为 n 的字符串，只由 0 到 9 这些字符组成，你需要往这个字符串中插入 n - 2 个运算符，规定插入的运算符只有 * 和 + 两种。

输入：

输出：

题目做法：

AC代码：

#include<bits/stdc++.h>
//#define int long long
//#define int __int128
#define loop(i, n) for(int i = 0; i < n; i++)
#define repeat(i, start, end, step) for(int i = start; i < end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);using namespace std;
using ll = long long;
using bigint = __int128;const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;int n, inips = 0, news[20];
string s, str[20];
int tonum(string t) {int res = 0;for(int i = 0; i < t.length(); i++) {res *= 10;res += t[i] - '0';}return res;
}
int construct(int x = -1, int y = -1) {inips = 0;for(int i = 0; i < n; i++) str[i] = s[i];for(int i = 0; i < n; i++) {if(i == x || i == y) {str[i + 1] = str[i] + s[i + 1];str[i] = "-";}}for(int i = 0; i < n; i++) if(str[i] != "-") news[inips++] = tonum(str[i]);int dp[20][2];dp[0][0] = dp[0][1] = news[0];for(int i = 1; i < inips; i++) {dp[i][0] = min(dp[i - 1][1] + news[i], dp[i - 1][0] + news[i]);dp[i][1] = min({dp[i][0], dp[i - 1][1] * news[i], dp[i - 1][0] * news[i]});}return dp[inips - 1][1];
}
void solve() {cin >> n >> s;int res = 1e9 + 10;if(n == 2) {cout << construct(0) << '\n';return ;}for(int i = 0; i < n - 1; i++) res = min(res, construct(i));cout << res << '\n';
}signed main() {FastIOint TestCase = 1;cin >> TestCase;while(TestCase--) solve();
}

事后ps：Dp比较好像也很好写，就两种状态，预处理也不是很难。

D. Maximize the Root

Educational Codeforces Round 168 (Rated for Div. 2)

原题链接：https://codeforces.com/problemset/problem/1997/D

题目标签分类：binary search，dfs and similar，dp，greedy，trees

题目难度：1500

题目大意：

给一颗树，规定编号为1的节点为根节点，每个节点上初始会有一个值，你每次可以进行操作，这个操作是选定一个非叶子节点的节点，给此节点上的值加一，此节点除了该节点外的子树种的节点上的值均减去1。规定每次操作后树上所有节点的值非负。

输入：

共 t 组输入数据。

每组数据有三行，第一行输入一个变量 n，代表这棵树有 n 个节点，第二行有 n 个变量 ai 分别代表初始的时候每个节点上的值，第三行有 n - 1 个变量代表树上每个节点的父节点，n - 1 是因为从下标从2开始，1号节点默认为根节点。

输出：

进行不限次数的合法调整过后根节点上的最大值。

题目做法：

如果根节点上的值确定了，那么这棵树的所有节点上的最小数值也就决定了。

因为结果显然是呈线性变化的，所以可以对答案进行二分，满足则往更大里搜索答案，反之往更小搜索， $check$ 函数的写法应该是 $dfs$ 一整颗树来检测当前二分的答案是否满足。dfs的时间复杂度是 $n$ ，二分的复杂度是 $log\left ( n \right )$ ，所以总复杂度是 $O\left ( nlogn \right )$ 。

AC代码：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);using namespace std;
using ll = long long;
using bigint = __int128;const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;int a[maxn] ,tval;
vector<int> tr[maxn];
bool check(int now, int val) {bool judge = 1;if(val < 0 || val >= 1e18 + 10) return 0;if(tr[now].size() == 0) return (max((ll)0, val - a[now]) <= 0);for(auto it:tr[now]) {judge &= check(it,val * (now != 1) + max((ll)0, val - a[now]));}return judge;
}void solve() {int n, l = 0, r = 1e18 + 10, ans = 0 ,t;cin >> n;loop(i, n) cin >> a[i + 1], tr[i + 1].clear();rep(i, 2, n, 1) cin >> t, tr[t].pb(i);while(l <= r) {int mid = (l + r) / 2;if(check(1, mid)) {ans = max(ans, mid);l = mid + 1;}else r = mid - 1;}cout << ans << '\n';
}signed main() {FastIO int TestCase = 1;cin >> TestCase;while(TestCase--) solve();
}

事后ps：分析整体情况后还是比较容易想到二分答案的，dfs的时候有细节需要注意可能会爆long long，我二分写得挺烂的，还是按板子来比较稳妥。

A. Distanced Coloring

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

原题链接：https://codeforces.com/problemset/problem/2002/A

题目标签分类：constructive algorithms，implementation，math

题目难度：800

题目大意：

给出 n * m 的网格和一个 k ，满足如下条件的两个点为同一颜色，求填满网格的最小颜色数目。

条件：

题目做法：

在一行上最多就用k个颜色就能填满，如果k小于n的话，k大于n的话就用n个。在同一列上同理。这样最小，还是比较好像的，因为等于k的时候间距最小。

AC代码：

#include<bits/stdc++.h>
//#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);using namespace std;
using ll = long long;
using bigint = __int128;const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;void solve() {int n, m, k;cin >> n >> m >> k;cout << min(n, k) * min(m, k) << '\n';
}signed main() {FastIO int TestCase = 1;cin >> TestCase;while(TestCase--) solve();
}

B. Removals Game

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)

原题链接：https://codeforces.com/problemset/problem/2002/B

题目标签分类：constructive algorithms，games

题目难度：1000

题目大意：

Alice 和 Bob 一开始会分别拿到两个全排列数组，

输入：

输出：

题目做法：

AC代码：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);using namespace std;
using ll = long long;
using bigint = __int128;const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;void solve() {int n;cin >> n;int a[n],b[n];for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < n; i++) cin >> b[i];bool is = 1, is2 = 1;rep(i, 0, n - 1, 1) is &= (a[i] == b[i]), is2 &= (a[n - 1 - i] == b[i]);if(is || is2) {cout << "Bob" << '\n';return ;}cout << "Alice" << '\n';
}signed main() {FastIO int TestCase = 1;cin >> TestCase;while(TestCase--) solve();
}

事后ps：

A. Legs

Codeforces Round 962 (Div. 3)

原题链接：https://codeforces.com/contest/1996/problem/A

题目标签分类：binary search，math，ternary search

题目难度：800

题目大意：

输入：

输出：

题目做法：

AC代码：

#include<bits/stdc++.h>
#define int long long
//#define int __int128
#define pb push_back
#define loop(i, n) for(int i = 0; i < n; i++)
#define rep(i, start, end, step) for(int i = start; i <= end; i += step)
#define FastIO ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);using namespace std;
using ll = long long;
using bigint = __int128;const int maxn = 2e5 + 10;
const int modi = 1e9 + 7;void solve() {int n;cin >> n;cout << n / 4 + (n % 4 != 0) << '\n';
}signed main() {FastIO int TestCase = 1;cin >> TestCase;while(TestCase--) solve();
}