Thứ Tư, 2 tháng 12, 2020

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ự bất kỳ sao cho số lượng cặp $a_i<a_i+1$ lớn nhất có thể

Lời giải: Đây là bài sử dụng map đặc trưng, từ đó ta thu được mảng cần tìm

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. vector<ll> v;
  5. map<ll,ll> mt;
  6. int main(){
  7. ll n;
  8. cin>>n;
  9. ll i;
  10. for(i=0;i<n;i++){
  11. ll x;
  12. cin>>x;
  13. mt[x]++;
  14. }
  15. ll res=0;
  16. for(auto p: mt){
  17. res=max(res,p.second);
  18. }
  19. for(ll z=0;z<res;z++){
  20. for(auto p: mt){
  21. if(p.second!=0) {v.push_back(p.first); mt[p.first]--;}
  22. else continue;
  23. }
  24. }
  25. ll ans=0;
  26. for(i=1;i<v.size();i++)
  27. if(v[i]>v[i-1]) ans++;
  28. cout<<ans;
  29. return 0;
  30. }

Cho n thẻ bài có dạng (a_i,b_i). Ban đầu ta bốc một thẻ bất kì, khi đó số điểm sẽ được cộng thêm a_i và ta sẽ có quyền bốc thêm b_i cái thẻ nữa. Tìm số điểm tối đa mà ta có thể thu được

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

 Tóm tắt:Cho n thẻ bài có dạng (a_i,b_i). Ban đầu ta bốc một thẻ bất kì, khi đó số điểm sẽ được cộng thêm a_i và ta sẽ có quyền bốc thêm b_i cái thẻ nữa. Tìm số điểm tối đa mà ta có thể thu được

Lời giải: Bài này ta chỉ việc sắp xếp lại và sau đó cộng tổng là xong

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. struct cap{
  5. ll a,b;
  6. };
  7. bool cmp(cap x, cap y){
  8. if(x.b==y.b) return x.a>y.a;
  9. return x.b>y.b;
  10. }
  11. int main(){
  12. ll n;
  13. cin>>n;
  14. cap oke[n];
  15. ll i;
  16. for(i=0;i<n;i++){
  17. cin>>oke[i].a>>oke[i].b;
  18. }
  19. sort(oke,oke+n,cmp);
  20. ll res=0;
  21. for(i=0;i<n;i++){
  22. res=res+oke[i].b;
  23. }
  24. res=min(n,res+1);
  25. ll ans=0;
  26. for(i=0;i<res;i++){
  27. ans=ans+oke[i].a;
  28. }
  29. cout<<ans;
  30. return 0;
  31. }

Cho 6 cái que. Biết rằng con gấu và con voi tạo từ 4 que giống nhau để làm chân, 1 que để làm đầu, 1 que để làm thân. Đối với con gấu, que đầu phải ngắn hơn quen thân, còn con voi sao cũng được. Hãy in ra 6 que trên có thể tạo thành con gì. Nếu không tạo thành được con gì in ra Alien

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

Tóm tắt:Cho 6 cái que. Biết rằng con gấu và con voi tạo từ 4 que giống nhau để làm chân, 1 que để làm đầu, 1 que để làm thân. Đối với con gấu, que đầu phải ngắn hơn quen thân, còn con voi sao cũng được. Hãy in ra 6 que trên có thể tạo thành con gì. Nếu không tạo thành được con gì in ra Alien 

Lời giải: Đây là bài thuần cài đặt, nhưng đòi hỏi ta phải cần thận.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. map<ll,ll> mt;
  5. int main(){
  6. ll i,x;
  7. for(i=0;i<6;i++){
  8. cin>>x;
  9. mt[x]++;
  10. }
  11. if(mt.size()==1){
  12. cout<<"Elephant";
  13. return 0;
  14. }
  15. if(mt.size()==3){
  16. for(auto p: mt){
  17. if(p.second==4){
  18. cout<<"Bear";
  19. return 0;
  20. }
  21. }
  22. }
  23. if(mt.size()==2){
  24. for(auto p: mt){
  25. if(p.second==4){
  26. cout<<"Elephant";
  27. return 0;
  28. }
  29. if(p.second==5){
  30. cout<<"Bear";
  31. return 0;
  32. }
  33. }
  34. }
  35. cout<<"Alien";
  36. return 0;
  37. }

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ả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ự...