UVA - 1620 Lazy Susan（逆序数）

题目：

把1~n(n≤500)放到一个圆盘里，每个数恰好出现一次。每次可以选4个连续的数字翻转顺序。问能不能变成1.2.3....n的顺序。

思路：

这样的题的规律真的是一点都不好推，看了网上的博客知道只有n为奇数且给出的序列的逆序数为奇数的时候，这种情况下是不能完成的，其余的情况都可以。

如果n为偶数，那么在这个环中总有4个连续的数字的逆序数是偶数，假设4个数的逆序数是x，翻转之后逆序数变成了6-x（为什么是6-x自己还没有搞懂），逆序数的变化为6-2x为偶数。最后升序的逆序数是0为偶数。根据偶数+(-)偶数=偶数,奇数+(-)偶数=奇数，可以得知当序列的逆序数为偶数时，那就可以通过翻转是逆序数变为0.

代码：

树状数组求逆序数

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1e3

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int maxn = ;

int a[maxn],n,tree[maxn];

int lowbit(int x){

    return x&(-x);

}

void add(int x){

    while(x<=n){

        tree[x]++;

        x += lowbit(x);

    }

}

int getSum(int x){

    int res = ;

    while(x>){

        res+=tree[x];

        x -= lowbit(x);

    }

    return res;

}

int main(){

    //FRE();

    int kase;

    scanf("%d",&kase);

    while(kase--){

        memset(tree,,sizeof(tree));

        scanf("%d",&n);

        int cnt = ;

        for(int i=; i<n; i++){

            scanf("%d",&a[i]);

            add(a[i]);

            cnt += i+-getSum(a[i]);

        }

        if(cnt%== && n%==){

            printf("impossible\n");

        }else{

            printf("possible\n");

        }

    }

    return ;

}

暴力求逆序数

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1e3

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int maxn = ;

int a[maxn],n;

int main(){

    int kase;

    scanf("%d",&kase);

    while(kase--){

        scanf("%d",&n);

        for(int i=; i<n; i++){

            scanf("%d",&a[i]);

        }

        int cnt = ;

        for(int i=; i<n; i++){

            for(int j=; j<i; j++){

                if(a[j]>a[i]){

                    cnt++;

                }

            }

        }

        if(cnt%== && n%==){

            printf("impossible\n");

        }else{

            printf("possible\n");

        }

    }

    return ;

}

巴特西

UVA - 1620 Lazy Susan（逆序数）

最新文章

热门文章