首页 > 试题广场 >

数据分类处理

[编程题]数据分类处理
  • 热度指数:180417 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
\hspace{15pt}信息社会,有海量的数据需要分析处理,比如公安局分析身份证号码、QQ 用户、手机号码、银行帐号等信息及活动记录。采集输入大数据和分类规则,通过大数据分类处理程序,将大数据分类输出。
\hspace{15pt}对于给定的分类规则集 R = \{R_1, R_2, \dots, R_m\} ,规范化它,具体地:
\hspace{23pt}\bullet\,R 中的整数按从小到大的顺序重新排序;
\hspace{23pt}\bullet\,去除 R 中的重复元素;
\hspace{15pt}记规范化后的分类规则集为 r = \{r_1, r_2, \dots, r_m\}

\hspace{15pt}对于收集到的、由若干个整数组成的数据集 I ,按照下方的要求,使用规范后的分类规则集 r 输出分类后的结果。
\hspace{23pt}\bullet\,对于第 i 条分类规则 r_i ,如果 I 中存在以 r_i 为连续子串的整数,则该规则集有效;进一步地,你需要输出有多少条数据符合该规则,以及这些数据在 I 中的位置、数据本身。

\hspace{15pt}子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。对应本题中,你需要将整数看作是数字字符串。

输入描述:
\hspace{15pt}第一行先输入一个整数 n \left(1 \leqq n \leqq 100\right) 代表数据集 I 中的数据条数。随后,在同一行输出 n 个整数 I_1, I_2, \dots, I_n \left(0 \leqq I_i < 2^{31}\right) 代表数据。
\hspace{15pt}第二行先输入一个整数 m \left(1 \leqq m \leqq 100\right) 代表分类规则集 R 中的规则条数。随后,在同一行输出 m 个整数 R_1, R_2, \dots, R_m \left(0 \leqq R_i < 2^{31}\right) 代表规则。


输出描述:
\hspace{15pt}在一行上:
{\hspace{20pt}}_\texttt{1.}\,先输出一个整数 k ,代表一共需要输出的数字个数。简单地说,这个数字为下文中你输出数量的个数统计。
{\hspace{20pt}}_\texttt{2.}\,随后,对于规范后的每一条规则,如果其有效:先输出这条规则本身,随后输出一个整数 p ,代表符合该规则的数据条数;随后输出 p 个二元组 \{\textrm{id}_1, I_{\textrm{id}_1}\}, \{\textrm{id}_2, I_{\textrm{id}_2}\}, \dots, \{\textrm{id}_p, I_{\textrm{id}_p}\} ,代表符合这条规则的数据在 I 中的位置、数据本身。其中,位置从 0 开始计数。如果其无效,则跳过这条规则。
示例1

输入

15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123
5 6 3 6 3 0

输出

30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786

说明

\hspace{15pt}在这组样例中,给定的原始数据集为 I = \{123, 456, 786, 453, 46, 7, 5, 3, 665, 453456, 745, 456, 786, 453, 123\} ,给定的原始规则集为 R = \{6, 3, 0\}
\hspace{15pt}规范化后的规则集为 r=\{0,3,6\}
\hspace{15pt}随后,对 I 进行分类处理:
\hspace{23pt}\bullet\,对于规则 r_0=0 ,由于 I 中不存在以 0 为连续子串的数据,因此该规则无效,跳过;
\hspace{23pt}\bullet\,对于规则 r_1=3I 中以 3 为连续子串的数据有:I_0 = 12{\color{orange}{3}}I_3 = 45{\color{orange}{3}}I_7 = {\color{orange}{3}}I_9 = 45{\color{orange}{3}}456I_{13} = 45{\color{orange}{3}}I_{14} = 12{\color{orange}{3}},因此该规则有效。根据输出描述,先输出规则本身 \texttt{ 、随后输出符合要求的条数 \texttt{ 、随后输出符合要求的数据在 I 中的位置和整数本身 \texttt{
\hspace{23pt}\bullet\,对于规则 r_2=6I 中以 6 为连续子串的数据有:I_1 = 45{\color{orange}{6}}I_2 = 78{\color{orange}{6}}I_4 = 4{\color{orange}{6}}I_8 = {\color{orange}{66}}5I_9 = 45345{\color{orange}{6}}I_{11} = 45{\color{orange}{6}}I_{12} = 78{\color{orange}{6}} ,因此该规则有效。根据输出描述,先输出规则本身 \texttt{ 、随后输出符合要求的条数 \texttt{ 、随后输出符合要求的数据在 I 中的位置和整数本身。
\hspace{15pt}不要忘了在输出开始的整数 k ,在这个样例中,一共输出了 30 个数字,所以 k = 30

备注:
\hspace{15pt}本题由牛客重构过题面,您可能想要阅读原始题面,我们一并附于此处。
\hspace{15pt}【以下为原始题面】

从R依次中取出R<i>,对I进行处理,找到满足条件的I: 

I整数对应的数字需要连续包含R<i>对应的数字。比如R<i>为23,I为231,那么I包含了R<i>,条件满足 。 

按R<i>从小到大的顺序:

(1)先输出R<i>; 

(2)再输出满足条件的I的个数; 

(3)然后输出满足条件的I在I序列中的位置索引(0开始); 

(4)最后再输出I。 

附加条件: 

(1)R<i>需要从小到大排序。相同的R<i>只需要输出索引小的以及满足条件的I,索引大的需要过滤掉 

(2)如果没有满足条件的I,对应的R<i>不用输出 

(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)

 

序列I:15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123(第一个15表明后续有15个整数) 

序列R:5,6,3,6,3,0(第一个5表明后续有5个整数) 

输出:30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786

说明:

30----后续有30整数

3----从小到大排序,第一个R<i>为0,但没有满足条件的I,不输出0,而下一个R<i>是3

6--- 存在6个包含3的I 

0--- 123所在的原序号为0 

123--- 123包含3,满足条件 

这道题你会答吗?花几分钟告诉大家答案吧!