Hello mọi người, đây là solution của e cho checkpoint 6 tháng đầu năm 2023.
Ý tưởng:
Tạo mảng Profits với kích N, với Profit[i] lưu lợi nhuận tối đa khi bán cổ phiếu tại thời điểm i:
=> Profit[i] = Giá tại vị trí i – Giá nhỏ nhất trước vị trí i;
Kết quả = Max(Profits)
Tối ưu:
Dùng biến CurrentMin (giá trị cổ phiếu nhỏ nhất tính đến hiện tại, khởi tạo = 10^6), CurrentMaxProfit (Lợi nhuận lớn nhất tính đến hiện tại, khởi tạo = 0).
Duyệt qua từng phần tử trong danh sách cổ phiếu:
- Nếu: giá trị hiện tại < CurrentMin => cập nhật lại CurrentMin = giá trị hiện tại, continue
- Nếu: giá trị hiện tại – CurrentMin > CurrentMaxProfit => cập nhật lại CurrentMaxProfit = giá trị hiện tại – CurrentMin
Code tham khảo:
N = int(input());
arr = [int(i) for i in input().split()];
CurrentMin = 1000000;
CurrentMaxProfit = 0;
for i in arr:
if i < CurrentMin:
CurrentMin = i;
continue;
if CurrentMaxProfit < i - CurrentMin:
CurrentMaxProfit = i - CurrentMin;
print(CurrentMaxProfit);
Để người tại vị trí i đứng khi kết thúc thì số ước số của i phải là số lẻ, để điều đó xảy ra i phải là số chính phương.
=> Đề bài : Tìm số chính phương lớn nhất <= N
Code ví dụ:
import math
print(int(math.sqrt(int(input())) // 1))
Ý tưởng:
Gom các máy được liên kết với nhau thành cụm => Số dây ít nhất = Số cụm – 1
Thuật toán dùng để gom cụm có thể dùng DSU (Disjoint Sets Union)
Code tham khảo:
class GomCum:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0 for i in range(n)]
def findRoot(self, x):
if self.parent[x] != x:
return self.findRoot(self.parent[x])
return self.parent[x]
def noi2May(self, x, y):
x_root = self.findRoot(x)
y_root = self.findRoot(y)
if x_root == y_root:
return
if self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
elif self.rank[x_root] > self.rank[y_root]:
self.parent[y_root] = x_root
else:
self.parent[y_root] = x_root
self.rank[x_root] += 1
def soDayItNhat(self, n):
return len(set([self.findRoot(i) for i in range(n)])) - 1
[n, m] = [int(i) for i in input().split()]
res = GomCum(n)
for i in range(m):
[a, b] = [int(i) for i in input().split()]
res.noi2May(a, b)
if m < n - 1 :
print(-1)
print(res.soDayItNhat(n))
Chạy vòng lặp. Khi 1 trong 2 chuỗi đã hết ký tự trong vòng lặp, thực hiện so sánh
Các case có thể gặp:
- 2 chuỗi khác tiền tố => Lấy ký tự đầu của chuỗi nhỏ hơn
- 2 chuỗi cùng tiền tố =>Lấy ký tự đầu của chuỗi có ký tự sau phần tiền tố chung nhỏ hơn (‘ABCD’ vs ‘ABCC’ => Lấy A trong ABCC)
- 2 chuỗi giống nhau => Lấy ký tự đầu của dãy nào cũng được
- 1 chuỗi là tiền tố của 1 chuỗi khác => Lấy ký tự đầu của dãy dài hơn ( Test thử với các case trong trường hợp này có thể đúc kết ra)
Code tham khảo:
def GetKey(d1, d2):
res = ''
while len(d1) and len(d2) :
Len = min(len(d1), len(d2))
if d1[:Len] < d2[:Len]:
res += d1[0]
d1 = d1[1:]
continue
if d2[:Len] < d1[:Len]:
res += d2[0]
d2 = d2[1:]
continue
if len(d1) > len(d2):
res += d1[0]
d1 = d1[1:]
continue
if len(d2) >= len(d1):
res += d2[0]
d2 = d2[1:]
continue
if len(d1) != 0:
return res + d1
if len(d2) != 0:
return res + d2
return res
n = int(input())
key = []
for i in range(n):
d1 = input()
d2 = input()
key.append(GetKey(d1, d2))
[print(i) for i in key]
Bài này chúng ta có thể giải bằng quy hoạch động:
Dùng 1 list ArrRes N phần tử, ArrRes[i] = (Min tổng các dự án bị loại bỏ từ 0 -> i) + Vi
Triển khai:
Tạo 1 store để lưu min tổng các dự án bị loại bỏ từ 0 -> i
Duyệt từ dự án đầu đến dự án cuối:
1) Nếu: i < k + 1: thêm vi vào store, ArrRes[i] = Vi, continue
2) ArrRes[i] = Vi + min(store)
3) xóa ArrRes[i – k – 1] khỏi store
Tối ưu store dùng BinarySearchTree
Code tham khảo:
class BinarySearchTree:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __init__(self):
self.root = None
self.min_value = None
def add(self, value):
if self.root is None:
self.root = self.Node(value)
self.min_value = value
else:
self._add_recursive(self.root, value)
if value < self.min_value:
self.min_value = value
def _add_recursive(self, node, value):
if value < node.value:
if node.left is None:
node.left = self.Node(value)
else:
self._add_recursive(node.left, value)
else:
if node.right is None:
node.right = self.Node(value)
else:
self._add_recursive(node.right, value)
def remove(self, value):
self.root = self._remove_recursive(self.root, value)
if value == self.min_value:
if self.root is None:
self.min_value = None
else:
node = self.root
while node.left is not None:
node = node.left
self.min_value = node.value
def _remove_recursive(self, node, value):
if node is None:
return None
if value < node.value:
node.left = self._remove_recursive(node.left, value)
elif value > node.value:
node.right = self._remove_recursive(node.right, value)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
successor = self._find_min(node.right)
node.value = successor.value
node.right = self._remove_recursive(node.right, successor.value)
return node
def _find_min(self, node):
if node.left is None:
return node
return self._find_min(node.left)
def begin(self):
return self.min_value
def add_list(self, values):
for value in values:
self.add(value)
def solve(n, x):
if n == 0:
return 0
Max = sum(arr)
if x >= n:
return Max
store = BinarySearchTree()
store.add_list(arr[:x + 1])
for i in range(x + 1, n):
arr[i] = arr[i] + store.begin()
store.remove(arr[i - x - 1])
store.add(arr[i])
return Max - store.begin()
n, x = map(int, input().split())
arr = [int(input()) for _ in range(n)]
print(solve(n, x))
