题解 P3322 [SDOI2015]排序
2021/5/23 18:29:25
本文主要是介绍题解 P3322 [SDOI2015]排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题解
仔细审题,我们会发现
小 \(A\) 认为两个操作序列不同,当且仅当操作个数不同,或者至少一个操作不同(种类不同或者操作位置不同)。
所以,对于一种操作,不管是交换哪两段,都算作同一种操作,只会对答案贡献一次。
引理
对于一个合法的操作序列,其中的操作可以互换位置,仍为合法序列。
可以自己手动模拟一下,结论很显然。
那么对于每一次操作,设此次操作的长度为 \(len=2^x\),我们将从头开始每 \(len\) 的长度分为一个块,则有 \(2^{n-x}\) 个块。
对于每一个块,我们要保证他是一个合法的有序序列,又因为 \(2^x\) 是由 \(2^{x-1}\) 的块调整顺序转移而来的,那么对于每个 \(2^{x-1}\) 的块,我们就要找出有多少个两两的块不符合顺序递增。如果有超过两对不合理,则我们可以直接判定此分支下无解,
原因就是对于每种操作,我们只能用一次。
当到边界时且合法时,我们需要加上用到的操作数的阶乘。(原因见引理)
\(AC \kern 0.5emCODE:\)
#include<bits/stdc++.h> #define ri register int #define p(i) ++i using namespace std; namespace IO{ char buf[1<<21],*p1=buf,*p2=buf; inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} inline int read() { ri x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();} return x*f; } } using IO::read; namespace nanfeng{ static const int N=12; int num[(1<<N)+7],p[N+7],n, ans; inline void Swap(int i,int j,int k) { int len=1<<k,si=(i-1)*len,sj=(j-1)*len; for (ri l(1);l<=len;p(l)) swap(num[si+l],num[sj+l]); } inline int check(int x) {//用于判断交换后的块是否符合要求顺序递增 int len=1<<x; for (ri i(1);i<=(1<<n-x);i+=2) if (num[i*len]+1!=num[i*len+1]) return 0; return 1; } inline void dfs(int x,int cnt) { if (x&&!check(x-1)) return; if (x==n) {ans+=p[cnt];return;} dfs(x+1,cnt); ri ch[5],tot=0,len=1<<x;//一定不要设成全局数组,因为若要定义为全局,向下递归时分支会将他改变,之后回溯时会炸。 for (ri i(1);i<=(1<<n-x);i+=2) { if (num[i*len]+1!=num[i*len+1]) { if (tot==4) return; ch[p(tot)]=i;ch[p(tot)]=i+1; } } if (!tot) return; for (ri i(1);i<=tot;p(i)) { for (ri j(i+1);j<=tot;p(j)) { // if ((i+j==3||i+j==7)&&tot==4) continue; Swap(ch[i],ch[j],x); dfs(x+1,cnt+1); Swap(ch[i],ch[j],x);//记得回溯 } } } inline int main() { // freopen("1.in","r",stdin); n=read(); p[1]=1; for (ri i(2);i<=12;p(i)) p[i]=p[i-1]*i; for (ri i(1);i<=(1<<n);p(i)) num[i]=read(); dfs(0,0); printf("%d\n",ans); return 0; } } int main() {return nanfeng::main();}
目前是洛谷最优解,而且这么写码量也很小。
这篇关于题解 P3322 [SDOI2015]排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)