渚千夏的串 C++/C

Question

**渚千夏的串
_时间限制 : 1.000 sec 内存限制 : 128 MB ** _

题目描述
我们定义一个 01 串的权值，是其子序列为 01 的个数。
先给定权值 m ，试构造一个合法的 01 串使其权值为 m 且长度在 10^5 以内。
01 串即字符集仅包含 0,1 的字符串。
注意:序列 a 是字符串 b 的子序列，当且仅当 a 可以通过删除 b 中的若干(可能为零或全部)元素得到。例如：对于串 01011，字符串 1011,111 都是它的子序列。
输入
输入包含一个正整数 m (0≤m≤10^9) ，代表 01 子序列的个数。
输入数据保证有解。
输出
输出第一行，包含一个正整数 n (1≤n≤10^5)，表示 01 串的长度。
输出第二行，包含一个长为 n 的 01 串。
样例输入 Copy
【样例输入1】
2
【样例输入2】
5
样例输出 Copy
【样例输出1】
3
001
【样例输出2】
6
010001

Answer 1

让【宝码香车】来帮你解答，本回答参考DeepSeek编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

---

问题分析

我们需要构造一个01串，使得其子序列为“01”的个数等于给定的权值 m。子序列“01”的个数可以通过统计每个 0 后面有多少个 1 来计算。

构造思路

1. 基本构造：假设我们有一个 0，后面跟着 k 个 1，那么子序列“01”的个数就是 k。因此，如果我们有 m 个 1 跟在 0 后面，那么子序列“01”的个数就是 m。

2. 优化长度：为了减少字符串的长度，我们可以将多个 0 和 1 组合起来。例如，如果我们有 a 个 0 和 b 个 1，那么子序列“01”的个数就是 a * b。因此，我们可以通过选择适当的 a 和 b 来满足 a * b = m。

3. 最小化长度：为了最小化字符串的长度，我们可以选择 a 和 b 使得 a + b 最小。这可以通过选择 a 为 m 的最大因数来实现。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m;
    cin >> m;

    // 找到m的最大因数a，使得a * b = m，且a + b最小
    int a = 1;
    for (int i = 1; i * i <= m; ++i) {
        if (m % i == 0) {
            a = i;
        }
    }
    int b = m / a;

    // 构造01串：a个0，b个1
    string s(a, '0');
    s += string(b, '1');

    // 输出结果
    cout << s.size() << endl;
    cout << s << endl;

    return 0;
}

代码解释

1. 输入处理：读取输入的 m。
2. 因数分解：找到 m 的最大因数 a，使得 a * b = m，并且 a + b 最小。
3. 构造01串：构造一个包含 a 个 0 和 b 个 1 的字符串。
4. 输出结果：输出字符串的长度和字符串本身。

样例解释

• 样例输入1：2

  • a = 1, b = 2
  • 构造的字符串为 011，长度为 3。
  • 输出：

    3
    011
    

• 样例输入2：5

  • a = 1, b = 5
  • 构造的字符串为 011111，长度为 6。
  • 输出：

    6
    011111
    

复杂度分析

• 时间复杂度：O(sqrt(m))，因为我们需要遍历到 sqrt(m) 来找到最大因数。
• 空间复杂度：O(1)，除了输入输出外，只使用了常数空间。

这个解法能够在给定的时间和空间限制内完成题目要求。