少儿编程竞赛智算之道2020第一二三场初赛全部试题

1、智算之道2020初赛第一场试题TI排队小A现在站在一个n个人的队伍里排队，他们的编号依次为l-n,现在她面前有m个窗 口，其中第i个窗口会给出一个数字a,然后将队伍中所有编号为ai倍数的人带出队伍， 请问最后队伍中还剩下多少个人？输入格式第一行两个用空格隔开的整数分别表示n,m第二行m个用空格隔开的整数，其中第i个代表a输出格式输出一个整数.代表剩下多少个人数据规模与约定对于 30% 的数据，IWnW100,IWmWlO对于 60% 的数据，IWn1000,lm10对于 IO0%的数据，IWnWIOoOOo,1 WmWlo(UWaiWn样例输入10 3345样例输出3T2开关小B面前有n个开关

2、，开始时第i个开关的状态是ai,其中ai = l表示第i个开关是开 的，a=O表示第i个开关是关的。现在小B获得了一种魔法，他可以进行若干次操作， 每次操作可以选择一个数Xl然后把X号开关及其之前的所有开关状态反转（开变关，关 变开），请问小B最少需要多少次操作才能使所有开关都变为关的状态。输入格式第一行一个整数表示n第二行为一个长度为n的Ol字符串，即每一位只会是0或者1输出格式输出一个整数.表示最少需要多少次操作才能使所有开关都变为关的状态数据规模与约定对于30%的数据，1WnW20对于60%的数据，IWnW2000对于100%的数据，1200000样例输入41001样例输出3T3字符串给

3、定两个字符串S和它们都只由小写字母组成。现在请计算出宇符串S的本质不同的 排列中有多少种是字符串T的子串，本质不同，就是看起来不同，例如aab有3种本质不同的排列aab, aba, baa。输入格式第一行有一个宇符串S第二行有一个宇符串T输出格式数据规模与约定对于3(的数据，对于60%的数据， 对于o的数据,输出一个整数表示字符串S的本质不同的排列中有多少种是字符串T的子串1 I S I 5,1 I T I 2001 I S I 2000,1 I T I W2000IW S 200000sl I T I 200000样例输入aababacabaa样例输出2智算之道2020第二场初赛试题TI声控

4、灯小明正在上楼梯，当小明逐渐接近某层楼的时候，这层楼的声控灯检测到小明的脚步声便会 亮起来，当小明逐渐远去的时候，声控灯由于一段时间内没检测到声音又会灭下去。由于小明是匀速上楼的，而且他的速度把控得刚刚好，脚步声的音量也十分恰当，使得灯的 亮灭呈现出这样的状态：他当前所在的楼层的声控灯是亮起的，他即将抵达的下一层楼的声 控灯是亮起的，他刚刚离开的那层楼的声控灯也是亮起的。现在你站在楼的外面，通过窗户看到了灯的亮灭状态，请推断小明现在在几楼？输入格式每个测试点包含以下内容：第一行给出一个整数T1表示接下来给出T组测试数据每组测试数据包含两行第一行包含两个数n,m,表示这栋楼一共有n层，当前有m盏

5、灯是亮起的，而其余灯都 是熄灭的第二行包含m个整数，这些整数按照从小到大的顺序给出亮起的灯的序号保证输入数据是符合实际情况的输出格式输出T行，每行包含一个数字，按照输入的顺序依次给出每组测试数据的答案。如果答案 不确定，请输出-1数据规模与约定对于 50% 的数据，lT10,3nl,m=3对于 IO0 的测试点，1T 1000,1 W10°IWmW3样例输入25312 3521 2样例输出21T2构造字符串给定若干个小写英文字母，请你用这些英文字母组成nnn个字符串，宇符串可以是空串。 要求这nnn个字符串的最长公共前缀最长。求出这个最长的长度，所有宇母都要用完，且每个字母只能用在一

6、个字符串里。名词解释前缀,是指一个字符串从第一个字符开始的连续若干个字符组成的宇符串。前缀可以为空串。 比如宇符串"aab"的前缀有四个，分别是,1 ,a", ,aa,1 ,aab"我们说一个字符串SSS是某些串的公共前缀，当且仅当这个串是每个字符串的前缀。 每一个公共前缀都是一个字符串，是字符串就有长度。当nn个串都确定下来的时候，这 n个串的所有公共前缀也就确定下来了，而且可以证明公共前缀的数目是有限的，在这 有限个公共前缀中，有一个公共前缀的长度是最长的，这个前缀就是最长公共前缀。举个例子，假设现在有三个串：abbcabbdeabbe这个三个串的杲

7、长公共前缀是”abb”，长度为3再举个例子，假设现在有四个串：abbdbbdabbdabb那么这四个串的最长公共前缀是：长度为O输入格式输入共有两行第一行是一个整数n ,表示字符串的数量第二行包含26个非负整数。从前往后依次表示你拥有字母a的数目，字母b的数目, 字母Z的数目。输出格式输出一个非负整数，表示答案数据规模与约定对于30%的数据，除了字母a之外其它字母的数目都为0对于IOO的数据，210°,每种字母的个数也不超过10°样例输入233000000000000000000000000样例输出2样例解释在第一个样例中，你拥有3个字母a和3个字母b可以构造这样的两个串P

8、baTabbl 这样最长公共前缀的长度是2o可以证明不存在更优秀的方案样例输入22IIOOOOOOOOOOOOOOOOOOOOOOOO样例输出20样例解释2在第二个样例中，你拥有1个字母a和1个字母b,无论如何构造两个串，都无法产生非 空的公共前缀，因此答案是0T3情报战现在我方已经查明，敌人通信所使用的加密方式依赖于一个长度为n的数列，只要得知了 这个数列中每个数的值，我方便可破解敌方的通信。通过深入敌人内部的内线人员的艰苦奋斗,我方逐渐获得了一些有用的情报,通过这些情报, 整个数列正在被不断地破解。先后有m条情报被得知，每条情报是以下两种情况之一：情况1 :知道了数列中第X个数的值情况2

9、:知道了数列中第X个数和第y个数的和每得知一条情报，我方都试图破解数列中元素的值作为情报部门核心技术人员的你，请编程实现如下功能：每次得知一条新情报，你都要计算 当前已经能够确定出数列中的多少个数了你比较笨，对于情况2这种情报，只能在已知其中一个数的情况下推岀另一个数，不能通 过若干情况2的情报列方程求解输入格式第一行，两个正整数n,m接下来m行，每行的第一个数是typeo如果type=l,则接下来跟着一个整数x,表示得 知了数列中第X个数的值；如果type二2,则接下来跟着两个空格隔开的整数x,y表示得知 了第X个数和第y个数的和输出格式输出m行，每行包含一个非负整数，第i行的非负整数表示在

10、得知了前i条情报之后数 列中已经能够确定的数的数量数据规模与约定对于20的数据，lWn,rW10,且只有第一种情报对于50 的数据，IWn,mW5000对于 IOo)6 的数据，lWn,mW3l'可能会有重复的情报，也可能出现x=y的情况样例输入54111 22 2 3213样例输出1233智算之道2020第三场初赛试题TI水杯小D有一个能显示温度的杯子.其原理是杯盖上的一个传感器.只有在杯子内的水的体积 大于等于某个数LL的时候传感器才能显示水温，并且如果水温不在A3内传感器也无法注意，这里温度对水的体积没有影响初始水杯为空，有n次操作，操作分为三种：1 X表示把水温变成X-2x表示

11、把水的体积变成X.3查询传感器的显示情况.如果不能显示水温输岀GG,否则输岀水温.输入格式第一行四个整数n丄AB含义如题目所示.接下来n行，每行一个整数OPt或两个整数opt,x,表示执行操作opt.输出格式对于所有操作3输出结果，每行一个答案.数据规模与约定对于 Io 的数据，IWnWlo00,-273WAWBWlO(UWLWloOo,1WOPtW3.对于操作2, -273WXWloo ；对于操作2, lx1000.样例输入52 131 52 331 23样例输出GG2T3顺序安排给定一棵有根树，对于给定的树求出对应的一种排列使得代价和最小。 对于一种排列计算代价方式如下给定常数koa的父亲在序列中的位置是X, a在序列中的位置是yoa的儿子节点必须在a之后出现。a的父亲在a之前出现，代价是k×(y-)o特殊的，容易看