thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
)
Windows 2001
Member
Xong, hôm nay Q4 dễ 
Windows 2001
Member
Bị lag mấy phút đầu xong vào lại được rồi, fen vào làm đi
aNotHeRNo0b
Senior Member
Sửa lần cuối:
freedom.99
Senior Member
Cái test case leetcode example = 5 mà lúc import vô nó là n = 3, làm mình ko hiểu sao sai cay thật 
athxzz
Senior Member
e giống bác, + 10 phút lag nữa nên contest này bay màu rCái test case leetcode example = 5 mà lúc import vô nó là n = 3, làm mình ko hiểu sao sai cay thật
JakovichTimViec
Senior Member
JakovichTimViec
Senior Member
Câu 4 em làm DP nè bác
Vhnguyen
Senior Member
Câu 4 các state DP của bác thế nào? Mình không làm DP vẫn pass O(logN). Mình nhận ra là mỗi cái recursive call nhân step lên 2 lần thì các state của DP cũng không trùng lặp nhiều lắm, tính ra không tối ưu được bao nhiêu.
Python:
class Solution:
def lastInteger(self, n: int) -> int:
def op1(l, r, s):
if l == r:
return l
sec = l+s
if (r-sec) % (s*2) == 0:
new_r = r-s
else:
new_r = r
return op2(l, new_r, s*2)
def op2(l, r, s):
if l == r:
return l
sec = r-s
if (sec-l) % (s*2) == 0:
new_l = l+s
else:
new_l = l
return op1(new_l, r, s*2)
return op1(1, n, 1)
Python:
class Solution:
def lastInteger(self, n: int) -> int:
def dp(k, fromLeft):
if k == 1:
return 0
if fromLeft:
new_k = (k + 1) // 2
res = dp(new_k, False)
return res * 2
else:
new_k = (k + 1) // 2
res = dp(new_k, True)
if k % 2 == 0:
return res * 2 + 1
else:
return res * 2
return dp(n, True) + 1À không phải DP bác, chỉ là recursive th, quen đặt tên func là dp nên lú
freedom.99
Senior Member
Thôi unrate ai về nhà nấy
JakovichTimViec
Senior Member
Bài 4 kiểu toán quá, mà em thì ghét toán cực.
.
Q2 mấy bác optimize kiểu gì thế chứ em chơi 3 Heap cho mỗi mod 0 1 2 (size_max=3) xong tổng kết lại là ra
Q2 mấy bác optimize kiểu gì thế chứ em chơi 3 Heap cho mỗi mod 0 1 2 (size_max=3) xong tổng kết lại là ra
C#:
public class Solution
{
public int MaximumSum(int[] nums)
{
[COLOR=rgb(29, 31, 32)] PriorityQueue<int, int>[] q = new PriorityQueue<int, int>[3];[/COLOR]
for (int i = 0; i < 3; i++)
q[i] = new();
foreach(var i in nums)
{
var c = i % 3;
q[c].Enqueue(i,i);
if (q[c].Count>3)
q[c].Dequeue();
}
List<int> l = new();
for (int i = 0; i < 3; i++)
while (q[i].Count > 0)
l.Add(q[i].Dequeue());
int rtn= 0;
for(int i=0;i<l.Count;i++)
for(int j=i+1;j<l.Count;j++)
for(int k=j+1;k<l.Count;k++)
{
var sum = l[i] + l[j] + l[k];
if (sum % 3 == 0)
rtn = Math.Max(sum, rtn);
}
return rtn;
}
}Vhnguyen
Senior Member
Bài này mình thấy chia 3 cũng nhỏ thôi thì tính hết các trường hợp ra luôn cho chắc kèoBài 4 kiểu toán quá, mà em thì ghét toán cực..
Q2 mấy bác optimize kiểu gì thế chứ em chơi 3 Heap cho mỗi mod 0 1 2 (size_max=3) xong tổng kết lại là ra
C#:public class Solution { public int MaximumSum(int[] nums) { [COLOR=rgb(29, 31, 32)] PriorityQueue<int, int>[] q = new PriorityQueue<int, int>[3];[/COLOR] for (int i = 0; i < 3; i++) q[i] = new(); foreach(var i in nums) { var c = i % 3; q[c].Enqueue(i,i); if (q[c].Count>3) q[c].Dequeue(); } List<int> l = new(); for (int i = 0; i < 3; i++) while (q[i].Count > 0) l.Add(q[i].Dequeue()); int rtn= 0; for(int i=0;i<l.Count;i++) for(int j=i+1;j<l.Count;j++) for(int k=j+1;k<l.Count;k++) { var sum = l[i] + l[j] + l[k]; if (sum % 3 == 0) rtn = Math.Max(sum, rtn); } return rtn; } }
Python:
class Solution:
def maximumSum(self, nums: List[int]) -> int:
nums = sorted(nums, reverse=True)
div_map = {0: [], 1: [], 2: []}
for n in nums:
div_map[n%3].append(n)
print(div_map)
s0 = float("-inf")
if len(div_map[0]) >= 3:
s0 = sum(div_map[0][:3])
s1 = float("-inf")
if len(div_map[1]) >= 3:
s1 = sum(div_map[1][:3])
s2 = float("-inf")
if len(div_map[2]) >= 3:
s2 = sum(div_map[2][:3])
s3 = float("-inf")
if len(div_map[0]) >= 1 and len(div_map[1]) >= 1 and len(div_map[2]) >= 1:
s3 = div_map[0][0] + div_map[1][0] + div_map[2][0]
ans = sorted([s0,s1,s2,s3], reverse=True)[0]
if ans == float("-inf"):
return 0
return ansChủ đề tương tự
