Bình luận

• 
  

  4

  phuc11731    10:20 p.m. 18 Tháng 2, 2024

  s=input()
  def NMP(s,n):
      global m
      i=0
      while i!=n:
          if s[i] in ex:
              k,i=NMP1(s,n,i)
              t=int(k)
              if t>m:m=t
          i+=1
  def NMP1(s,n,i):
      k,j=s[i],0
      for j in range(i+1,n):
          if s[j] in num:k+=s[j]
          else:
              j-=1
              break
      i=j
      return k,i
  ex,num,m='-0123456789','0123456789',float('-inf')
  NMP(s,len(s))
  print(m)
  

• 
  

  24

  dang7rickroll    7:15 p.m. 2 Tháng 2, 2022 ← đã chỉnh sửa →

  Sau 7749 lần submit và debug thì cuối cùng mình cũng đã AC bài này và xin chia sẻ lời giải bài này như sau:

  Mình sẽ chia lời giải này thành 2 phần:

  • Phần 1. Giải subtask 1 (đề chuẩn)
  • Phần 2. Giải subtask 2 (đề mở rộng)

  Phần 1. Giải subtask 1 (đúng 10/13 test)

  • Tư tưởng chính của thuật toán để giải subtask 1 của mình là lọc ra các số nguyên có trong xâu và đưa vào một mảng số nguyên và sử dụng thuật tìm giá trị lớn nhất của mảng và in ra kết quả.
  • Ta sẽ chia ra 3 trường hợp có thể xảy ra đối với subtask 1 và sẽ lần lượt giải từng trường hợp
  • Trường hợp 1. Có các chữ cái trong xâu và chỉ bao gồm số nguyên dương
  • Trường hợp 2. Có các chữ cái trong xâu và có thể bao gồm cả số nguyên âm
  • Trường hợp 3. Không có chữ cái trong xâu.

  Với trường hợp 1, ta sẽ duyệt từ đầu đến cuối xâu, nếu ký tự đang xét là chữ số thì cộng chữ số này vào đáp án theo công thức res = 10*res + (s[i] - '0').

  Ta sẽ lặp lại công thức trên cho đến khi ký tự đang xét không còn là chữ số nữa thì ta sẽ cộng biến res vào mảng số nguyên, khởi tạo lại res = 0.

  ---

  Với trường hợp 2, thì ta cần cần xét: nếu ký tự hiện tại đang xét là chữ số và ký tự phía trước là dấu trừ (-) thì vẫn sử dụng công thức ở trên, nhưng thay dấu cộng bằng dấu trừ.

  Rồi làm y hệt như trường hợp 1.

  ---

  Với trường hợp 3, ta sử dụng hàm kiểm tra 1 xâu có phải xâu số hay không (tham khảo của mình):
  

  bool isNumber (string s)
  {
      for (int i = 0; i < s.size(); i++)
      {
          if (isdigit(s[i]) == false) return false;
      }
      return true;
  }
  

  Nếu nó là xâu số thì không cần phải xét gì nữa, in ra nó luôn (bạn cũng hiểu tại sao mà)

  ---

  Phần 2. Giải subtask 2 (Accepted)

  Theo đề mở rộng thì \(|S| \le 10^6\) nên có thể số nguyên lớn nhất có thể vượt quá long long nên dùng string để thao tác.

  Trước hết ta cần viết một hàm so sánh giữa 2 xâu.

  Hàm này của mình đã vẽ ra cho cả 3 trường hợp đã nêu ở phần 1:

  string maximize(string a, string b)
  {
      if (a[0] == '-' && b[0] != '-') return b; //1
      if (a[0] != '-' && b[0] == '-') return a; //2
      if (a[0] == '-' && b[0] == '-') return min(a,b); //3
      if (a[0] == '-' && b[0] == '0') return b; //4
      if (a[0] == '0' && b[0] == '-') return a; //5
      if (a.size() < b.size()) return b; //6
      if (a.size() > b.size()) return a; //7
      return max(a,b);//8
  }
  

  
  Giải thích 1 chút về hàm của mình:

  1. Trường hợp xâu \(a\) là số nguyên âm, xâu \(b\) là số nguyên dương \(\rightarrow\) trả về xâu \(b\).
  2. Trường hợp xâu \(a\) là số nguyên dương, xâu \(b\) là số nguyên âm \(\rightarrow\) trả về xâu \(a\).
  3. Trường hợp cả 2 xâu là số nguyên âm \(\rightarrow\) trả về xâu nhỏ hơn.
  4. Trường hợp xâu \(a\) là số nguyên âm và xâu \(b\) là số \(0\) \(\rightarrow\) trả về xâu \(b\).
  5. Trường hợp xâu \(b\) là số nguyên âm và xâu \(a\) là số \(0\) \(\rightarrow\) trả về xâu \(a\).
  6. Trường hợp xâu \(a\) ngắn hơn xâu \(b\) \(\rightarrow\) trả về xâu \(b\).
  7. Trường hợp xâu \(b\) ngắn hơn xâu \(a\) \(\rightarrow\) trả về xâu \(a\).

  ---

  Ta cũng chia subtask 2 này thành 3 trường hợp như subtask 1:

  • Nếu xâu đó là xâu số thì in ra luôn.
  • Trường hợp có cả số nguyên âm và nguyên dương và trường hợp chỉ có số nguyên dương ta gộp thành 1 lần để tiện cài đặt: nếu ký tự đang xét là số hoặc là dấu - thì ta xét tiếp: nếu res rỗng và ký tự đang xét là số 0 thì bỏ qua, ngược lại chèn ký tự đang xét vào phía sau res.
  • Ngược lại thì ta kiểm tra: nếu res khác rỗng thì lấy max của res và ans (ans ở đây là biến lưu kết quả để in ra màn hình), reset lại res.
  • Xuất ra kết quả.

  Code tham khảo cho subtask 1: Đây

  Code tham khảo cho subtask 2: Đây

  ---

  P/s: Upvote hoặc tôi sẽ dẫn bạn đến Gulag

  2 phản hồi