1. 题目

传送门= ̄ω ̄=

题目描述

我们称一个字符串 $x$是好的,当且仅当它满足下列条件:
条件:$x$可以被表示为连续两个相同的非空串 $y$首尾相连
例如,’aa’ 和’bubobubo’ 是好的;但是空串,’a’,’abcabcabc‘和’abba’ 都不是好的。
Eagle 和 Owl 提出了关于好串的问题。请找出一个串 s 使得其满足下述条件:
1. $1≤|s|≤200$
2. $s$的每一个字符都是 $1$到 $100$之间的整数
3. $s$的 $2^{|s|}$个子串中,有恰好 $N$个是好串

输入格式

一个整数 $N$。

输出格式

第一行,一个整数表示 $s$的长度。

第二行,用空格隔开的若干个整数,描述字符串 $s$。

样例

样例输入 1

7

样例输出 1

4
1 1 1 1

样例输入 2

299

样例输出 2

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

数据范围与提示

$1≤N≤10^{12}$

2. 题解

QAQ 初赛考完了来道构造题压压惊.jpg

首先可以想到对于 $n=1$的询问答案是 $1, 1$

设 $f(s)$表示字符串 $s$的 “好” 子串个数。

然后可以构造出如下性质:

(其中 $c$为一个 $X, Y$内都未出现过的字符,$X,Y$分别是两个字符串)

$f(c + X + Y + c) = f(X + Y) + 1$
$f(c + X + c + Y) = 2 \times f(X + Y) + 1$

(备注一下第二个性质的 $+1$是因为 $c$除了和 $X,Y$组合还能组成一个 $c, c$,即 $X,Y$都选择空串)

对于询问 $x$:

  • $x$为奇数:转化为询问 $\frac {x – 1} 2$(即第二条性质)
  • $x$为偶数:转化为询问 $x – 1$(即第一条性质),然后询问就成了奇数

然后就能倍增了是吧。。。

这样构造出来的结果长度为 $O(log _ 2 n)$,复杂度也是 $O(log _ 2 n)$的,真美妙= ̄ω ̄=

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n, num;

list<int> L, R;

void Work(LL a)
{
    if (!a) return;
    if (a & 1) Work(a >> 1), L.push_front(++num), R.push_front(num);
    else Work(a - 1), L.push_front(++num), R.push_back(num);
}

int main(int argc, char const* argv[])
{
    scanf("%lld", &n), Work(n);
    printf("%lu\n", L.size() + R.size());
    for (list<int>::iterator i = L.begin(); i != L.end(); i++) printf("%d ", *i);
    for (list<int>::iterator i = R.begin(); i != R.end(); i++) printf("%d ", *i);
    putchar(10);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注