{ }codelper
拼接构建字符串P0095

数字带的片段

第一行给出整数 n 和 w,第二行给出询问数 q,第三行给出 q 个片段编号。
把 1 到 n 的数依次不加空格地连起来,得到一条长长的数字带(n = 12 时为 "123456789101112")。
从头开始把这条带每 w 个字符剪成一段,从前往后称为第 1 段、第 2 段……最后一段可以少于 w 个字符。
按询问顺序,每行输出一个被询问的片段。

输入
1 ≤ n ≤ 1,000,000,1 ≤ w ≤ 100,1 ≤ q ≤ 100,片段编号在 1 到片段数之间(同一编号可以多次询问)
输出
每个询问输出一行该片段
样例 1 · stdin
12 5
3
3 1 2
stdout
01112
12345
67891
样例 2 · stdin
10 4
1
3
stdout
910
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写?查看各语言题解 · 8 种语言题解

n 为一百万时这条带约有 590 万个字符,拼接的方法对速度影响很大。
Java String 和 C# string 是不可变的,每次 s += x 都会新建一个复制了之前全部字符的字符串。
在循环里这样写是 O(n²),会超时,所以要用 StringBuilder 的 append/Append 收集。
Python 字符串也是不可变的。
CPython 有让 += 变快的优化,但语言并不保证,所以标准做法是收集片段后用 "".join(...) 一次连接。
JS/TS 引擎(V8)在内部把片段链接起来处理 +=,所以很快;收集到数组再 join("") 也可以。
C++ std::string 的 += 是在末尾追加,很快,但 s = s + x 每次都会复制。
C 没有字符串类型。
strcat 每次都要从头找字符串的结尾,同样是 O(n²)。
用 sprintf 返回的字符数记住结尾位置,直接写在那里。
片段编号从 1 开始,所以第 k 段从第 (k - 1) * w 个字符(从 0 数)开始。
Craykon 用 ribbon += i 把数接到字符串后面(运行在 JS 上,所以很快),用 ribbon.截取(开始, 个数) 剪出片段。

Pythonmain.py · 8 行
n, w = map(int, input().split())q = int(input())ks = list(map(int, input().split()))# 조각을 목록에 모았다가 join 한 번으로 잇는다ribbon = "".join(str(i) for i in range(1, n + 1))for k in ks:    start = (k - 1) * w    print(ribbon[start:start + w])
JavaScriptmain.js · 7 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, w] = lines[0].trim().split(/\s+/).map(Number);const ks = lines[2].trim().split(/\s+/).map(Number);const parts = [];for (let i = 1; i <= n; i++) parts.push(i);const ribbon = parts.join("");console.log(ks.map((k) => ribbon.slice((k - 1) * w, k * w)).join("\n"));
TypeScriptmain.ts · 8 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, w]: number[] = lines[0].trim().split(/\s+/).map(Number);const ks: number[] = lines[2].trim().split(/\s+/).map(Number);const parts: number[] = [];for (let i = 1; i <= n; i++) parts.push(i);const ribbon: string = parts.join("");console.log(ks.map((k) => ribbon.slice((k - 1) * w, k * w)).join("\n"));
JavaMain.java · 19 行
import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int w = sc.nextInt();        int q = sc.nextInt();        // String += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다        StringBuilder ribbon = new StringBuilder();        for (int i = 1; i <= n; i++) ribbon.append(i);        StringBuilder out = new StringBuilder();        for (int j = 0; j < q; j++) {            int start = (sc.nextInt() - 1) * w;            out.append(ribbon, start, Math.min(start + w, ribbon.length())).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 21 行
using System;using System.Text; class Program{    static void Main()    {        string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(t[0]), w = int.Parse(t[1]);        Console.ReadLine();        // string += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다        var ribbon = new StringBuilder();        for (int i = 1; i <= n; i++) ribbon.Append(i);        string s = ribbon.ToString();        foreach (string k in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries))        {            int start = (int.Parse(k) - 1) * w;            Console.WriteLine(s.Substring(start, Math.Min(w, s.Length - start)));        }    }}
C++main.cpp · 14 行
#include <iostream>#include <string> int main() {    int n, w, q, k;    std::cin >> n >> w >> q;    // std::string의 += 는 뒤에 덧붙인다(용량을 넉넉히 늘려 가서 빠르다)    std::string ribbon;    for (int i = 1; i <= n; i++) ribbon += std::to_string(i);    for (int j = 0; j < q; j++) {        std::cin >> k;        std::cout << ribbon.substr(static_cast<std::size_t>(k - 1) * w, w) << '\n';    }}
Cmain.c · 18 行
#include <stdio.h> static char ribbon[6000000]; int main(void) {    int n, w, q, k;    scanf("%d %d %d", &n, &w, &q);    // 끝 자리(len)를 기억하며 그 뒤에 바로 쓴다 — strcat은 매번 처음부터 끝을 찾는다    int len = 0;    for (int i = 1; i <= n; i++) len += sprintf(ribbon + len, "%d", i);    for (int j = 0; j < q; j++) {        scanf("%d", &k);        int start = (k - 1) * w;        int count = len - start < w ? len - start : w;        printf("%.*s\n", count, ribbon + start);    }    return 0;}
Craykonmain.cray · 15 行
t = 控制台.读数字();n = t[0];w = t[1];q = 控制台.读行().转数字();ks = 控制台.读数字();ribbon = "";循环 (i = 1; i <= n; i++){    ribbon += i;}遍历 (k 在 ks){    start = (k - 1) * w;    控制台.输出(ribbon.截取(start, 数学.较小值(w, ribbon.长度 - start)));}