Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm kiếm số lượng chuỗi nến đầy màu sắc ngày càng tăng nghiêm ngặt có trong Python

Giả sử có n ngọn nến được xếp theo thứ tự từ trái sang phải. Cây nến thứ i tính từ phía bên trái có chiều cao h [i] và màu c [i]. Chúng ta cũng có một số nguyên k, biểu thị có các màu trong phạm vi từ 1 đến k. Chúng ta phải tìm xem có bao nhiêu chuỗi kẹo có màu sắc tăng dần nghiêm ngặt? Trình tự tăng dần được kiểm tra dựa trên độ cao và một chuỗi được cho là có nhiều màu sắc nếu có ít nhất một ngọn nến của mỗi màu trong phạm vi từ 1 đến K. Nếu câu trả lời quá lớn, thì trả về kết quả mod 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như K =3 h =[1,3,2,4] c =[1,2,2,3], thì đầu ra sẽ là 2 vì nó có các chuỗi [1,2,4] và [1,3,4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm read (). Điều này sẽ mất T, i
  • s:=0
  • while i> 0, do
    • s:=s + T [i]
    • s:=s mod 10 ^ 9 + 7
    • i:=i - (i AND -i)
  • trả lại s
  • Xác định một bản cập nhật chức năng (). Điều này sẽ mất T, i, v
  • while i <=50010, do
    • T [i]:=T [i] + v
    • T [i]:=T [i] mod 10 ^ 9 + 7
    • i:=i + (i AND -i)
  • return v
  • Từ phương pháp chính, hãy thực hiện như sau -
  • L:=2 ^ k, R:=0, N:=kích thước của h
  • đối với tôi trong phạm vi từ 0 đến L - 1, thực hiện
    • T:=một mảng có kích thước 50009 và điền bằng 0
    • t:=0
    • đối với j trong phạm vi từ 0 đến N - 1, thực hiện
      • nếu (i sau khi dịch các bit (c [j] - 1) lần sang phải) là số lẻ, thì
        • t:=t + update (T, h [j], read (T, h [j] - 1) + 1)
        • t:=t mod 10 ^ 9 + 7
    • nếu (số bit trong i) mod 2 giống với k mod 2, thì
      • R:=R + t
      • R:=R mod 10 ^ 9 + 7
    • nếu không,
      • R:=(R + 10 ^ 9 + 7) - t
      • R:=R mod 10 ^ 9 + 7
  • trả về R

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

def solve(k, h, c):
   def read(T, i):
      s = 0
      while i > 0:
         s += T[i]
         s %= 1000000007
         i -= (i & -i)
      return s

   def update(T, i, v):
      while i <= 50010:
         T[i] += v
         T[i] %= 1000000007
         i += (i & -i)
      return v

   def number_of_bits(b):
      c = 0
      while b:
         b &= b - 1
         c += 1
      return c

   L = 2 ** k
   R = 0
   N = len(h)

   for i in range(L):
      T = [0 for _ in range(50010)]
      t = 0

      for j in range(N):
         if (i >> (c[j] - 1)) & 1:
            t += update(T, h[j], read(T, h[j] - 1) + 1)
            t %= 1000000007

      if number_of_bits(i) % 2 == k % 2:
         R += t
         R %= 1000000007
      else:
         R += 1000000007 - t
         R %= 1000000007
   return R

k = 3
h = [1,3,2,4]
c = [1,2,2,3]

print(solve(k, h, c))

Đầu vào 

3, [1,3,2,4], [1,2,2,3]

Đầu ra 

2