题目链接

总体来说还是很考思维的，cf的题目质量非常不错。

A Insert Digit

也不知道为啥，比赛搞半天，其实就是找到比给的数小的位置的时候将它放在这个位置的前面，如果没有找到就放在最后面即可。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

void solve() {
    string s;
    int n;
    char op;
    cin >> n >> op >> s;
    int ret = 0;
    for (int i = 0; i < s.size(); i++) {
        if (op > s[i] && ret == 0) {
            cout << op;
            ret = 1;
        }
        cout << s[i];
    }
    if (ret == 0)cout << op;
    cout << endl;
}


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

B Conveyor Belts

这道题其实贪心的去做就可以了，先通过坐标找出它在第几层，然后将两个的层数相减即可，赛时写的都写复杂了

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 100010;

void solve() {
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    int rank1 = 0, rank2 = 0;
    int x = min(x1, y1), y = n - x + 1;
    int a = x, b = y;
    x = min(a, b);
    y = max(a, b);
    if (x1 >= x && x1 <= y && y1 <= y && y1 >= x)rank1 = x;
    else {
        int xx = max(x1, y1), yy = n - xx + 1;
        int aa = xx, bb = yy;
        xx = min(aa, bb);
        yy = max(aa, bb);
        if (x1 >= xx && x1 <= yy && y1 <= yy && y1 >= xx)rank1 = n - yy + 1;
    }
    x = min(x2, y2), y = n - x + 1;
    a = x, b = y;
    x = min(a, b);
    y = max(a, b);
    if (x2 >= x && x2 <= y && y2 <= y && y2 >= x)rank2 = x;
    else {
        int xx = max(x2, y2), yy = n - xx + 1;
        int aa = xx, bb = yy;
        xx = min(aa, bb);
        yy = max(aa, bb);
        if (x2 >= xx && x2 <= yy && y2 <= yy && y2 >= xx)rank2 = n - yy + 1;
    }
    //cout << rank1 << ' ' << rank2 << endl;
    cout << abs(rank1 - rank2) << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    cin >> h_h;
    while (h_h--)solve();
}

其实直接使用坐标映射到对应的层数上方即可，还是要多观察规律

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

void solve() {
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    int rank1, rank2;
    rank1 = min({x1, y1, n - x1 + 1, n - y1 + 1});
    rank2 = min({x2, y2, n - x2 + 1, n - y2 + 1});
    cout << abs(rank1 - rank2) << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    cin >> h_h;
    while (h_h--)solve();
}

C Restore the Arra

又是cf经典的构造题，我的方法是将数字存入两个数组，一个数组来添加元素，一个用来判断条件，我们从一个开始判断，如果和下一个的最大值符合就继续遍历，如果不符合就往这个数的后面加一个最小的数零，并且标记已经添加过了，因为题目说只能加一个，然后如果后面遇到不符合的情况，九八这个数的值变为教的的那个书的值，就构造完了，可能表述不清楚，见谅。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 200010;

int b[N];
int n;

void solve() {
    cin >> n;
    int a[N];
    memset(b, 0, sizeof b);
    for (int i = 1; i <= n - 1; i++)cin >> b[i], a[i] = b[i];
    int r = n;
    int res = 0;
    for (int i = 1; i <= n - 1; i++) {
        if (b[i] != max(a[i], a[i + 1])) {
            if (res == 0) {
                for (int j = n; j >= i + 2; j--)a[j] = a[j - 1];
                a[i + 1] = 0;
                res = 1;
            } else a[i] = a[i + 1];
        }
    }
    if (res == 0)a[n] = b[n - 1];
    for (int i = 1; i <= n; i++)cout << a[i] << ' ';
    cout << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    cin >> h_h;
    while (h_h--)solve();
}

D Umka and a Long Flight

这个题主要的思想还是贪心，而且我们不要去拼，而是去裁它，最终如果额能够裁到只剩一个正方行输出YES，否则就输出NO，我们还要提前处理一下斐波那契的数，使用dfs不断去裁剪它，并且我们要注意，每次dfs以后要更新小正行的坐标，保证都是宽比高长，它是裁成n+1个正方形，所以当的方式的次数为n的时候就可以return了，dfs一定要注意边界不然容易不断递归.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 50;

int F[N];

void init() {
    F[0] = F[1] = 1;
    for (int i = 2; i <= N; i++)F[i] = F[i - 1] + F[i - 2];
}

bool dfs(int n,int x,int y) {
    if (n == 0)return true;
    if (y > F[n])return dfs(n - 1, y - F[n], x);
    else if (y <= F[n - 1]) return dfs(n - 1, y, x);
    else return false;
}

int main() {
    init();
    int T;
    cin >> T;
    while (T--) {
        int n, x, y;
        cin >> n >> x >> y;
        if (dfs(n, x, y))puts("Yes");
        else puts("No");
    }
    return 0;
}

E Living Sequence

可以使用数位DP+二分的方法来做，也可以转化为九进制的数来做，二这个九进制数很特殊，没有四，要把4-8的数用5-9来表示，所以把十进制的数转化为九进制的数就可以了，并且判断每一位数字不能有四，如果大于等于四就加一。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

#define int long long

using namespace std;

void solve() {
    vector<int> ve;
    int n;
    cin >> n;
    while (n) {
        ve.push_back(n % 9);
        n /= 9;
    }
    for (int i = 0; i < ve.size(); i++)if (ve[i] >= 4)ve[i]++;
    reverse(ve.begin(), ve.end());
    for (auto i: ve)cout << i;
    puts("");
}

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