专栏文章

CF2157H

xxujindong_
CF2157H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min11u6x
此快照首次捕获于
2025/12/01 18:49
3 个月前
此快照最后确认于
2025/12/01 18:49
3 个月前
查看原文
下面为了方便操作，把条件改成先降后升，最后反过来。
考虑一个增量法。在排列后面加一个 pn+1=n+1p_{n+1}=n+1，也就是加一个自环，让 (n,m)(n,m) 变成 (n+1,m+1)(n+1,m+1)。如果 p1=np_1=n，我们可以往环里塞一个单点，也就是令 p1=n+1,pn+1=np_1=n+1,p_{n+1}=n，让 (n,m)(n,m) 变成 (n+1,m)(n+1,m)。
这启示我们用一个增量法，先跑出较小的 nn 的 20002000 组构造再拓展。取 n=18n=18，不超过这个值的 O(n2n)O(n2^n) 暴力。这是因为当 n=19,m≤9n=19,m\leq9 时都有超过 20002000 组构造。
若 n>18,n−m≥10n>18,n-m\geq10，我们从 (19,i)(19,i) 开始拓展。若 n−m≤18n-m\leq 18，我们从 (19,19−(n−m))(19,19-(n-m)) 开始加入自环即可。否则从 (19,1)(19,1) 开始拓展，因为这是一个大环，有 p1=19p_1=19，否则 p19=19p_{19}=19 就有至少两个环。先往大环里塞若干个单点，然后再塞自环即可。
若 n>18,n−m≤9n>18,n-m\leq9，首先排列中至少有 n−2(n−m)n-2(n-m) 个不动点。我们注意到，p1∼p1p_{1\sim p_1} 之间最多有一个不动点。否则，设第一个不动点是 pi=ip_i=i，则排列的谷在 pip_i 之前，而 2∼i−12\sim i-1 内没有足够的位置把 1∼i−11\sim i-1 的数填完。因此 p1≤2(n−m)+1p_1\leq2(n-m)+1，整个排列只有 p1∼p1p_{1\sim p_1} 是乱的，其他都是不动点。因此我们只需要对前 2(n−m)+12(n-m)+1 个位置暴力即可。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int> >ans;
void solve(int n,int m){
  for(int i=0;i<1<<n&&ans.size()<2000;i+=2){
    vector<int>p;
    for(int j=n-1;j>=0;j--)if(i>>j&1)p.push_back(j);
    for(int j=0;j<n;j++)if(~i>>j&1)p.push_back(j);
    int cyc=0;
    bool vis[n]={0};
    for(int j=0;j<n;j++){
      if(vis[j])continue;
      cyc++,vis[j]=1;
      for(int k=p[j];k!=j;k=p[k])vis[k]=1;
    }
    if(cyc==m)ans.push_back(p);
  }
}
int main(){
  cin>>n>>m;
  if(n<=18)solve(n,m);
  else if(n-m<=9){
    solve(2*(n-m)+1,n-m+1);
    for(int i=0;i<ans.size();i++)while(ans[i].size()<n)ans[i].push_back(ans[i].size());
  }
  else{
    solve(19,max(19-n+m,1));
    for(int i=0;i<ans.size();i++){
      while(ans[i].size()<n)ans[i].push_back(ans[i].size());
      if(n-m>=19){
        ans[i][0]=n-m;
        for(int j=19;j<=n-m;j++)ans[i][j]--;
      }
    }
  }
  cout<<ans.size()<<'\n';
  for(int i=0;i<ans.size();i++)for(int j=n-1;j>=0;j--)cout<<n-ans[i][j]<<(j?' ':'\n');
  return 0;
}
一个有趣的事情是，如果写一个爆搜，优先往后面放，过程中算一下最终置换环数的上下界剪枝，发现直接过了。这是因为当 nn 大的时候，排列后面是一段 pi=i−1p_i=i-1 接一段 pi=ip_i=i，搜的时候我们先尝试往右边填一个 pi=ip_i=i，然后往左边填一个数后尝试 pi=i−1p_i=i-1，所以可以很快搜出来。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,p[105];
bool vis[105];
ostringstream ans;
void dfs(int l,int r){
  if(cnt>=2000)return;
  int cyc=0;
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++){
    if(!p[i]||vis[i])continue;
    int pos=p[i];
    vis[i]=i;
    while(pos&&pos!=i)vis[pos]=i,pos=p[pos];
    cyc+=pos==i;
  }
  if(cyc+min(r-l+1,1)>m||cyc+r-l+1<m)return;
  if(l>r){
    cnt++;
    for(int i=1;i<=n;i++)ans<<p[i]<<(i==n?'\n':' ');
    return;
  }
  p[l]=n-r+l,dfs(l+1,r),p[l]=0;
  if(l<r)p[r]=n-r+l,dfs(l,r-1),p[r]=0;
}
int main(){
  return cin>>n>>m,dfs(1,n),cout<<cnt<<'\n'<<ans.str()<<'\n',0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...