1 条题解
-
0
题目分析
测试点 1~5
考虑最简单的暴力,具体操作略。
测试点 6~9
考虑预处理出 次操作中每次操作后新产生的数,即对于每个 操作 次并开桶统计。
本来的时间复杂度 ,但是注意到有重复情况,其实跑不满 次,时间复杂度 。
测试点 10~12
考虑预处理出 次操作中每次操作后新产生的数,即对于每个 操作 次并开桶统计。
时间复杂度 。
测试点 13~20
发现可以划归为如下子问题:
给定 ,判断对于 ,几次“过渡”后才会出现。
容易发现进行拆位,每次判断 的大小关系,累加答案。每次比较后问题被缩小一倍,划归即可。
这样复杂度是 的。可以通过。
当然考虑更普适的情况,发现 能在第 次后出现,当且仅当 ,使得 。
于是迅速做到 单次判断。但是因为会出现 ,会溢出,所以不采用。(写高精应该是可以的,但没必要)
E
能够证明逆序对个数不会超过 个。
表示长度为 的排列中,逆序对个数为 的排列有多少个,可以利用 DP + 前缀和在 的时间复杂度内计算。
根据 可以计算出排名第 小的排列有多少个逆序对。
然后从第一位逐位开始确定,假设已经确定了前 位,我们可以知道前 个数字内部之间的逆序对个数,和前 个和后 个数字之间的逆序对个数,从而推出后 个数字内部之间的逆序对个数,这个方案数可以利用 快速计算出,时间复杂度为 ,如果实现的不精细会退化到 。
#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
- 上传者