网络广告的特点,佛山企业网站优化,对网站做打包备份处理,外贸行业网站推广题目大意
有一个排列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an#xff0c;我们现在进行如下操作#xff1a;
for(int i1;in-m1;i) sort(ai,aim);设最后的结果为 b 1 , b 2 , ⋯ , b n b_1,b_2,\cdots,b_n b1,b2,⋯,bn#xff0c;求满足条件的…题目大意
有一个排列 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an我们现在进行如下操作
for(int i1;in-m1;i) sort(ai,aim);设最后的结果为 b 1 , b 2 , ⋯ , b n b_1,b_2,\cdots,b_n b1,b2,⋯,bn求满足条件的 a a a中字典序第 k k k小的 a a a。 1 ≤ n ≤ 1 0 6 , m ≤ n , 1 ≤ k ≤ 1 0 18 1\leq n\leq 10^6,m\leq n,1\leq k\leq 10^{18} 1≤n≤106,m≤n,1≤k≤1018 b i b_i bi是 1 1 1到 n n n的一个排列。 题解
由题意可得 b i b_i bi是 a 1 , a 2 , … , a min ( i m − 1 , n ) a_1,a_2,\dots,a_{\min(im-1,n)} a1,a2,…,amin(im−1,n)中满足不在 b 1 , b 2 , … , b i − 1 b_1,b_2,\dots,b_{i-1} b1,b2,…,bi−1中的最小的数。
那么当 b i − 1 b i b_{i-1}b_i bi−1bi就一定有 a i m − 1 b i a_{im-1}b_i aim−1bi。
把这些已经确定的 b i b_i bi去掉剩下的问题等价于 n n n变小 m , k m,k m,k不变 b i i b_ii bii的子问题。
下面我们假设 b i i b_ii bii。
考虑从小到大将每一个 i i i填入 a a a中易得 i i i需要填在 [ 1 , min ( i m − 1 , n ) ] [1,\min(im-1,n)] [1,min(im−1,n)]中任意没填过的位置那么填 i i i的方案数为 min ( m , n − i 1 ) \min(m,n-i1) min(m,n−i1)。
然而因为方案数很大而 k k k相对没那么大所以 a a a有一个前缀都满足 a i i a_ii aii。
设 f i f_i fi表示满足上面条件的前缀为 n − i n-i n−i也就是后面有最多 i i i个数不满足那么 f i f i − 1 × min ( m , i ) f_if_{i-1}\times \min(m,i) fifi−1×min(m,i)
当 m 1 m1 m1时显然只有一个答案。因为保证有解这种情况下 k 1 k1 k1。
当 m 1 m1 m1时 f i ≥ 2 i − 1 f_i\geq 2^{i-1} fi≥2i−1可得 f 62 ≥ k f_{62}\geq k f62≥k
那么我们只需取最后 min ( n , 62 ) \min(n,62) min(n,62)个位置后面用一个状压维护状态再枚举每一位填什么即可。细节见代码。
时间复杂度为 O ( n v 3 ) O(nv^3) O(nv3)其中 v min ( n , 62 ) v\min(n,62) vmin(n,62)。
code
#includebits/stdc.h
using namespace std;
int n,m,a[1000005],b[1000005],c[1000005],num[1000005],z[1000005];
long long k;
long long gt(int t,int w,long long now){long long re1;for(int i1;it;i){if((nowi-1)1){if(rek/(min(im-1,t)-w)1) return k1;rere*(min(im-1,t)-w);if(rek) return k1;w;}}return re;
}
void dd(int l,int t){long long now(1llt)-1;for(int i1;il-t;i) c[i]num[i];for(int it;i1;i--){for(int j1;jt;j){if((nowj-1)1){long long vtgt(t,t-i1,now^(1llj-1));if(kvt) k-vt;else{c[l-i1]num[l-tj];now^(1llj-1);break;}}}}
}
int main()
{scanf(%d%d%lld,n,m,k);--k;for(int i1;in;i){scanf(%d,b[i]);}int lstb[1],cnt0;for(int i2;in;i){if(lstb[i]){a[im-1]b[i];z[b[i]]1;}else lstb[i];}for(int i1;in;i){if(!z[i]) num[cnt]i;}dd(cnt,min(cnt,62));int now1;for(int i1;in;i){if(!a[i]){a[i]c[now];now;}printf(%d ,a[i]);}return 0;
}
