$A：AcWing 4305.$ 斐波那契字符串

一开始错误的求了前1000位斐波那契数列，疯狂$SF$，其实完全不需要求那么多位…,应该用$c$来控制范围的上限

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
bool st[N];
int main()
{
    int n; cin >> n;
    int a = 0, b = 1, c;
    while (c <= 1000)
    {
        c = a + b;
        a = b, b = c;
        st[c] = true;
    }
    for (int i = 1; i <= n; i ++)
        if (st[i]) cout << 'O';
        else cout << 'o';

    return 0;
}

$B：AcWing 4306.$ 序列处理

$My$ $Code$

对于每一个出现次数大于1的数$x$，从$x+1$开始找后面没有出现过的第一个数$y$，将x加上$y-x$，标记$y$已经出现，这样的时间复杂度是$O(N^2)$，但是对于最后两组过不了的数据，比如1 1 1 … 2800 … 2800 …，当大量数据聚集出现在后半段的时候，$j$枚举的范围应该远超过$n$，所以对于数据量为3000的的数据(小于3000的话就算不完，$WA$)，j要开到远大于3000，但是这样时间复杂度会爆，所以这种做法不行

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int w[N], cnt[N];
int main()
{
    int n, start = 0x3f3f3f3f; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i], cnt[w[i]] ++, start = min(start, w[i]);
    long long ans = 0;
    sort(w + 1, w + 1 + n);
    for (int i = 1; i <= n; i ++)
        if (cnt[w[i]] > 1)
        {
            for (int j = w[i] + 1; j <= 3000; j ++)
                if (!cnt[j])
                {

                    ans += (j - w[i]);
                    cnt[j] ++;
                    break;
                }
            cnt[w[i]] --;
        }
    printf("%lld", ans);
    return 0;
}

正确做法

可以发现我们上一种做法在枚举j的时候存在大量重复的不必要枚举，所以我们可以对这个部分进行优化
先将所有$w[i]$排序，对于每一个$w[i]$，我们都将它$+1$到大于前面一个数(这其实就是上一种做法中的枚举j)，每$+1$一次，操作次数也就$+1$，这样就避免了对j的重复枚举

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int w[N], cnt[N];
int main()
{
    int n, start = 0x3f3f3f3f; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];
    long long ans = 0;
    sort(w + 1, w + 1 + n);
    for (int i = 2; i <= n; i ++)
        while (w[i] <= w[i - 1])
        {
            ans ++;
            w[i] ++;
        }
    printf("%lld", ans);
    return 0;
}

$C：AcWing 4307.$ 数字重构

错误点：

打乱重组的数位问题

1. 在判断每位能选的最大的数的时候，不能只看在$b[i]$的限制下，$a[i]$以选的最大值，还需要判断能选的数中是否还剩余这个能选的最大数，比如$a=15778899$，$b=98715689$，如果不判断的话凑出来的最大$a$为$98715798$，但其实从最后三位中的7开始就已经不能选$7、8、9$了，这就是因为没有判断能选的最大数是否还有剩余
2. 前面已经确定的数位是否与$b$中部分完全相同要取决于前面的数位是否完全相同和当前位置是否相同，即$same$ && $i == b[pos]$
3. 最高位不能取$0$可以在枚举$i$的时候用$pos ? 1 : 0$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100;
int a[N], b[N], cnt[N], ans[N], lena = -1, lenb = -1;
bool dfs(int pos, bool same)  // 当前位置，前面的已选的部分是否完全一样
{
    if (pos == -1) return true;
    for (int i = 9; i >= (pos == lena ? 1 : 0); i --)  // 第一位不能选0
    {
        if (same && i > b[pos] || !cnt[i]) continue;
        cnt[i] --, ans[pos] = i;
        if (dfs(pos - 1, same && i == b[pos])) return true;  // 注意下一位前面是否与前面相同取决于前面的same及i和b[pos]
        cnt[i] ++;
    }
    return false;
}
int main()
{
    LL n, m; 
    scanf("%lld %lld", &n, &m);
    while (n) a[++ lena] = n % 10, cnt[n % 10] ++, n /= 10;
    while (m) b[++ lenb] = m % 10, m /= 10;
    if (lena < lenb)
    {
        sort(a, a + lena + 1);
        for (int i = lena; i >= 0; i --) cout << a[i];
        return 0;
    }
    dfs(lena, true);
    for (int i = lena; i >= 0; i --) cout << ans[i];
    return 0;
}