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. 数字重构(贪心)
题目描述
解题思路
独白:这道题起初拿到手误把$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;
}