排序

内存限制：128 MiB 时间限制：1000 ms 标准输入输出

题目描述

输入格式

数据范围与提示

对于30%的数据，1<=N<=4；对于全部的数据，1<=N<=12。

一群数论题中出了一个搜索。

甚至我考试时一点也不会。

自己算复杂度比较大然后交上去只跑了90ms。

这也太

不多说了。

引理1

当前可以将原数列变成排序的操作，其每一种其他排列都可以将原序列变成排序。

证明不太好证，举几个例子

例如 3 4 2 1这个序列可以经过操作1 操作2 变成 1 2 3 4

那么显然先进行操作2 再进行操作1 也可以变成 1 2 3 4

于是推而广之（数学归纳）用cnt次操作可以达到目的，那么所有符合的方案数为cnt!

这样通过引理1 可以剪很多枝

我们从小到大枚举每一种方案，每次验证符合，若符合ans+cnt！就完了

引理2

假设枚举到第i个方案设划分序列为区间长度为1<<(i+1)的序列，如果有三个及以上不符合递增且相连的区间，那么这个序列没救了。

这个我们可以验证

首先我们保证如果我们进行到第i个方案那么所有长度1<<i的序列都符合递增且相连

如果有一个长度1<<(i+1)不是递增且相连的区间，我们把它划分成两个1<<i,i<<i的序列，我们直接用第i种操作（可能）就行了

然后如果有两个长度那么把它划分成四个，然后也（可能）行

但如果有三个及以上我们最多保证经过i操作后，两个序列符合条件

所以得证

然后搜就完了

以下是本人丑陋的代码

#include<bits/stdc++.h>

#define ll long long

#define A 1000000

using namespace std;

ll xx[A],a[A],b[A],ans,n;

ll read()

{

        ll x=0,f=1;char ch=getchar();

        while(!isdigit(ch)){

                if(ch=='-') f=-1;

                ch=getchar();

        }

        while(isdigit(ch)){

                x=x*10+ch-'0';

                ch=getchar();

        }

        return f*x;

}

void SWAP(ll x,ll k,ll len)

{

        for(ll i=x,j=k;len;len--,i++,j++)

                swap(a[i],a[j]);

}

bool check(ll l,ll r)

{

        for(ll i=l;i<r;i++)

                if(a[i]+1!=a[i+1])

                        return 0;

        return 1;

}

void shuchu()

{

        for(ll i=1;i<=(1<<n);i++)

                cout<<a[i]<<"";

        cout<<endl;

}

void dfs(ll k,ll cnt)

{

//        shuchu();

//        cout<<k<<endl;

        if(k==n)

        {

                ans+=xx[cnt];

                return ;

        }

        ll now=(1<<(k+1)),x=(1<<k),b[5],tot=0;

        for(ll i=1;i<=(1<<n);i+=now)

        {

//                printf("检查i=%lld j=%lld\n",i,i+now-1);

                if(!check(i,i+now-1))

                {

                        b[++tot]=i;

                        if(tot==3) return ;

                }

        }

//        cout<<"tot="<<tot<<"x="<<x<<"now="<<now<<endl;

//        for(ll i=1;i<=n;i++)

//        {

//

//        }

        if(tot==0) {dfs(k+1,cnt);return ;}

        if(tot==1)

        {

                SWAP(b[1],b[1]+x,x);

                if(check(b[1],b[1]+x)) dfs(k+1,cnt+1);

                SWAP(b[1],b[1]+x,x);

        }

        if(tot==2)

        {

                SWAP(b[1],b[2],x);

                if(check(b[1],b[1]+x)&&check(b[2],b[2]+x)) dfs(k+1,cnt+1);

                SWAP(b[1],b[2],x);

                SWAP(b[1]+x,b[2],x);

                if(check(b[1],b[1]+x)&&check(b[2],b[2]+x)) dfs(k+1,cnt+1);

                SWAP(b[1]+x,b[2],x);

                SWAP(b[1],b[2]+x,x);

                if(check(b[1],b[1]+x)&&check(b[2],b[2]+x)) dfs(k+1,cnt+1);

                SWAP(b[1],b[2]+x,x);

                SWAP(b[1]+x,b[2]+x,x);

                if(check(b[1],b[1]+x)&&check(b[2],b[2]+x)) dfs(k+1,cnt+1);

                SWAP(b[1]+x,b[2]+x,x);

        }

//        shuchu();

}

int main()

{

        n=read();xx[0]=1;

        for(ll i=1;i<=(1<<n);i++) a[i]=read();

        for(ll i=1;i<=n;i++) xx[i]=xx[i-1]*i;

        dfs(0,0);

        cout<<ans<<endl;

}

划艇

有点难。

至少对于我来说有点难。弱的我在loj交了5页wa 才AC。

不多说了。

https://blog.csdn.net/qq_22541499/article/details/51674707

https://www.cnblogs.com/hzoi-DeepinC/p/11158757.html#4298030

https://www.cnblogs.com/heoitys/p/11166727.html

这三篇博客已经讲的很清楚了。

所以我鸽掉了

必须写出来，填掉这个这个坑，要不这个题就白做了。

首先这个题必须离散化，肯定开不了这么大的数组。

我们把区间离散化一下，把每段区间设置成左开右闭（或者左闭右开）的，把每个区间出现次序处理出来，左右端点处理出来，区间长度处理出来，

注意这里区间不可以设置成左闭右闭的，因为如果这样设置会出现重复枚举，前面这段区间会枚举最右面这个端点，后面这个区间会枚举最左面这个区间。

然后思考这个题肯定要dp

说明f数组含义。

设$f[i][j]$表示第i个学校选择第j个区间中某一个数

思考会被什么转移

首先如果前面所有学校都没有选择j之后的区间（要么没选要么选择了j之前的区间），那么这个区间可以选择任何一个数。

$\sum\limits_{l=1}^{i-1}\sum\limits_{r=1}^{j-1} f[l][r]*C_{len}^{1}$

然后如果前面有学校同样选择了j这个区间

先假设前面选择这个区间的学校为k

那么对当前这个区间的贡献即为

$\sum\limits_{l=1}^{k-1}\sum\limits_{r=1}^{j-1} f[l][r]$*（k～i之间一堆方案数）

$\sum\limits_{l=1}^{k-1}\sum\limits_{r=1}^{j-1} f[l][r]$$\sum\limits_{l=1}^{i-1}\sum\limits_{r=1}^{j-1} f[l][r]*C_{len}^{1}$这两个式子都可以用前缀和进行维护

那么我们现在要做的就是求出来（k～i之间一堆方案数）

剩下的明天写

巴特西

NOIP模拟测试2「排列（搜索）·APIO划艇」

排序

题目描述

输入格式

数据范围与提示

划艇

最新文章

热门文章

巴特西

NOIP模拟测试2「排列 （搜索）·APIO划艇」

排序

题目描述

输入格式

数据范围与提示

划艇

最新文章

热门文章

NOIP模拟测试2「排列（搜索）·APIO划艇」