题目
AT_agc012_c [AGC012C] Tautonym Puzzle
题目描述
当字符串 $ x $ 满足以下条件时,称 $ x $ 为好字符串。
- 条件:$ x $ 可以表示为某个长度不少于 $ 1 $ 的字符串 $ y $ 重复两次所得的字符串 $ yy $。
例如,aa
、bubobubo
等是好字符串,而空字符串、a
、abcabcabc
、abba
等都不是好字符串。
“ワシ”与猫头鹰设计了关于好字符串的谜题。请找出一个满足下列条件的字符串 $ s $。在本题的约束条件下,一定存在这样的字符串。
- $ 1\leq |s|\leq 200 $
- $ s $ 仅由用 $ 1 $ 至 $ 100 $ 的整数表示的 $ 100 $ 种字符构成。
- $ s $ 的 $ 2^{|s|} $ 个子序列中,成为好字符串的子序列有 $ N $ 个。
题目分析
这显然是一道构造题目,高质量的构造题目。
我们注意到填什么似乎并不重要,重要的是种类不同。
因此有 \(200\) 个位置,我们先用 \(100\) 个位置从左到右依次放置 \(1,\dots,100\)。
我们考虑后半部分怎么与前面的匹配出 \(n\) 个合法的。
首先考虑一个最大的 \(k\) 使得 \(2^k-1\leq n\),将 \(n\) 分为 \(2^k-1\) 和 \(rest=n-2^k+1\) 两个部分进行计算。
第一个部分,我们可以只需要按顺序放置 \(k\) 个数就可以了,至于是什么得看第二个部分。
对于第二个部分,我们试图将其与 \(rest\) 的二进制扯上关系,如果说第 \(x\) 位(从后往前,从 \(0\) 开始)为 \(1\),我们希望多产生 \(2^x\) 的贡献,怎么弄呢?
要产生 \(2^x\) 的贡献其中一个方法就是当前在末尾放置一个数 \(a\),使得前面比它小的数有 \(x\) 个即可。
这个的方法不同,其中一种比较简单的方法是:前面直接放置偶数就可以了(\(\{2,4,6,\dots\}\)),然后后面补充奇数,比如说对于 \(rest=(101)_2\),得到后半部分的序列的第二部分为:\(\{5,1\}\)。
注意遍历的时候要从高位开始遍历,否则小奇数对大奇数也有可能产生贡献。
真是一道好题!
代码
时间复杂度 \(\mathcal{O}(len)\),其中 \(len\) 为最后答案的长度。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
// #define N
using namespace std;
int n;
vector<int> ans;
signed main(){cin >> n;// cout << 200 << '\n';// for (int i = 1;i <= 100;i ++) cout << i << ' ';for (int i = 1;i <= 100;i ++) ans.push_back(i);int k = 0;for (;(1ll << k + 1) - 1ll <= n;k ++);for (int i = 1;i <= k;i ++) ans.push_back(i * 2);int rest = n - (1ll << k) + 1ll;for (int i = k - 1;i >= 0;i --)if ((rest >> i) & 1) ans.push_back(i * 2 + 1);cout << ans.size() << '\n';for (auto i : ans) cout << i << ' ';return 0;
}