每日水题记录（洛谷）

只记录红橙题，因为 \(\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)\) 的快速排序。

#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];
  }
  sort(s + 1, s + n + 1, cmp);
  for (int i = 1; i <= n; ++ i) {
    cout << s[i];
  }
  return 0;
}

to be update.