Codeforces practice /C++ 2024/9/11 - 2024/9/12

D. Mathematical Problem

Codeforces Round 954 (Div. 3)

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

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

题目难度：1400

题目大意：

输入：

输出：

题目做法：

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() {
    FastIO
    int 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号节点默认为根节点。

输出：

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

题目做法：

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

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

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

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

题目难度：1500

题目大意：

​

给出 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();
}