仓库的传送带上原来有 n 个贴着号码牌的箱子排成一列。 机器人依次做了 q 项作业，现在只剩下作业记录和全部作业做完之后的队列。 位置按做该项作业时的队列计数，最前面的箱子算作 1。 S i j 是把第 i 个箱子和第 j 个箱子对调的作业。 M i j 是把第 i 个箱子取出（后面的箱子各向前挪一格），再把它插回去，使它成为新队列的第 j 个的作业。 L k 是把最前面的箱子取下放到最后面，做 k 次的作业。 F i j 是把第 i 个到第 j 个箱子原地倒过来的作业。 第一行给出 n 和 q。 第二行给出全部作业做完之后的队列，从最前面的箱子起共 n 个号码牌。 接下来 q 行每行一项作业，按机器人做的顺序给出。 最后一行给出整数 t。 一行中的值用一个空格隔开。 第一行输出做第 t 项作业之前那一刻的队列，第二行输出做第一项作业之前的最初队列。 队列从最前面的箱子起写出号码牌，用一个空格隔开。 把记录从最后一项作业到第一项作业倒着走一遍，每项作业都做一次还原即可。
输入
1 ≤ n ≤ 1,000。 1 ≤ q ≤ 2,000。 号码牌是 1 到 1,000,000 的整数（只给出数字，不带逗号），同一个号码牌可能出现多次。 S 和 M 满足 1 ≤ i ≤ n，1 ≤ j ≤ n（i 和 j 可以相同）。 F 满足 1 ≤ i ≤ j ≤ n。 L 满足 1 ≤ k ≤ n。 1 ≤ t ≤ q
输出
两行。 第一行是第 t 项作业之前的队列，第二行是最初的队列（各 n 个号码牌）
样例 1 · stdin
5 4
30 20 50 10 40
M 1 4
L 2
S 1 5
F 2 4
3
stdout
40 10 50 20 30
10 20 30 40 50
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
倒着走的循环各语言写法不同。 Python 是 for idx in range(q - 1, -1, -1)，终点值不包含在内，所以要走到 0 号就把终点写成 -1。 写成 range(q - 1, 0, -1) 会漏掉第一项作业。 JS・TS・Java・C#・C・C++ 写 for (int idx = q - 1; idx >= 0; idx--)，Craykon 写 循环 (idx = q - 1; idx >= 0; idx--)。 把起点写成 q、条件写成 idx > 0，就会读到不存在的 q 号而漏掉 0 号。 在 C・C++ 中如果下标是 unsigned 或 size_t，0 减 1 会变成一个很大的数，idx >= 0 永远为真，循环不会结束，会读到数组外面。 这时 C++ 的 ops.at(idx) 会抛出异常而停下，但 ops[idx] 或 C 数组会发生什么是没有定义的。 也可以先把列表反过来再从前往后走。 Python 的 reversed(ops) 返回一个倒着走的对象，但 ops.reverse() 是原地反转并返回 None，所以 for op in ops.reverse() 是 TypeError。 JS 的 ops.reverse() 原地反转并返回这个数组本身。 C++ 可以从 rbegin() 走到 rend()。 只把顺序倒过来还不够，每项作业都要做相反的事。 在样例中从前往后还原记录，会得到错误的最初队列 20 30 10 40 50。 S 和 F 再做一次就还原了，但 M i j 要从第 j 个取出再插到第 i 个（Python row.insert(i - 1, row.pop(j - 1))，Craykon 按位置移除 和 插入），L k 要把最后 k 个拿到最前面（Python row[n - k:] + row[:n - k]，Java Collections.rotate(row, k)，C++ std::rotate）。 最后，“第 t 项作业之前”就是刚还原完第 t 项作业的时候。 从 0 数这项作业是 t - 1 号，所以在 idx == t - 1 时输出。 在 idx == t 时输出得到的是做完第 t 项作业之后的队列，而且 t 等于 q 时这一行根本不会出现。
Pythonmain.py · 28 行
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())row = lines[1].split()ops = [lines[2 + i].split() for i in range(q)]t = int(lines[2 + q])out = []# 마지막 작업부터 첫 작업까지 거꾸로: range의 끝 -1은 들어가지 않으므로 0번까지 돈다for idx in range(q - 1, -1, -1): op = ops[idx] a = int(op[1]) if op[0] == "S": # 맞바꾸기는 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1], row[b - 1] = row[b - 1], row[a - 1] elif op[0] == "M": # i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = int(op[2]) row.insert(a - 1, row.pop(b - 1)) elif op[0] == "L": # 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row[n - a:] + row[:n - a] else: # F: 뒤집기도 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1:b] = row[a - 1:b][::-1] if idx == t - 1: # t번 작업을 되돌린 직후 = t번 작업을 하기 직전 out.append(" ".join(row))out.append(" ".join(row))print("\n".join(out))
JavaScriptmain.js · 29 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row = lines[1].trim().split(/\s+/);const ops = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t = Number(lines[2 + q]);const out = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 31 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row: string[] = lines[1].trim().split(/\s+/);const ops: string[][] = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t: number = Number(lines[2 + q]);const out: string[] = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
JavaMain.java · 42 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] head = in.readLine().trim().split("\\s+"); int n = Integer.parseInt(head[0]), q = Integer.parseInt(head[1]); List<String> row = new ArrayList<>(Arrays.asList(in.readLine().trim().split("\\s+"))); String[][] ops = new String[q][]; for (int i = 0; i < q; i++) ops[i] = in.readLine().trim().split("\\s+"); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { String[] op = ops[idx]; int a = Integer.parseInt(op[1]); switch (op[0]) { case "S": Collections.swap(row, a - 1, Integer.parseInt(op[2]) - 1); break; case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 row.add(a - 1, row.remove(Integer.parseInt(op[2]) - 1)); break; case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 Collections.rotate(row, a); break; default: Collections.reverse(row.subList(a - 1, Integer.parseInt(op[2]))); } if (idx == t - 1) out.append(String.join(" ", row)).append('\n'); // t번 작업을 하기 직전 } out.append(String.join(" ", row)).append('\n'); System.out.print(out); }}
C#Main.cs · 57 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); var row = new List<string>(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)); var ops = new string[q][]; for (int i = 0; i < q; i++) ops[i] = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int t = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { string[] op = ops[idx]; int a = int.Parse(op[1]); switch (op[0]) { case "S": { int b = int.Parse(op[2]); (row[a - 1], row[b - 1]) = (row[b - 1], row[a - 1]); break; } case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 { int b = int.Parse(op[2]); string box = row[b - 1]; row.RemoveAt(b - 1); row.Insert(a - 1, box); break; } case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 { List<string> tail = row.GetRange(n - a, a); row.RemoveRange(n - a, a); row.InsertRange(0, tail); break; } default: { int b = int.Parse(op[2]); row.Reverse(a - 1, b - a + 1); // (시작 자리, 개수) break; } } if (idx == t - 1) sb.Append(string.Join(" ", row)).Append('\n'); // t번 작업을 하기 직전 } sb.Append(string.Join(" ", row)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 49 行
#include <algorithm>#include <iostream>#include <vector>struct Op { char kind; int a, b;};static void printRow(const std::vector<int>& row) { for (size_t i = 0; i < row.size(); i++) std::cout << (i ? " " : "") << row[i]; std::cout << '\n';}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q, t; std::cin >> n >> q; std::vector<int> row(n); for (int& x : row) std::cin >> x; std::vector<Op> ops(q); for (Op& op : ops) { std::cin >> op.kind >> op.a; op.b = 0; if (op.kind != 'L') std::cin >> op.b; } std::cin >> t; // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { const Op& op = ops[idx]; if (op.kind == 'S') { std::swap(row[op.a - 1], row[op.b - 1]); } else if (op.kind == 'M') { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 int box = row[op.b - 1]; row.erase(row.begin() + (op.b - 1)); row.insert(row.begin() + (op.a - 1), box); } else if (op.kind == 'L') { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 std::rotate(row.begin(), row.end() - op.a, row.end()); } else { std::reverse(row.begin() + (op.a - 1), row.begin() + op.b); } if (idx == t - 1) printRow(row); // t번 작업을 하기 직전 } printRow(row);}
Cmain.c · 56 行
#include <stdio.h>#include <string.h>#define MAXN 1000#define MAXQ 2000static int row[MAXN], tmp[MAXN];static char kind[MAXQ];static int pa[MAXQ], pb[MAXQ];static void print_row(int n) { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", row[i]); putchar('\n');}int main(void) { int n, q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d", &row[i]); for (int i = 0; i < q; i++) { scanf(" %c %d", &kind[i], &pa[i]); pb[i] = 0; if (kind[i] != 'L') scanf("%d", &pb[i]); } scanf("%d", &t); /* 마지막 작업부터 첫 작업까지 거꾸로 */ for (int idx = q - 1; idx >= 0; idx--) { int a = pa[idx], b = pb[idx]; if (kind[idx] == 'S') { int x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; } else if (kind[idx] == 'M') { /* i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 */ int box = row[b - 1]; if (b < a) memmove(&row[b - 1], &row[b], (size_t)(a - b) * sizeof(int)); else memmove(&row[a], &row[a - 1], (size_t)(b - a) * sizeof(int)); row[a - 1] = box; } else if (kind[idx] == 'L') { /* 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 */ memcpy(tmp, &row[n - a], (size_t)a * sizeof(int)); memcpy(tmp + a, row, (size_t)(n - a) * sizeof(int)); memcpy(row, tmp, (size_t)n * sizeof(int)); } else { for (int l = a - 1, r = b - 1; l < r; l++, r--) { int x = row[l]; row[l] = row[r]; row[r] = x; } } if (idx == t - 1) print_row(n); /* t번 작업을 하기 직전 */ } print_row(n); return 0;}
Craykonmain.cray · 60 行
head = 控制台.读数字();n = head[0];q = head[1];row = 控制台.读数字();ops = [];循环 (i = 0; i < q; i++){ ops.添加(控制台.读行().去空白().分割(" "));}t = 控制台.读行().转数字();// 마지막 작업부터 첫 작업까지 거꾸로循环 (idx = q - 1; idx >= 0; idx--){ op = ops[idx]; a = op[1].转数字(); 选择 (op[0]) { 情况 "S": b = op[2].转数字(); x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; 跳出; 情况 "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = op[2].转数字(); box = row[b - 1]; row.按位置移除(b - 1); row.插入(a - 1, box); 跳出; 情况 "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 앞 = row.子列表(0, n - a); row = row.子列表(n - a, a); 遍历 (v 在 앞) { row.添加(v); } 跳出; 默认: l = a - 1; r = op[2].转数字() - 1; 当 (l < r) { x = row[l]; row[l] = row[r]; row[r] = x; l++; r--; } 跳出; } 如果 (idx == t - 1) { // t번 작업을 하기 직전 控制台.输出(row.连接(" ")); }}控制台.输出(row.连接(" "));