【SDOI2015】bzoj3990 排序

2020-12-13 06:06

阅读：388

标签：etc oid char img ott label 条件 ges lld

A. 排序

题目描述

技术图片

输入格式

技术图片

输出格式

一行，一个整数，表示可以将数组A从小到大排序的不同的操作序列的个数。

样例

样例输入

3
7 8 5 6 1 2 4 3

样例输出

数据范围与提示

对于30%的数据，1

一个伪装成计数题的大搜索…

首先要知道一个结论：对于一个操作序列，如果他是合法的，那么他的全排列都是合法的，所以从小到大搜索，同时记录操作数k。

对于第x次操作，把序列分成2^x-1段，暴力搜索有几段不满足a[i]=a[i-1]+1(注意这里并不只是要求满足递增)，如果大于两段，显然无解;

如果没有，则第x操作无需进行（即对答案无贡献），直接向下递归即可，因为如果此时进行第x次操作，会将顺序打乱，之后的操作并不能使之还原。

如果有1段，则将这一段从中间断开，暴力交换，如果仍不满足则无解，满足则继续向下递归，k++;

如果有2端，则有四种情况，暴力交换向下递归即可，注意回溯时要还原。

结束条件：a[i]=i，答案为k！（即A（k，k））;

不过这题看起来复杂度好高啊，居然能跑的这么快…

#include
#include
#include
#define LL long long
using namespace std;
int n,m=1;
int a[5010];
LL jc[15];

bool end()
{
	for(int i=1;i2)return 0;
	if(!pd)return dfs(x+1,k);
	if(pd==1)
	{	
		int l=(d1-1)*len+1,r=(d1)*len;bool pp=0;LL res=0;
		swapp(l,(l+r)>>1,(l+r)/2+1,r);
		for(int i=l+1;i1,(l+r)/2+1,r);
		return res;
	}
	if(pd==2)
	{
		int l1=(d1-1)*len+1,r1=(d1)*len,l2=(d2-1)*len+1,r2=(d2)*len;
		int mid1=(l1+r1)>>1,mid2=(l2+r2)>>1;		
		LL res=0;
		swapp(l1,mid1,l2,mid2);
		{
			int pp=0;
			for(int i=l1+1;i‘9‘)a=getchar();
	while(a>=‘0‘&&a

【SDOI2015】bzoj3990 排序

标签：etc oid char img ott label 条件 ges lld

原文地址：https://www.cnblogs.com/Al-Ca/p/11166533.html

上一篇：出现ImportError: No module named win32api异常

下一篇：windows的路由例子

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【SDOI2015】bzoj3990 排序
文章链接：http://soscw.com/essay/32437.html

亲，登录后才可以留言！

【SDOI2015】bzoj3990 排序

A. 排序

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

评论

热门文章

推荐文章

最新文章

置顶文章