[找规律][逆序数][思维] UVa1620 Lazy Susan

自己看看了半天都找不到规律,倒是感觉和逆序数应该有关系,但是直接按照偶序列有解奇序列无解来算wa,因为按照我原来的理解是,偶序列4个反转一定还是偶序列,奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件,那就是这个是个环,所以他从任意一个地方开始都可以,这就相当于在原来的4个翻转的变换的基础上多了一种变换:把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话,相当于做了i*j次变换,其中i是分界点前一段的个数,j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段,则相乘之后仍然是奇数,等于说这时候是可以从奇序列变成偶序列的;而当n为奇数的时候,i和j必定一奇一偶,这时候相乘必定为偶数,无法变换序列的奇偶性。所以,只有当序列为奇序列且n为奇数的时候才无解,其他情况均有解,因为均可以变换为偶序列。

#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;

int a[505],n;
int t[1100];

void change(int x,int p)
{
    while(x<=n)
    {
        t[x]+=p;
        x+= (x&(-x));
    }
    return ;
}

int sum(int k)
{
    int ans=0;
    while(k>0)
    {
        ans+=t[k];
        k-=(k&(-k));
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(t,0,sizeof(t));
        int ans=0;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=n;i>=1;i--)
        {
            change(a[i],1);
            ans+=sum(a[i]-1);
        }
        if((ans&1)&&(n&1))
        {
            cout<<"impossible\n";
        }
        else
            cout<<"possible\n";
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据