每日洛谷 10 月水题记录，有哪些你还没解决的难题？
摘要：每日水题记录（洛谷 10 月） 只记录红橙题，因为 (ge) 橙不算很水的题。 (2023.11.9) P1012 [NOIP1998 提高组] 拼数 (75) 分代码 直接把每个数字用字符串输入，然后按字典序排序。 原因：不
每日水题记录（洛谷 10 月）
只记录红橙题，因为 \(\ge\) 橙不算很水的题。
\(2023.11.9\)
P1012 [NOIP1998 提高组] 拼数
\(75\) 分代码
直接把每个数字用字符串输入，然后按字典序排序。
原因：不能直接按字典序排序，寄。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 22, kInf = (((1 << 30) - 1) << 1) + 1;
int n;
string s[kMaxN];
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> s[i];
}
sort(s + 1, s + n + 1);
for (int i = n; i >= 1; -- i) {
cout << s[i];
}
return 0;
}
\(100\) 分代码
我们直接用自己秘制的全比排序（注：这是以前写的，语言会有点那啥），每次比较 \(2\) 个数 \(a, b\)，如果 \(a + b > b + a\)，则交换 \(a, b\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 22, kInf = (((1 << 30) - 1) << 1) + 1;
int n;
string s[kMaxN];
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> s[i];
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
if (cmp(s[i], s[j])) {
swap(s[i], s[j]);
}
}
}
for (int i = n; i >= 1; -- i) {
cout << s[i];
}
return 0;
}
当然，还有 \(O(n \log n)\) 的快速排序。