1 条题解

  • 0
    @ 2026-11-15 19:21:48

    题目分析

    测试点 1~5

    考虑最简单的暴力,具体操作略。

    测试点 6~9

    考虑预处理出 kk 次操作中每次操作后新产生的数,即对于每个 [ai,ai+1][a_i,a_{i+1}] 操作 kk 次并开桶统计。

    本来的时间复杂度 O(n⋅2k+q)O(n\cdot 2^k+q),但是注意到有重复情况,其实跑不满 6060 次,时间复杂度 O(max⁡i=1nai+q)O(\max_{i=1}^na_i+q)。

    测试点 10~12

    考虑预处理出 kk 次操作中每次操作后新产生的数,即对于每个 [ai,ai+1][a_i,a_{i+1}] 操作 kk 次并开桶统计。

    时间复杂度 O(n⋅2k+q)O(n\cdot 2^k+q)。

    测试点 13~20

    发现可以划归为如下子问题:

    给定 a=[0,c]a=[0,c],判断对于 xx,几次“过渡”后才会出现。

    容易发现进行拆位,每次判断 x,c2x,\dfrac c2 的大小关系,累加答案。每次比较后问题被缩小一倍,划归即可。

    这样复杂度是 O(q(log⁡n+log⁡max⁡1≤i<l{ai+1−ai})O(q(\log n+\log\max_{1\le i<l}\{a_{i+1}-a_i\}) 的。可以通过。

    当然考虑更普适的情况,发现 xx 能在第 kk 次后出现,当且仅当 ∃p∈Z+\exists p\in\textbf Z^+,使得 x=⌊p⋅c2k⌋x=\left\lfloor\dfrac{p\cdot c}{2^k}\right\rfloor。

    于是迅速做到 O(1)O(1) 单次判断。但是因为会出现 1018×101810^{18}\times 10^{18},会溢出,所以不采用。(写高精应该是可以的,但没必要)

    E

    能够证明逆序对个数不会超过 200200 个。

    f[i][j]f[i][j] 表示长度为 ii 的排列中,逆序对个数为 jj 的排列有多少个,可以利用 DP + 前缀和在 O(200n)O(200n) 的时间复杂度内计算。

    根据 f[i][j]f[i][j] 可以计算出排名第 kk 小的排列有多少个逆序对。

    然后从第一位逐位开始确定,假设已经确定了前 xx 位,我们可以知道前 xx 个数字内部之间的逆序对个数,和前xx 个和后 n−xn-x 个数字之间的逆序对个数,从而推出后 n−xn-x 个数字内部之间的逆序对个数,这个方案数可以利用f[i][j]f[i][j] 快速计算出,时间复杂度为 O(200n)O(200n),如果实现的不精细会退化到 O(n2)O(n^2)。

    #include <bits/stdc++.h>
    #define fst first
    #define snd second
    #define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
    #define pb push_back
    #define ALL(s) s.begin(),s.end()
    #define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
    #define SZ(s) int(s.size())
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> ii;
    
    const int MAXN=2e5+10;
    vector<ll> dp[MAXN];
    ll INF=4e18;
    
    ll solve(int n, int rem){
    	if(!n) return rem==0;
    	
    	if(rem>=SZ(dp[n])) dp[n].resize(rem+1,-1);
    	ll &r=dp[n][rem];
    	if(r>=0)return r;
    	r=0;
    	
    	//poner el i-esimo ahora
    	fore(i,0,min(n,rem+1)){
    		r=min(INF, r+solve(n-1,rem-i));
    		if(r==INF)break;
    	}
    	
    	return r;
    }
    
    int main(){FIN;
    	int n; ll k; cin>>n>>k;
    	
    	int rem=0;
    	while(solve(n,rem)<k) k-=solve(n,rem),rem++;
    	vector<int> ans;
    	
    	vector<int> v(n);
    	fore(i,0,n) v[i]=n-i-1;
    	
    	while(n){
    		fore(i,0,min(n,rem+1)){
    			if(solve(n-1,rem-i)<k) k-=solve(n-1,rem-i);
    			else{
    				ans.pb(v[SZ(v)-i-1]);
    				v.erase(v.end()-i-1);
    				n--;
    				rem-=i;
    				break;
    			}
    		}
    	}
    	
    	for(auto x:ans)cout<<x+1<<" ";cout<<"\n";
    }
    • 1

    信息

    ID
    175
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者