Bình luận

• 
  

  4

  jumptozero    7:18 a.m. 18 Tháng 6, 2020 ← chỉnh sửa 5 →

  • Mình xin chia sẻ lời giải bài toán này như sau:
  • Đầu tiên ta có chú ý đó là: Vì \(C\) được tạo từ các chữ số của \(A\) và \(B\) và \(C\) có \(N+M\) chữ số. Nên nếu \(C\) có số \(0\) đứng đầu thì xem như số đó không thỏa mãn , vì nó không được tính là \(N+M\) chữ số.
  • Ví dụ: \(A=10,B=1\). Thì số \(C=011\) là không thỏa mãn yêu cầu bài toán vì số chữ số thực sự của nó chỉ là \(2\ne 3\).
  • Tiếp theo ta đến phần tìm \(C\) nhỏ nhất.
  • Vì thứ tự của chuỗi \(A\) ta có thể tùy ý thay đổi, còn chuỗi \(B\) thì không, do đó để số \(C\) nhỏ nhất thì ta làm một việc đó là :
  • Ta sẽ sắp xếp lại chuỗi \(A\) thỏa mãn tính chất sau:
  • Nếu trong chuỗi \(A\) không có kí tự nào bằng \(0\) thì ta sẽ sắp xếp chuỗi theo tự tăng dần, tức là \(A[0],A[1],...,A[N-1]\)(trong đó \(A[0]<=A[1]<=...<=A[N-1]\))
  • Nếu trong chuỗi \(A\) tồn tại kí tự bằng \(0\) thì ta sẽ sắp xếp chuỗi theo dạng sau: \(s,0,0,...,A[i],A[i+1],...,A[N-1]\) (trong đó s là kí tự nhỏ nhất khác '0' , còn các phần tử còn lại ta sắp xếp theo tự tăng dần).
  • Ví dụ: Giả sử có có \(A=36002102\). Thì khi đó ta sắp xếp lại \(A\) như sau: \(A=10002236\).
  • Việc sắp xếp như vậy, sẽ giúp ta dễ dàng tìm được \(C\) thông qua việc sử dụng một vòng while và hai con trỏ tương ứng với hai chuỗi \(A\) và \(B\).
  • Ý tưởng của vòng lặp rất đơn giản:
  • Ta so sánh \(A[i]\) và \(B[j]\) để tìm ra số nhỏ nhất, và cộng vào chuỗi \(res\) (chuỗi \(res\) khởi tạo ban đầu là rỗng).
  • Nếu \(A[i]>B[j]\) thì ta cộng \(B[j]\) vào \(res\), ngược lại nếu \(A[i]<B[j]\) thì ta cộng \(A[i]\) vào \(res\).
  • Điểm hay của bài toán này đó là khi \(A[i]=B[j]\) thì ta chọn \(A[i]\) hay \(B[j]\) để cộng vào \(res\) ???
  • Để giải quyết nút thắt này, ta cần phải so sánh \(A[i+1]\) và \(B[j+1]\).
  • Các bạn có thể xem đoạn xử lý dưới đây:
    
    C++

    if(s1[i]<s2[j]) {res+=s1[i];i++;}
                else if(s1[i]>s2[j]){res+=s2[j];j++;}
                else {
                    if(s1[i+1]<s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s1[i];i++;continue;}
                    if(s1[i+1]>s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s2[j];j++;continue;}
                    if(i+1==s1.size()||j+1==s2.size()) {res+=s2[j];j++;continue;}
                    if(s1[i+1]==s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s2[j];j++;continue;}
                }
                continue;
    

  • Như vậy ta đã giải quyết xong phần tìm \(C\) nhỏ nhất,
  • Tiếp theo đến phần tìm \(C\) lớn nhất. Phần này tương tự phần tìm \(C\) nhỏ nhất !
  • Như vậy là bài toán đã giải quyết xong.
  • Các bạn có thể tham khảo code của mình tại \(\href{https://ideone.com/5EhCY2}{đây}\)

  • Nếu có gì sai hoặc khó hiểu, các bạn cứ comment nhé!

  • P/s: Code mình hơi xấu !

• 
  

  0

  SPyofgame    8:04 a.m. 19 Tháng 6, 2020 ← chỉnh sửa 2 →

  Anh thử dùng

  ```cpp

  C++

  code();
  

  ```

  ạ UwU

  Và anh có thể format code cho dễ nhìn hơn đấy ạ UwU

• 
  

  2

  SPyofgame    9:33 a.m. 18 Tháng 6, 2020 ← đã chỉnh sửa →

  Đoạn code anh viết còn khá rồi mắt ạ 😢

• 
  

  2

  minhtuanitk20    10:19 p.m. 6 Tháng 2, 2022

  cách của SPyofgame dễ hình dung hơn
5 bình luận nữa