Hướng dẫn cho Nhà Kho Hai Tầng

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: nguyenducleminh02

Lời giải – Nhà Kho Hai Tầng

Ý tưởng

Ta có thể thực hiện phép hoán đổi giữa a[i] và a[2i]. Nếu xem mỗi vị trí là một đỉnh và nối cạnh giữa i và 2i thì các vị trí sẽ tạo thành nhiều thành phần liên thông.

Trong cùng một thành phần, ta có thể hoán đổi nhiều lần nên các phần tử trong đó có thể đổi chỗ tự do với nhau. Vì vậy để dãy có thể sắp xếp tăng dần thì trong mỗi thành phần liên thông, tập giá trị phải trùng với tập chỉ số của thành phần đó.

Cách kiểm tra: với mỗi component, lấy tất cả chỉ số và các giá trị tại các vị trí đó, sắp xếp hai danh sách rồi so sánh. Nếu khác nhau thì không thể sắp xếp dãy.

Độ phức tạp

Mỗi phần tử được duyệt một lần và mỗi component được sắp xếp.

Time complexity: O(n log n)
Memory complexity: O(n)

Code C++

```cpp

include <bits/stdc++.h>

using namespace std;

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin >> t;
while(t--){
    int n;
    cin >> n;

    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];

    vector<int> vis(n+1,0);
    bool ok = true;

    for(int i=1;i<=n;i++){
        if(vis[i]) continue;

        vector<int> idx;
        queue<int> q;

        q.push(i);
        vis[i] = 1;

        while(!q.empty()){
            int u = q.front();
            q.pop();
            idx.push_back(u);

            if(u*2<=n && !vis[u*2]){
                vis[u*2]=1;
                q.push(u*2);
            }
            if(u%2==0 && !vis[u/2]){
                vis[u/2]=1;
                q.push(u/2);
            }
        }

        vector<int> val;
        for(int x:idx) val.push_back(a[x]);

        sort(idx.begin(),idx.end());
        sort(val.begin(),val.end());

        if(idx!=val){
            ok=false;
            break;
        }
    }

    cout<<(ok?"YES":"NO")<<"\n";
}

}

Bình luận (1)

Tải bình luận...