Hướng dẫn giải của Trại hè Đà Lạt 2020 - Ghép số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Ta thấy số lượng chữ số sau khi ghép của mọi cách là như nhau, nên để số sau khi ghép có giá trị lớn nhất thì các số ở phía đầu phải lớn nhất , hay nói cách khác khi ghép ~a_i~ và ~a_j~, ~a_i~ sẽ đứng trước ~a_j~ nếu ~a_i+a_j > a_j+a_i~. Vì vậy, ta sắp xếp các phần tử và in ra theo thứ tự trên.
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
/***Crazy Macros***/
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define reu(i,a,b) for(ll i = (a); i <= (b); ++i)
#define red(i,a,b) for(ll i = (a); i >= (b); --i)
typedef int64_t ll;
typedef deque<int> di;
typedef deque<ll> dll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef tuple<ll,ll,ll> iii;
const ll inf = 2e9;
/***Common Functions***/
ll inp() {ll x; cin >> x; return x;}
string inp_str() {string x; cin >> x; return x;}
ll sqr(ll n) {return n*n;}
ll power(ll a, ll b, ll mod = inf) {
ll res = 1; a %= mod;
for(ll i = b; i > 0; i /= 2) {
if (i % 2) res = (res*a) % mod;
a = (a*a) % mod;
} return res;
}
ll gcd(ll a, ll b) {
while (b > 0) {ll tmp = a % b; a = b; b = tmp;}
return a;
}
bool is_pal(string s) {return equal(all(s), s.rbegin());}
void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
void file_io(char *in, char *out) {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
void print_bool(bool a) {
if (a) cout << "YES\n";
else cout << "NO\n";
}
/***Main Code***/
ll n;
vector<string> a;
void Input() {
cin >> n;
a.clear();
a.resize(n+1);
generate(1+all(a), inp_str);
}
bool cmp(string a, string b) {
return a+b > b+a;
}
void Solve() {
sort(1+all(a), cmp);
for(auto v : a) cout << v;
}
int main()
{
fast_io();
// file_io("MAXV.INP", "MAXV.OUT");
Input(), Solve();
return 0;
}
Bình luận