给你一个 k,要你构造一个长度不超过 90 的排列,使得这个排列的递增子序列个数恰好为 k。
思路首先我们考虑构造出它至少要能到它的大小,那怎么增大的最快呢?
就直接按顺序,然后每次是
2
0
,
2
1
,
2
2
,
.
.
.
2^0,2^1,2^2,...
20,21,22,...。
那你会发现你可以依此得到一个
2
u
2^u
2u(
u
u
u 是
k
k
k 的最高位),不过要再加一个
1
1
1。
(不过你会发现因为空串也算,但是你没有算上,所以不用加)
然后你会发现后面就是可以类似二进制拆分的搞,从而得到
91.36
91.36
91.36。
接着就卡住了。。。
当然有一些神奇的随机化做法可以弄过去,但这里说一个从一个大佬的题解中看到的优美做法。
你观察为什么会卡,因为你是
2
log
k
2\log k
2logk 的次数,而
log
k
≈
60
\log k\approx 60
logk≈60,答案是
90
90
90,它是
log
k
\log k
logk 的一点五倍!
这启发我们用一些方法来优化常数。
自然前面的那
log
k
\log k
logk 个无法优化,那我们考虑把后面的
log
k
\log k
logk 减少一半。
怎么减少一半呢?你会发现如果你前面凑了两个位置,你可以通过一种方法使得后面两个连续的
1
1
1 只需要放一次!
如图,这两个的个数其实是一样的,因为你第二个图右边的那个点除了跟后面上面的黑点正常贡献,它可以有三种(自己,前面带上第一个红点,前面带上第二个红点)
那就是乘
3
3
3,亦或者说是给自己的前面加了一个
1
1
1!
先看看这样能优化的个数,前面
1
,
1
1,1
1,1 占了两个,如果那后面如果不是连续的
1
1
1,那说明这个位置
1
1
1 只占了一半,可以正常弄,如果两个
1
1
1 我们就压缩到
1
1
1 个,优化了一半。
所以是刚好优化了一半的!
那我们就可以用这种方法来搞,然后接下来讲讲具体的:
那我们先从高位往低位跑一次,得到那些位置值正常弄,那些位置压缩弄。
然后我们接着考虑怎么排位置,就根据上面的第二张图来看:
首先黑色点都是大于红色点,直接把最大的排上去。
接着我们考虑怎么搞,因为我们要保证每个合并点前面要恰好有两个比它小的,这从高位往低位不再好搞,我们考虑从低位往高位搞。
然后因为你从低位往高位搞,构造出来是从右往左的,所以你要把你构造出来的序列最后翻转一下。
那继续想怎么弄,你考虑数是越来越大的,然后如果你要弄新合并点,你就预先留出两个位置给非合并点放,这两个位置是小的。
如果合并点后面又是合并点,那其实没有必要再弄,继续用哪个非合并点,然后大小比前面的非合并点大(因为你从后往前)即可。
那我们可以这样实现,我们一直给新合并点找两个位置,如果有普通点来了就占一个位置,新的位置再找。
然后如果来了合并点我们已经找好了,就不用再找,直接用下一个位置。
然后我们记录就弄两个指针指着普通点当前放在哪里,合并点当前放在哪里。
然后搞就可以啦,如果还是不知道可以看看代码的实现。
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N = 101;
int a[N];
bool in[N];
vector<int> construct_permutation(long long k) {
vector <int> re, A, B;
int tot = 0;
ll tk = k; while (tk) a[tot++] = tk & 1, tk >>= 1;
int cnt = 0;
for (int i = tot - 2; i >= 0; i--) {
if (a[i]) {
if (cnt < 2 || !i || !a[i - 1]) {
cnt++; A.push_back(i); a[i] = 0;
}
else {
B.push_back(i - 1); a[i] = a[i - 1] = 0;
}
}
}
int p0 = 0, p1 = 0, num0 = 0, sum = tot - 1 + A.size() + B.size();
for (int i = 0; i < A.size() + B.size(); i++) in[i] = 0;
while (num0 < 2) if (!in[++p1]) num0++;
for (int i = 0; i < tot - 1; i++) {
if (!A.empty() && A.back() == i) {
re.push_back(p0); A.pop_back();
num0--; in[p0] = 1;
while (in[p0]) p0++;
while (num0 < 2) if (!in[++p1]) num0++;
}
if (!B.empty() && B.back() == i) {
re.push_back(p1); B.pop_back(); in[p1] = 1;
while (in[p1]) p1++;
}
re.push_back(--sum);
}
reverse(re.begin(), re.end());
return re;
}
/*
#include
#include
static long long MX=1e18;
static bool check_permutation(vector v)
{
sort(v.begin(),v.end());
for(int i=0;i& v) {
vector dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
dp[x+1] = min(dp[x+1],MX+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,MX+1);
}
return result;
}
int main() {
int t;
assert(1 == scanf("%d", &t));
while(t--)
{
long long k;
assert(1 == scanf("%lld",&k));
vector ret=construct_permutation(k);
// for (int i = 0; i < ret.size(); i++) printf("%d ", ret[i]); printf("\n");
if(!check_permutation(ret))
{
printf("WA: Returned array is not a permutation\n");
exit(0);
}
long long inc=count_increasing(ret);
if(inc!=k)
{
if(inc==MX+1)
printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
else
printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
exit(0);
}
printf("%d\n",(int)ret.size());
for(int i=0;i
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)