|
|
|
第三年蓝球杯，感觉题目比往年简单多了。题量合适够我这种菜鸟解答......大概可能有45分，希望进省一大三最后i一次机会了55555进省一了耶耶耶试题A:穿越时空之门（满分）本题总分：5分【问题描述】 随着2024年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。 在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数位之和。 在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。 穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。国王选定了小蓝作为领路人，带领着力量值从1到2024的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这2024位勇者中，有多少人符合穿越时空之门的条件。思路：进制转换......答案：63多此一举的输出纯粹怕粗心。defcheck(a):jin_2,x2=jin_s(a,2)jin_4,x4=jin_s(a,4)print(a,x2,x4)ifjin_2==jin_4:returnTruereturnFalsedefjin_s(x,m):res=[]whilex:res.append(x%m)x//=mreturnsum(res),resdefmain():res=0foriinrange(1,2025):ifcheck(i):res+=1print(res,'**************')#63if__name__=='__main__':main()试题B:数字串个数（满分）本题总分：5分【问题描述】小蓝想要构造出一个长度为10000的数字字符串，有以下要求： 1)小蓝不喜欢数字0，所以数字字符串中不可以出现0； 2)小蓝喜欢数字3和7，所以数字字符串中必须要有3和7这两个数字。请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其对109+7取余后的结果。思路：第一反应先构造长度2-4，模拟找规律。发现DP即可答案：157509472defmain():n=10000p=int(1e9+7)dp=[[[0]*2foriinrange(2)]forjinrange(n+1)]#前缀指的是不包括当前字符串的前子串#状态为[当前str长度][前缀是否有3][前缀是否有7]#边界dp[1][0][0]=7#没有3和7,只能是除37的其它七种方案dp[1][0][1]=1#有3,一种方案dp[1][1][0]=1#有7,一种方案dp[1][1][1]=0#有3和7,不可能(长度为1不可能同时出现37)#枚举阶段,决策为当前i位置填什么字符foriinrange(2,n+1):#状态转移dp[i][0][0]=(dp[i-1][0][0]*7)%p#前缀无37(当前可填7种1、2、4、5、6、8、9)dp[i][0][1]=(dp[i-1][0][1]*8+dp[i-1][0][0])%p#从有7(可填8种)、和均没有(可填1种)dp[i][1][0]=(dp[i-1][1][0]*8+dp[i-1][0][0])%p#从有3(可填8种)、和均没有(可填1种)dp[i][1][1]=(dp[i-1][1][1]*9+dp[i-1][0][1]+dp[i-1][1][0])%p#从有37(可填9种)、只有3(1种)、只有7(1种)三种情况#答案print(dp[n][1][1])#157509472if__name__=='__main__':main()试题C:连连看（满分）时间限制:10.0s内存限制:512.0MB本题总分：10分【问题描述】 小蓝正在和朋友们玩一种新的连连看游戏。在一个n×m的矩形网格中，每个格子中都有一个整数，第i行第j列上的整数为Ai,j。玩家需要在这个网格中寻找一对格子(a,b)−(c,d)使得这两个格子中的整数Aa,b和Ac,d相等，且它们的位置满足|a−c|=|b−d|>0。请问在这个n×m的矩形网格中有多少对这样的格子满足条件。对于所有评测用例，1≤n,m≤1000，1≤Ai,j≤1000。目标算法O(n^2)思路：对于每个元素,判断对‘X’型方向上有无相同元素。 因为矩阵斜行的下标满足 (i+j)%2000和(i-j)%2000是相等的，参考八皇后问题。 所以可用二维哈希[斜行][元素值]。importsysdefmain():input=lambda:sys.stdin.readline().strip()#快读n,m=map(int,input().split())maps=[]hax0=[[0]*1001foriinrange(2001)]#斜行=>'\'hax1=[[0]*1001foriinrange(2001)]#斜行=>'/'foriinrange(n):maps.append(list(map(int,input().split())))#记录这一斜行每个元素出现次数forj,xinenumerate(maps[-1]):hax0[(i-j)%2000][x]+=1hax1[(i+j)%2000][x]+=1res=0foriinrange(n):forjinrange(m):ai=maps[i][j]#因为要排除自己,所以需要大于1才行,还需要-1。#例如当前斜行有2个相等元素,有一个是自己,所以只能配成一对ifhax0[(i-j)%2000][ai]>1:res+=hax0[(i-j)%2000][ai]-1ifhax1[(i+j)%2000][ai]>1:res+=hax1[(i+j)%2000][ai]-1print(res)if__name__=='__main__':main()试题D:神奇闹钟（满分）时间限制:10.0s内存限制:512.0MB本题总分：10分【问题描述】 小蓝发现了一个神奇的闹钟，从纪元时间（1970年1月1日00:00:00）开始，每经过x分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起了小蓝的兴趣，他想要好好研究下这个闹钟。 对于给出的任意一个格式为yyyy-MM-ddHH:mm:ss的时间，小蓝想要知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？注意，你不必考虑时区问题。对于所有评测用例，1≤T≤10，1≤x≤1000，保证所有的时间格式都是合法的。目标复杂度应该要(9999年-1970年，以间隔迭代肯定超时，所以不能迭代)思路：datetime库，就用了两个最简单的类函数进行拼凑。importsysfromdatetimeimportdatetime,timedelta#时间类、时间差值类defmain():input=lambda:sys.stdin.readline().strip()start=datetime(1970,1,1,0,0,0)foriinrange(int(input())):aa,bb,mmm=input().split()n,y,r=map(int,aa.split('-'))s,f,m=map(int,bb.split(':'))#和秒没有关系,因为从0:0:0开始,又是整数间隔分钟#实例化当前时间now=datetime(n,y,r,s,f,0)#到目前的差值时间diff=now-start#计算差值时间的(mod间隔)的余数totmins=int(diff.total_seconds())//60%int(mmm)#把当前时间前移差值对间隔余多少分钟print(str(now-timedelta(minutes=totmins)))if__name__=='__main__':main()试题E:蓝桥村的真相（满分）时间限制:10.0s内存限制:512.0MB本题总分：15分【问题描述】 在风景如画的蓝桥村，n名村民围坐在一张古老的圆桌旁，参与一场思想的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要么是无可救药的说谎者。 当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流发言，编号为i的村民提出了这样的断言：坐在他之后的两位村民——也就是编号i+1和i+2（注意，编号是环形的，所以如果i是最后一个，则i+1是第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？ 请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，说谎者的总数。对于所有评测用例，1≤T≤105，3≤n≤1018。目标算法需要O(T)或者O(Tlogn)思路：刚开始没思路，先写个暴力找规律(因为数据范围2i）前往下一个结点。同理，小桥抵达之后，小蓝需要选择一个序号k>j的符文石sk继续他们的巡游。 为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣，这种共鸣只有当数字符号中至少包含一个特定的元素——星火（数字0）、水波（数字2）或者风语（数字4）时，才会发生。例如，符号序列126,552,24,4中的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而如果是15,51,5，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语中的任意一个。 小蓝总是先启程，使用他的符文石开启巡游。 你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样的序列形式为si1,ti2,si3,ti4,...，其中序列索引满足i1RRorw
|
|
|手机版|心飞设计-版权所有：微度网络信息技术服务中心
( 鲁ICP备17032091号-12 )|网站地图
发表于 2024-9-13 09:34:26
