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

发表评论

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

你是机器人吗? =。= *