简答题

课程名称:NOC软件创意编程

题目:谜 【题目描述】 二战期间,德军使用一种名为“Enigma”的密码机。这个密码机最终被盟军破解的关键之一,是来自于使用它的人的习惯。德军每天发送的电报中,会有很多重复的词语,比如问候语、结尾的落款、每天的天气等等。盟军的破解人员把这些重复出现的词语称作“crib”。知道了“crib”,还要知道“crib”在密文中的什么位置。由于“Enigma”是通过电路加密,所以一 个字母加密后绝对不会仍然是自身,这个特性可以帮助我们定位“crib”的位置。 例如盟军截获了一条密文"XEQFTWRWEVTRES",并且我们猜测原文中可能含有"WETTER"这个词。因为字母绝对不会被加密成自身,所以当我们将"WETTER"这个词和密文去比对,就可以找到这个词可能的位置。 在下面这个位置时,"WETTER"和密文对应的每个位置的字母都不相同,所以这条密文的原文中可能含有"WETTER"。 一条密文中可能含有不止一种“crib”,同一种“crib”也可能出现多次,“crib”所占据的位置不能有重叠。给出所有可能的“crib”和一条密文,你要求出这条密文中可能包含的“crib”的最多个数。 【输入格式】 第 1 行,1 个正整数 n,表示有 n 种“crib”。 接下来 n 行,每行一个字符串,表示 1 种“crib”。 最后 1 行,1 个字符串,表示密文。 【输出格式】 输出 1 个整数,表示密文中可能包含的“crib”的最大个数。 【输入样例 1】 2 WETTER XORT XEQFTWROEXGRES 【输出样例 1】 2 【输入样例 2】 2 CRYTIC OVULIST CCNDDZIYXDSMTOS 【输出样例 2】 2 【输入样例 3】 3 RUBRA DOING GRATED XMQWVBJAMMRGCOXQPFIZOBMDUYOXJNGTTNRJOHLD 【输出样例 3】 8 【说明提示】 样例 1 说明: 如下安排两个 crib 的位置,最多包含 2 个 crib。 crib 也可能在如下两个位置,仍然是包含 2 个 crib。 样例 2 说明: 如下安排两个 crib 的位置,最多包含 2 个 crib。 【数据范围】 对 10%数据:n=1 另有 10%数据满足:所有“crib”的长度都等于 1。 对 100%数据:1≤n≤50;“crib”互不相同。“crib”的长度不超过 50,密文的长度不超过 105,输入中所有字符串只含大写英文字母。

简答题

课程名称:NOC软件创意编程

题目:商场导购 【题目描述】 作为 H 国知名商人,东东在 D 城的市中心开了一家高人气商场,商场提供极其贴心的五星级导购服务。 需要导购服务的顾客可以提前一天预约使用的时间段。目前有 N 位顾客预约了第二天导购服务,其中第 i 位顾客预约的时间段为 Ai 到 Bi,注意导购服务包括了 Ai 和 Bi两个时间段。很明显一位导购在同一个时间段只能服务一位客户。 为了节约人工成本,东东希望使用最少的导购满足全部顾客的要求。请你帮他求出第二天最少需要多少位导购。 【输入格式】 输入有两行,第一行为两个正整数 N,表示预约导购服务的顾客数量。 第 2 到 N+1 行, 每行两个整数 Ai,Bi,表示第 i 位顾客预约的时间段。 【输出格式】 输出一个整数,表示最少需要多少导购,可以满足全部顾客。 【输入样例 1】 5 1 10 2 5 5 8 3 6 6 10 【输出样例 1】 4 【样例 1 说明】 由于导购服务包括边界的时间段,所以[2, 5]和[5, 8]必须让不同的导购负责,那么只有[2, 5]和[6, 10]可以请同一个导购,其他都需要单独请导购。 【输入样例 2】 10 24 29 11 14 5 10 26 32 4 6 27 31 39 39 39 44 18 21 18 18 【输出样例 2】 3 【数据范围】 对于 30%的数据:1<= N<= 10; 对于 60%的数据:1<= N<= 100,1<= Ai<= Bi<= 100; 对于 100%的数据:1<= N<= 10000,1<= Ai<= Bi<= 5000。