CF2275B.Did Not Go to Print
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Recently, K1o0n bought himself a new expensive printer, which is distinguished by its memory, that is, it may not print immediately. Yesterday, while he was away from his new purchase, his friends used the printer.
There are n documents numbered from 1 to n. Initially, the printer memory is empty. The friends sequentially performed n commands on the printer, where the i-th command can be one of:
- '1' — scanning. Document i is sent to the device memory and is placed on top of everything already there.
- '2' — printing from memory. If the memory is not empty, the device prints the topmost document in memory and removes it from there. Otherwise, the device prints document i.
- '3' — quick print. The device prints document i.
Today, the friends came to K1o0n with a complaint — not all documents were printed. Help K1o0n find the indices of all documents that were not printed.
最近,K1o0n 为自己购买了一台昂贵的新打印机,这台打印机的特点是具有内存,也就是说,它可能不会立即打印。
昨天,当他离开这台新打印机时,他的朋友们使用了该打印机。
共有 n 份编号为 1 到 n 的文档。初始时,打印机内存为空。朋友们按顺序对打印机执行了 n 条命令,其中第 i 条命令可能是以下三种之一:
'1'— 扫描:将文档 i 发送到设备内存,并将其置于内存中已有内容的最上方。'2'— 从内存中打印:若内存非空,则设备打印内存中最上方的文档,并将其从内存中移除;否则,设备打印文档 i。'3'— 快速打印:设备直接打印文档 i。
今天,朋友们向 K1o0n 抱怨——并非所有文档都被打印了。请帮助 K1o0n 找出所有未被打印的文档的编号。
输入格式
The first line contains an integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains an integer n (1≤n≤2⋅105) — the number of documents.
The second line of each testcase contains a string s of length n, consisting of the characters '1', '2' and '3' — the friends' commands.
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)—— 测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤2⋅105)—— 文档的数量。
每个测试用例的第二行包含一个长度为 n 的字符串 s,由字符 '1'、'2' 和 '3' 组成 —— 表示朋友们的指令。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each testcase, output two lines.
In the first line — the number k of documents that were not printed.
In the second line — their numbers in increasing order, separated by spaces. If k=0, the second line is empty.
对于每个测试用例,输出两行。
第一行:未被打印的文档数量 k。
第二行:这些文档的编号(按升序排列),以空格分隔。若 k=0,则第二行为空行。
输入输出样例
输入#1
6 2 12 2 13 2 23 6 112332 3 112 6 211213
输出#1
1 2 1 1 0 2 3 6 2 1 3 3 2 4 5
说明/提示
In the first testcase, the first document number 1 is stored in memory, and then it is printed at the next step, so document number 2 is not printed.
In the second testcase, document number 1 is put into memory, but is never printed, because the next command prints document number 2.
In the fifth testcase, the first document number 1 is put into memory, then document number 2 is put into memory, and by the third command we print the last document put into memory — document number 2.
在第一个测试用例中,第一个文档编号 1 被存入内存,随后在下一步被打印,因此文档编号 2 未被打印。
在第二个测试用例中,文档编号 1 被存入内存,但从未被打印,因为下一个命令打印的是文档编号 2。
在第五个测试用例中,第一个文档编号 1 被存入内存,接着文档编号 2 被存入内存,而第三个命令打印的是最后存入内存的文档——即文档编号 2。
输入解题思路,AI测评打分。不知道怎么写?