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. }

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