精品课程网站建设情况,微信自创小程序,佛山网站建设费用,推广公司经营范围正题
题目链接:https://jzoj.net/senior/#contest/show/3017/0 题目大意
长度为2n2^n2n的序列#xff0c;nnn个操作#xff0c;第iii个可以将序列划分为2i2^i2i段后交换其中两段#xff0c;每个操作只能用一次#xff0c;求有多少种操作可以使得序列有小到大。 解题思路 …正题
题目链接:https://jzoj.net/senior/#contest/show/3017/0 题目大意
长度为2n2^n2n的序列nnn个操作第iii个可以将序列划分为2i2^i2i段后交换其中两段每个操作只能用一次求有多少种操作可以使得序列有小到大。 解题思路
每个操作只能一次操作顺序不会影响结果所以可以假设从小到大操作做到第iii个操作时每个可以被交换的段都必须是已经交换好的。
那么假设现在交换的段长度xxx那么每段2x2x2x的最多只有两个不按顺序否则无解所以我们搜索一下就好了
时间复杂度O(2nn)O(2^nn)O(2nn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N14;
ll n,l,ans,a[1N],fac[N];
void dfs(ll dep,ll f){if(depn){ansfac[f];return;}ll len1dep,hlen/2,z0,w[4];for(ll i1;il;ilen){if(a[ih]!a[i]h) w[z]i;if(z2){return;}}if(!z)dfs(dep1,f);if(z1){if(a[w[1]]a[w[1]h]h){for(ll iw[1];iw[1]h;i)swap(a[i],a[ih]);dfs(dep1,f1);for(ll iw[1];iw[1]h;i)swap(a[i],a[ih]);}}if(z2){if(a[w[1]]ha[w[2]]a[w[1]h]ha[w[2]h]){for(ll i0;ih;i)swap(a[w[1]hi],a[w[2]i]);dfs(dep1,f1);for(ll i0;ih;i)swap(a[w[1]hi],a[w[2]i]);}if(a[w[2]]ha[w[1]h]a[w[1]]ha[w[2]h]){for(ll i0;ih;i)swap(a[w[1]i],a[w[2]i]);dfs(dep1,f1);for(ll i0;ih;i)swap(a[w[1]i],a[w[2]i]);}if(a[w[1]]ha[w[2]h]a[w[2]]ha[w[1]h]){for(ll i0;ih;i)swap(a[w[1]hi],a[w[2]hi]);dfs(dep1,f1);for(ll i0;ih;i)swap(a[w[1]hi],a[w[2]hi]);}if(a[w[2]h]ha[w[1]h]a[w[2]]ha[w[1]]){for(ll i0;ih;i)swap(a[w[1]i],a[w[2]hi]);dfs(dep1,f1);for(ll i0;ih;i)swap(a[w[1]i],a[w[2]hi]);}}
}
int main()
{scanf(%lld,n);l1n;fac[0]1;for(ll i1;in;i)fac[i]fac[i-1]*i;for(ll i1;il;i)scanf(%lld,a[i]);dfs(1,0);printf(%lld,ans);
}
