A - 4305. 斐波那契字符串

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, f[N];
bool st[N];

int main()
{
    cin >> n;

    f[0] = f[1] = 1;
    st[1] = true;

    for (int i = 2; f[i - 1] <= n; i ++ )
    {
        f[i] = f[i - 1] + f[i - 2];
        st[f[i]] = true;
    }

    for (int i = 1; i <= n; i ++ )
        if (st[i]) cout << 'O';
        else cout << 'o';

    return 0;
}

B - 4306. 序列处理

Code (自己的做法)

#include <bits/stdc++.h>
using namespace std;
const int N = 3010;

int n, a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    
    sort(a + 1, a + 1 + n);
    
    int res = 0;
    for (int i = 2; i <= n; i++)
    {
        while (a[i] <= a[i - 1]) 
        {
            a[i]++;
            res++;
        }
    }
    
    cout << res;
    return 0;
}

Code (yxc的做法)

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

using namespace std;

const int N = 3010;

int n;
int q[N];

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) cin >> q[i];

    sort(q, q + n);

    int res = 0;
    for (int i = 0, last = 0; i < n; i ++ )
    {
        int cur = max(last + 1, q[i]);
        res += cur - q[i];
        last = cur;
    }

    cout << res << endl;
    return 0;
}

C - 4307. 数字重构(贪心)

题目描述

avatar

解题思路

独白:这道题起初拿到手误把$10^{18}$看成数字位数了,吓得我连排序都不敢,还以为是数位dp

一种经典的贪心:
如果a的长度小于b的长度,直接输出即可
如果长度相等的话:
1.从高到低,从大到小枚举每一位
2.这一位的后面所有位以从大到小(这样处理一定能保证最大)的顺序排序
3.如果拼接起来后的res < b(即最小的顺序能够比b小的话),说明是可行的,直接加上!

Code

#include <bits/stdc++.h>
using namespace std;

int cnt[10];

string get_min(int x)
{
    string res = to_string(x);
    cnt[x]--;
    
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < cnt[i]; j++)
            res += to_string(i);
        
    cnt[x]++;
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    
    if (a.length() < b.length())
    {
        sort(a.begin(), a.end(), greater<char>());
        cout << a;
    }
    else 
    {
        for (auto c : a)    cnt[c - '0']++;  // 统计每个数的数量
        string res;
        
        for (int i = 0; i < a.length(); i++)
            for (int j = 9; j >= 0; j--)   // 从高到低枚举每一位
            {
                if (cnt[j] && res + get_min(j) <= b)
                {
                    res += to_string(j);
                    cnt[j]--;
                    break;  // 每次只检测一位,所以直接break
                }
            }
            
        cout << res;
    }
    
    return 0;
}
上一篇 下一篇