诗

[题目链接](https://www.nowcoder.com/practice/7eef94e6f96f401b9078213cbc6c7eaf)

思路

模拟题。按照规则将字符串分行：第 1 行取 1 个字符，第 2 行取 2 个字符，第 3 行取 3 个字符……每行的首字母位置依次是 $0, 1, 1+2, 1+2+3, \ldots$ ，即第 $k$ 行（从 1 开始）的首字母下标为 $\frac{k(k-1)}{2}$ 。

只需用一个指针 pos 从 0 开始，每次取 s[pos] 加入答案，然后 pos += k（k 从 1 递增），直到 pos 超出字符串长度。

时间复杂度 $O(\sqrt{n})$ （行数约为 $\sqrt{2n}$ ），空间复杂度 $O(\sqrt{n})$ 。

代码

C++
Java

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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    string ans;
    int pos = 0, k = 1;
    while (pos < n) {
        ans += s[pos];
        pos += k;
        k++;
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        StringBuilder ans = new StringBuilder();
        int pos = 0, k = 1;
        while (pos < n) {
            ans.append(s.charAt(pos));
            pos += k;
            k++;
        }
        System.out.println(ans.toString());
    }
}