Thứ Hai, 30 tháng 11, 2020

Cho n người vẽ và m bức tranh, cùng với ma trận m*n. Trong đó t_ij cho biết thời gian người thứ i hoàn thành bức tranh thứ j. Một bức tranh được vẽ lần lượt từ người thứ nhất đến người thứ hai... cho đến người thứ n, và tất cả những người này làm việc liên tục và không có thời gian nghỉ ngơi. Thời điểm bắt đầu là 0. Hãy in tất cả thời điểm người thứ n hoàn thành tất cả các bức tranh.

Đề bài: $\href{https://codeforces.com/problemset/problem/416/B}{Đây}$

 Tóm tắt: Cho n người vẽ và m bức tranh, cùng với ma trận m*n. Trong đó t_ij cho biết thời gian người thứ i hoàn thành bức tranh thứ j. Một bức tranh được vẽ lần lượt từ người thứ nhất đến người thứ hai... cho đến người thứ n, và tất cả những người này làm việc liên tục và không có thời gian nghỉ ngơi. Thời điểm bắt đầu là 0. Hãy in tất cả thời điểm người thứ n hoàn thành tất cả các bức tranh.

Lời giải: Goi $dp[i][j]$ là thời điểm mà người thứ i kết thúc bức tranh thứ j.

Khi đó ta có công thức dp như sau: $dp[i][j]=max(dp[i][j-1],dp[i-1][j])+t[i][j]$.

Từ đây ta chỉ việc thực hiện tính toán mảng dp là xong, các bạn có thể xem thêm tại source

Souce:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define inf -1000000000000000000
  5. int main(){
  6. ll m,n;
  7. cin>>m>>n;
  8. ll a[m][n];
  9. ll i,j;
  10. for(i=0;i<m;i++)
  11. for(j=0;j<n;j++) cin>>a[i][j];
  12. ll dp[n][m];
  13. dp[0][0]=a[0][0];
  14. for(i=1;i<n;i++) dp[i][0]=dp[i-1][0]+a[0][i];
  15. for(j=1;j<m;j++){
  16. for(i=0;i<n;i++) dp[i][j]=max((j>0?dp[i][j-1]:inf),(i>0?dp[i-1][j]:inf)) + a[j][i];
  17. }
  18. for(j=0;j<m;j++) cout<<dp[n-1][j]<<" ";
  19. return 0;
  20. }

Bạn đang ở vị trí 0, và có các cây táo ở vị trí trên trên tọa độ. Ban đầu bạn có thể chọn qua trái hoặc phải tùy ý. Sau đó đi, gặp cây nào hái hết táo cây đó và đi ngược lại. Hỏi số táo tối đa tìm được là bao nhiêu ?

Đề bài: $\href{https://codeforces.com/problemset/problem/558/A}{Đây}$

 Tóm tắt: Bạn đang ở vị trí 0, và có các cây táo ở vị trí trên trên tọa độ. Ban đầu bạn có thể chọn qua trái hoặc phải tùy ý. Sau đó đi, gặp cây nào hái hết táo cây đó và đi ngược lại. Hỏi số táo tối đa tìm được là bao nhiêu ?

Lời giải: Bài này ta sử dụng sắp xếp và một chút suy luận để xác định sang trái hay sang phải cho phù hợp là xong

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. vector<pair<ll,ll> > v1,v2;
  5. int main(){
  6. ll n;
  7. cin>>n;
  8. ll i;
  9. for(i=0;i<n;i++){
  10. ll u,v;
  11. cin>>u>>v;
  12. if(u<0) v1.push_back({u,v});
  13. else v2.push_back({u,v});
  14. }
  15. sort(v1.rbegin(),v1.rend());
  16. sort(v2.begin(),v2.end());
  17. ll res=0;
  18. if(v1.size()==v2.size()){
  19. for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
  20. cout<<res;
  21. return 0;
  22. }
  23. if(v1.size()>v2.size()){
  24. for(i=0;i<v2.size();i++) res=res+v1[i].second+v2[i].second;
  25. res=res+v1[v2.size()].second;
  26. cout<<res;
  27. return 0;
  28. }
  29. if(v1.size()<v2.size()){
  30. for(i=0;i<v1.size();i++) res=res+v1[i].second+v2[i].second;
  31. res=res+v2[v1.size()].second;
  32. cout<<res;
  33. return 0;
  34. }
  35. }

Cho hai số X,Y chỉ gồm các kí tự 4 và 7. Ở mỗi phép toán, hoặc ta lấy hai vị trí bất kì để hoán đổi cho nhau, hoặc biến đổi kí tự này thành kí tự kia. Hỏi ta cần ít nhất bao nhiêu phép toán để biến x thành y

 Đề bài: $\href{https://codeforces.com/problemset/problem/145/A}{Đây}$

Tóm tắt:Cho hai số X,Y chỉ gồm các kí tự 4 và 7. Ở mỗi phép toán, hoặc ta lấy hai vị trí bất kì để hoán đổi cho nhau, hoặc biến đổi kí tự này thành kí tự kia. Hỏi ta cần ít nhất bao nhiêu phép toán để biến x thành y

Lời giải: Gọi số cặp (4,7) là first, và (7,4) là second. Khi đó đáp án là max(first,second)

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. string x,y;
  6. cin>>x>>y;
  7. ll fi=0,se=0;
  8. ll i;
  9. for(i=0;i<x.size();i++){
  10. if(x[i]=='4'&&y[i]=='7') fi++;
  11. else if(x[i]=='7'&&y[i]=='4') se++;
  12. }
  13. ll res=max(fi,se);
  14. cout<<res;
  15. return 0;
  16. }

Cho hai số X,Y ở hai cơ số khác nhau. So sánh hai số đó

Đề bài: $\href{https://codeforces.com/problemset/problem/602/A}{Đây}$ 

Tóm tắt: Cho hai số X,Y ở hai cơ số khác nhau. So sánh hai số đó

Lời giải: Bài này thuần cài đặt, các bạn có thể xem source

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n,k;
  6. cin>>n>>k;
  7. ll a[n];
  8. ll i;
  9. for(i=0;i<n;i++) cin>>a[i];
  10. ll dem=0, product=1;
  11. ll res1=0;
  12. while(dem<n){
  13. res1=res1+product*a[n-1-dem];
  14. dem++;
  15. product*=k;
  16. }
  17. /**/
  18. ll n1,k1;
  19. cin>>n1>>k1;
  20. ll a1[n1];
  21. ll i1;
  22. for(i1=0;i1<n1;i1++) cin>>a1[i1];
  23. ll dem1=0, product1=1;
  24. ll res11=0;
  25. while(dem1<n1){
  26. res11=res11+product1*a1[n1-1-dem1];
  27. dem1++;
  28. product1*=k1;
  29. }
  30. if(res1==res11){cout<<"=";return 0;}
  31. if(res1>res11){cout<<">";return 0;}
  32. cout<<"<";
  33. return 0;
  34. }

Cho một đa giác đều n cạnh, và có cách nối đặc biệt. Đếm xem có bao nhiêu miền được tạo ra từ cách nối trên ?

Đề bài: $\href{https://codeforces.com/problemset/problem/592/B}{Đây}$

 Tóm tắt: Cho một đa giác đều n cạnh, và có cách nối đặc biệt. Đếm xem có bao nhiêu miền được tạo ra từ cách nối trên ?



Lời giải: Đáp án của bài toán là : $(n-2)^2$

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n;
  6. cin>>n;
  7. ll res = (n-2)*(n-2);
  8. cout<<res;
  9. return 0;
  10. }

Chủ Nhật, 29 tháng 11, 2020

Một số gọi là may mắn khi số đó chỉ chứa số 4 hoặc 7. Sắp xếp tất cả các số may mắn theo thứ tự. Nhập từ bàn phím 1 số may mắn, hãy in ra chỉ số của số đó

Đề bài: $\href{https://codeforces.com/problemset/problem/535/B}{Đây}$

 Tóm tắt: Một số gọi là may mắn khi số đó chỉ chứa số 4 hoặc 7. Sắp xếp tất cả các số may mắn theo thứ tự. Nhập từ bàn phím 1 số may mắn, hãy in ra chỉ số của số đó (chỉ số bắt đầu từ 1)

Lời giải: Đây là kĩ thuật bitmask khá quen thuộc , ta ánh xạ số 4 cho 0 và số 7 cho 1 , từ đó ta sinh tất cả các trường hợp và duyệt là xong. Các bạn có thể xem source tại đây

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. ll po(ll a, ll n){
  5. ll res=a,ans=1;
  6. while(n){
  7. if(n&1) ans=ans*res;
  8. res=res*res;
  9. n/=2;
  10. }
  11. return ans;
  12. }
  13. int main(){
  14. string s;
  15. cin>>s;
  16. string res;
  17. ll i,j;
  18. ll len = s.size();
  19. for(i=0;i<(1<<len);i++){
  20. res="";
  21. for(j=0;j<len;j++){
  22. if((i>>j)&1==1) res=res+'7'; else res=res+'4';
  23. }
  24. reverse(res.begin(),res.end());
  25. if(res==s){
  26. ll ans = po(2,len)-2;
  27. ans = ans +(i+1);
  28. cout<<ans;
  29. return 0;
  30. }
  31. }
  32. return 0;
  33. }

Cho một mảng gồm n phần tử và có cấp số cộng là k. Tìm u0 sao cho tổng các phần tử của dãy cấp số cộng xuất phát từ u0 là nhỏ nhất

 Đề bài:$\href{https://codeforces.com/problemset/problem/366/B}{Đây}$ 

Tóm tắt: Cho một mảng gồm n phần tử và có cấp số cộng là k. Tìm u0 sao cho tổng các phần tử của dãy cấp số cộng xuất phát từ u0 là nhỏ nhất

Lời giải: Bài này thuộc dạng impletation thuần. Các bạn có thể xem source trực tiếp

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. vector<pair<ll,ll> > v;
  5. int main(){
  6. ll n,k;
  7. cin>>n>>k;
  8. ll a[n];
  9. ll i;
  10. for(i=0;i<n;i++) cin>>a[i];
  11. for(i=0;i<k;i++){
  12. ll tmp=i;
  13. ll sum=0;
  14. while(tmp<n){
  15. sum=sum+a[tmp];
  16. tmp+=k;
  17. }
  18. v.push_back({sum,i});
  19. }
  20. sort(v.begin(),v.end());
  21. cout<<v[0].second+1;
  22. }

Cho n điểm trên tọa độ Oxy, tìm diện tích hình vuông nhỏ nhất chứa tất cả các điểm đó (các điểm có thể nằm bên trong hoặc trên biên)

 Đề bài: $\href{https://codeforces.com/problemset/problem/485/B}{Đây}$

Tóm tắt: Cho n điểm trên tọa độ Oxy, tìm diện tích hình vuông nhỏ nhất chứa tất cả các điểm đó (các điểm có thể nằm bên trong hoặc trên biên)

Lời giải: Chiếu các điểm đó lần lượt trên Ox, Oy ta lần lượt xác định được giới hạn của các điểm đó, từ đó tìm ra được độ dài tối thiểu của hình vuông.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define inf 1000000000000000000
  5. ll maaxX,miinX,maaxY,miinY;
  6. struct cap{
  7. ll x;
  8. ll y;
  9. };
  10. int main(){
  11. maaxX=maaxY=-inf;
  12. miinX=miinY=inf;
  13. ll n;
  14. cin>>n;
  15. cap a[n];
  16. ll i;
  17. for(i=0;i<n;i++){
  18. cin>>a[i].x>>a[i].y;
  19. maaxX = max(maaxX,a[i].x);
  20. maaxY = max(maaxY,a[i].y);
  21. miinX=min(miinX,a[i].x);
  22. miinY=min(miinY,a[i].y);
  23. }
  24. ll res;
  25. res=max((ll)(maaxX-miinX),(ll)(maaxY-miinY));
  26. res=res*res;
  27. cout<<res;
  28. return 0;
  29. }

Cho một mảng gồm n phần tử, chọn 2 phần tử i,j sao cho xi>xj và lấy xi=xi-xj, cho đến khi tất cả các phần tử bằng nhau, sau đó tính tổng lại. In ra tổng đó

Đề bài: $\href{https://codeforces.com/problemset/problem/389/A}{Đây}$

 Tóm tắt:Cho một mảng gồm n phần tử, chọn 2 phần tử i,j sao cho xi>xj và lấy xi=xi-xj, cho đến khi tất cả các phần tử bằng nhau, sau đó tính tổng lại. In ra tổng đó

Lời giải: Bài này hay, ta sử dụng ước chung lớn nhất của n số là xong

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n;
  6. cin>>n;
  7. ll i;
  8. ll a[n];
  9. for(i=0;i<n;i++) cin>>a[i];
  10. ll res=a[0];
  11. for(i=0;i<n;i++) res=__gcd(res,a[i]);
  12. res=res*n;
  13. cout<<res;
  14. return 0;
  15. }

Cho một list ánh xạ từ các kí tự +,-,<,>,,,. thành các dãy nhị phân, Và sau đó tính chuỗi đó mod 10^6+3

Đề bài: $\href{https://codeforces.com/problemset/problem/133/B}{Đây}$

 Tóm tắt:Cho một list ánh xạ từ các kí tự +,-,<,>,,,. thành các dãy nhị phân, Và sau đó tính chuỗi đó mod 10^6+3

Lời giải: Bài này chỉ cần sử dụng mod, và lũy thừa nhị phân

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mod 1000003
  5. map<string,string> mt;
  6. ll po(ll a,ll n){
  7. ll res=a,ans=1;
  8. while(n){
  9. if(n&1) ans=ans*res%mod;
  10. res=res*res%mod;
  11. n/=2;
  12. }
  13. return ans;
  14. }
  15. void init(){
  16. mt[">"]="1000";
  17. mt["<"]="1001";
  18. mt["+"]="1010";
  19. mt["-"]="1011";
  20. mt["."]="1100";
  21. mt[","]="1101";
  22. mt["["]="1110";
  23. mt["]"]="1111";
  24. }
  25. int main(){
  26. init();
  27. string s;
  28. cin>>s;
  29. string res="";
  30. ll i;
  31. for(i=0;i<s.size();i++) {
  32. string tmp="";
  33. tmp = tmp+s[i];
  34. res=res+mt[tmp];
  35. }
  36. ll ans=0;
  37. reverse(res.begin(),res.end());
  38. for(i=0;i<res.size();i++){
  39. if(res[i]=='1') ans=(ans+po(2,i))%mod;
  40. }
  41. cout<<ans;
  42. return 0;
  43. }

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...