htss
Senior Member
giờ mới biết cái mobius này
Phi(d) là hàm phi euler à thím? sao ra được cái này thế thím?
thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
clonemasteruwu
Senior Member
ờ, totient function đó.giờ mới biết cái mobius này
Phi(d) là hàm phi euler à thím? sao ra được cái này thế thím?
thay gcd vô cái n bên trên, xong gộp những thằng d giống nhau vào
htss
Senior Member
Test 1:
3 4 5
d = 1 -> 3 phần tử chia hết cho 1 -> (2 ^ 3 - 1) * phi(1) = 7
d = 2 -> (2 ^ 1 - 1) * phi(2) = 1
d = 3 -> (2 ^ 1 - 1) * phi(3) = 2
d = 4 -> (2 ^1 - 1) * phi(4) = 2
d = 5 -> (2^1 - 1) * phi(5) = 4
Cộng lại ko ra 119 như trong test. mình tính có sai ở đâu ko nhỉ?
thuyduong2007
Member
Ở trên thì nói là từng cho làm lúc phỏng vấn. Dưới lại nói cần gì đi pv ai cái đó. Sao câu dưới lại đá câu trên vậy?
clonemasteruwu
Senior Member
đọc nhầm bội chung nhỏ nhất (lcm) thành ước chung lớn nhất (gcd)
thấy trên stackoverflow có solution bằng dp
giới hạn i như bài nàyhttps://stackoverflow.com/questions...ommon-multiples-of-all-subsets-of-a-given-set
nashwade
Senior Member
Giờ xem lại nguồn mới thấy bài này thuộc dạng siêu khó các bác à. Nó là bài F trong ICPC Regional Hatyai 2012, được upload trên gym của Codeforces https://codeforces.com/gym/101549/standings. Trong bảng rank này chỉ có mỗi team của tourist làm được, team rank 2 cũng là team vô địch WF mà còn không giải được 
_Gia_Cat_Luong_
Senior Member
Vkl thế mà mấy bác nhà mình giải 1 nốt nhạc. Vozer lương chuẩn 350m là có thậtGiờ xem lại nguồn mới thấy bài này thuộc dạng siêu khó các bác à. Nó là bài F trong ICPC Regional Hatyai 2012, được upload trên gym của Codeforces https://codeforces.com/gym/101549/standings. Trong bảng rank này chỉ có mỗi team của tourist làm được, team rank 2 cũng là team vô địch WF mà còn không giải được
KimSoHyunGoddness
Member
uả bài này nếu em giải bằng JS thì kq là: return x ** nNay thấy topic này vắng quá. Nên mình sẽ share bài mình mới làm chiều nay.
https://leetcode.com/problems/powx-n/
Yêu cầu là implement hàm pow.
Đọc đề xong thấy bài này easy vkl, k hiểu sao lại là medium, nghĩ trong bụng bài này chắc done trong 1 nốt nhạc. Chỉ cần 1 vòng for chạy từ 0->n rồi nhân lại là xong. dpt là O(n).
Lúc đó ngồi nghĩ kỹ lại mới thấy bài này hoàn toàn có thể giải với đpt là O(logN).
tại vì m^n = m^(n/2)*m^(n/2) như vậy mình chỉ cần tính m^(n/2) 1 lần thôi.
Bài này chắc là kinh điển, nên chắc nhiều anh em cũng từng làm qua rồi.C++:class Solution { public: double myPow(double x, int n) { double result = 1; x = n > 0 ? x : 1/x; for (int i = 0; n != 0; i++){ result *= n%2!=0 ? x : 1; n/=2; x = x*x; } return result; } };
Mà bản chất x ** n là 1 vòng for hả bác
_Gia_Cat_Luong_
Senior Member
x ** n chắc bên dưới cũng implement O(logn) thôi, đoán thế. Cơ mà đề k cho dùng cách này đâu.
Edit: Nó translate thành n * n * n.... => O(n)
Yêu em Thu Nga CN12 ptit
Senior Member
Mấy bác cho em hỏi bài này với, ý tưởng của e là xét 4 ô xung quanh của ô đang xét (ô đang xét tất nhiên là giá trị =1, còn 4 ô xung quanh ô cần xét là [i-1][j],[i-1][j-1],[j-1],[i-1][j+1]), lấy max của 4 thằng đó + với 1, sau khi xét xong mảng, nếu ô đó có dp==1 thì ta tăng đáp số lên 1, nếu > 1 nghĩa là đã được đếm nên không tăng đáp án. Mà không hiểu sao cứ sai, em hiểu sai chỗ nào hay nó có test đặc biệt vậy
C++:
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int a[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
vector<vector<int> >dp(n+2,vector<int>(m+2,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i-1][j-1]==1){
dp[i][j]=max(max(max(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]),dp[i][j-1])+1;
}
}
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dp[i][j]==1) res++;
}
}
cout<<res<<"\n";
}
}
}
cuc gach
Junior Member
Cần kiểm tra 8 vị trí xung quanh chứ không phải 4.
Mấy bác cho em hỏi bài này với, ý tưởng của e là xét 4 ô xung quanh của ô đang xét (ô đang xét tất nhiên là giá trị =1, còn 4 ô xung quanh ô cần xét là [i-1][j],[i-1][j-1],[j-1],[i-1][j+1]), lấy max của 4 thằng đó + với 1, sau khi xét xong mảng, nếu ô đó có dp==1 thì ta tăng đáp số lên 1, nếu > 1 nghĩa là đã được đếm nên không tăng đáp án. Mà không hiểu sao cứ sai, em hiểu sai chỗ nào hay nó có test đặc biệt vậy
C++:#include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int a[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } vector<vector<int> >dp(n+2,vector<int>(m+2,0)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i-1][j-1]==1){ dp[i][j]=max(max(max(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]),dp[i][j-1])+1; } } } int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(dp[i][j]==1) res++; } } cout<<res<<"\n"; } } }
Bác có thể thử lại test này. Kết quả là 1.
1
3 3
0 0 1
1 1 1
1 1 1
Yêu em Thu Nga CN12 ptit
Senior Member
xong rồi bác, em cảm ơn
nashwade
Senior Member
Vòng loại Facebook Hacker Cup năm nay đang diễn ra, các bác nào có hứng thú có thể tham gia. Vòng này kéo dài 3 ngày và chỉ cần giải được 1/5 bài là sẽ vào vòng sau. https://www.facebook.com/codingcompetitions/hacker-cup/2021/
KimSoHyunGoddness
Member
này là làm về thuật toán luôn hả bác
nashwade
Senior Member
Đúng rồi bác
thuyduong2007
Member
Có ai tham gia cái này k? đang bị kẹt ở 2 bài cuối. Ai làm rồi cho ý tưởng với.
KimSoHyunGoddness
Member
Mấy bác giúp em giải thích đề bài này với. Em đọc chưa hiểu là combinations ntn
eraganxs
Member
Tổ hợp. Cho 2 số k và n. Tìm tổ hợp chập k trong dãy số [1,2,3,...,n]
Sent from Xiaomi M2102J20SG using vozFApp
vozguy
Member
Tổ hợp chập k phần tử trong dãy từ 1 đến n
Vd k=2, n=3
Có dãy 1->n là {1,2,3}
tổ hợp 2 pt [1,2] [1,3] [2,3]
_Gia_Cat_Luong_
Senior Member
để thử đk làm xem sao, lập team chơi k fen ?Có ai tham gia cái này k? đang bị kẹt ở 2 bài cuối. Ai làm rồi cho ý tưởng với.
Chủ đề tương tự
