Codeforces Round 863 (Div. 3)

A. Insert Digit

题意：插入一个字母使得这个数字最大化

思路：只要从前往后便利就行

#include <iostream>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    bool x = true,y=false;
    for (int i = 0; i < n; i++) {
        char b;
        cin >> b;
        int a = b - '0';
        if (a < k && x) {
            cout << k;
            x = false;
        }
        cout << a;
    }
    if (x) {
        cout << k;
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. Conveyor Belts

题意：从（x1，y1）到（x2，y2）所需能量，每变换一次轨道需要能量

思路：确定是哪个轨道就行

#include <iostream>
#include <cmath>

using namespace std;

void solve() {
    int n = 0, x1 = 0, x2 = 0, y1 = 0, y2 = 0;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    int a1 = min(x1, min(n - x1 + 1, min(y1, n - y1 + 1)));
    int a2 = min(x2, min(n - x2 + 1, min(y2, n - y2 + 1)));
    cout << abs(a1 - a2) << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Restore the Array

*前面卡了一会因为以为a的长度是不确定的，但是他是确定的读题很重要！！！！！！！

题意：给你一个b数组他是由a数组两个相邻元素的最大值而决定且b的长度为n-1，a的长度为n

思路：

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 10;
int a[MAX];

void solve() {
    int n;
    cin >> n;
    bool x = true;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
    }
    a[0] = a[1];
    a[n] = a[n - 1];
    for (int i = 0; i < n; i++) {
        cout << min(a[i], a[i + 1]) << " ";
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

D. Umka and a Long Flight

题意：给一个长方形他的边长是斐波那契数列(典中典就不描述了)，然后给定一个坐标(x,y)，问能否最后剩下这个坐标上的方形为1*1，分割的矩形中有个要求：有一个矩阵为正方形而且其边长是等于斐波那契的

思路：

ps：以上为题目给的图(讲真看了这图我觉得这个题目难度至少下降两个level)

按照斐波那契来分割矩形(边割边转(坐标问题画图理解就是了))

#include <bits/stdc++.h>

using namespace std;
#define int long long
int dp[55];

void fab() {
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= 45; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}

bool cut(int n, int x, int y) {
    if (n == 1) return true;
    int mid = dp[n + 1] / 2;
    if (y <= mid) y = dp[n + 1] - y + 1;
    if (y <= dp[n]) return false;
    return cut(n - 1, y - dp[n], x);
}

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    if (cut(n, x, y)) cout << "Yes\n";
    else cout << "NO\n";
}

signed main() {
    int t;
    cin >> t;
    fab();
    while (t--) {
        solve();
    }
    return 0;
}

E. Living Sequence

题意：简单来说就是一旦数字里面有一个位数含有4就跳过

第一眼dp，第二眼1e12怎么dp，不会！gg

思路：没有4，就相当于将10进制变成了9进制，然后每个数组映射(太妙了kao)

#include <bits/stdc++.h>

using namespace std;
#define int long long
int a[22];
int x[10] = {0, 1, 2, 3, 5, 6, 7, 8, 9};

void solve() {
    int n;
    cin >> n;
    int cnt = 0;
    while (n) {
        a[++cnt] = x[n % 9];
        n /= 9;
    }
    for (int i = cnt; i > 0; i--) {
        cout << a[i];
    }
    cout << "\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

后面的题慢慢补，每道题只有三位数太夸张