第一行给出整数 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
错误列表00F8 ↓ · ⇧F8 ↑
输入(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"));
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;}