【python】✨最小的十六进制python的16进制❓️问题描述答案提交思路︎参考答案✨Excel的列进制转化❓️问题描述答案提交思路︎参考答案✨相等日期datetime日期❓️问题描述答案提交思路︎参考答案✨多少种取法简单模拟❓️问题描述答案提交思路︎参考答案✨最大连通分块DFS❓️问题描述答案提交思路︎参考答案✨哪一天模拟题❓️问题描述输入格式输出格式样例输入样例输出评测用例规模与约定思路︎参考代码✨信号覆盖暴力模拟❓️问题描述输入格式输出格式样例输入样例输出评测用例规模与约定思路︎参考代码✨清理水草简单模拟❓️问题描述输入格式输出格式样例输入样例输出样例输入样例输出评测用例规模与约定思路︎参考代码✨最长滑行DFS搜索❓️问题描述输入格式输出格式样例输入样例输出样例说明评测用例规模与约定思路︎参考代码✨区间最小值ST表模板题❓️问题描述输入格式输出格式样例输入样例输出评测用例规模与约定思路RMQ问题ST

Sparse

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。

这道题和第一期模拟赛的第一题都是考虑到了二进制对于python来说还是很快的只需要从2022开始遍历利用python的bin函数就可以迅速将十进制转成二进制然后再减去首字母的两个0b即可判断最低的6个尾数为0即可。

︎参考答案

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。

如果以2个字母的组合为列名最多为26x26676个列所以2022列就是以三个字母的组合去得到的其实简单一点这道题也可以进行简单的手算但是仔细一看实际上就是2022转成26进制即可但是这个26进制没有数字是从A~Z。

其实这道题我们也可以列一个数组穷举把所有数算出来然后取对应位置2022的数据出来就好了这两种方法都OK的。

︎参考答案

对于一个日期我们可以计算出年份的各个数位上的数字之和也可以分别计算月和日的各位数字之和。

请问从

1900

日总共有多少天年份的数位数字之和等于月的数位数字之和加日的数位数字之和。

例如2022年11月13日满足要求因为

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。

这道题最简单的话就是可以利用python的datetime库进行判断转成字符串进行计数最后把符合条件的结果计数输出就是最后日期的总数量。

︎参考答案

datetime.timedelta(days1)print(cnt)

70910✨多少种取法简单模拟

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。

这道题其实很简单的就是随机取两个数然后进行判断如果符合条件的话计数最后就把结果输出即可

︎参考答案

110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110

001011101000100011111111111010000010010101010111001000010100

101100001101011101101011011001000110111111010000000110110000

010101100100010000111000100111100110001110111101010011001011

010011011010011110111101111001001001010111110001101000100011

101001011000110100001101011000000110110110100100110111101011

101111000000101000111001100010110000100110001001000101011001

001110111010001011110000001111100001010101001110011010101110

001010101000110001011111001010111111100110000011011111101010

011111100011001110100101001011110011000101011000100111001011

011010001101011110011011111010111110010100101000110111010110

001110000111100100101110001011101010001100010111110111011011

111100001000001100010110101100111001001111100100110000001101

001110010000000111011110000011000010101000111000000110101101

100100011101011111001101001010011111110010111101000010000111

110010100110101100001101111101010011000110101100000110001010

110101101100001110000100010001001010100010110100100001000011

100100000100001101010101001101000101101000000101111110001010

101101011010101000111110110000110100000010011111111100110010

101111000100000100011000010001011111001010010001010110001010

001010001110101010000100010011101001010101101101010111100101

001111110000101100010111111100000100101010000001011101100001

101011110010000010010110000100001010011111100011011000110010

011110010100011101100101111101000001011100001011010001110011

000101000101000010010010110111000010101111001101100110011100

100011100110011111000110011001111100001110110111001001000111

111011000110001000110111011001011110010010010110101000011111

011110011110110110011011001011010000100100101010110000010011

010011110011100101010101111010001001001111101111101110011101答案提交

这是一道结果填空的题你只需要算出结果后提交即可。

本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。

︎参考答案

sys.setrecursionlimit(131-1)matrix

110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110

001011101000100011111111111010000010010101010111001000010100

101100001101011101101011011001000110111111010000000110110000

010101100100010000111000100111100110001110111101010011001011

010011011010011110111101111001001001010111110001101000100011

101001011000110100001101011000000110110110100100110111101011

101111000000101000111001100010110000100110001001000101011001

001110111010001011110000001111100001010101001110011010101110

001010101000110001011111001010111111100110000011011111101010

011111100011001110100101001011110011000101011000100111001011

011010001101011110011011111010111110010100101000110111010110

001110000111100100101110001011101010001100010111110111011011

111100001000001100010110101100111001001111100100110000001101

001110010000000111011110000011000010101000111000000110101101

100100011101011111001101001010011111110010111101000010000111

110010100110101100001101111101010011000110101100000110001010

110101101100001110000100010001001010100010110100100001000011

100100000100001101010101001101000101101000000101111110001010

101101011010101000111110110000110100000010011111111100110010

101111000100000100011000010001011111001010010001010110001010

001010001110101010000100010011101001010101101101010111100101

001111110000101100010111111100000100101010000001011101100001

101011110010000010010110000100001010011111100011011000110010

011110010100011101100101111101000001011100001011010001110011

000101000101000010010010110111000010101111001101100110011100

100011100110011111000110011001111100001110110111001001000111

111011000110001000110111011001011110010010010110101000011111

011110011110110110011011001011010000100100101010110000010011

010011110011100101010101111010001001001111101111101110011101matrix

len(matrix),

这道题实际上就是模拟题首先我们可以认为是0~6分别代表周一到周日我们只需要把当前星期n天数%7就可以得到n天后是周几由于是0-indexing的所以1转成1-indexing

︎参考代码

int(input())print((w-1n)%71)✨信号覆盖暴力模拟

❓️问题描述

小蓝负责一块区域的信号塔安装整块区域是一个长方形区域建立坐标轴后西南角坐标为

(0,

为了对信号覆盖的情况进行检查小蓝打算在区域内的所有横纵坐标为整数的点进行测试检查信号状态。

其中横坐标范围为

W纵坐标范围为

y表示一个信号塔的坐标。

信号塔可能重合表示两个信号发射器装在了同一个位置。

输出格式

这道题实际上一看下来就是一个暴力模拟的题目了只需要循环这W1)*(H1)个点查看有哪些被信号覆盖即可所以这道题可以直接穷举看题目的一个数量级不大所以O(n3)O(n^3)O(n3)应该也是没问题的我稍微改进了一下简单的穷举我只对每一个信号塔周边的区域进行判断。

也可以遍历所有的点然后遍历所有的信号塔查看是否有覆盖但是那个可能就会代码简单时间复杂一点

︎参考代码

((x1-x2)**2(y1-y2)**2)**0.5flag

[[0]*(h1)

c2相邻整数之间用一个空格分隔表示一次清理。

请注意输入的顺序。

输出格式

感觉这道题也是一样的和前面的信号覆盖也是类似的并且数据也不是很大所以首先就用模拟的穷举也可以很快的写出来只要把清理过的标为0其他均为1之后进行求和即可

所以以下简单的思路还是用一个flag数组表示是否清理过然后计数所有清理过的草坪最后总数-清理过的草坪就可以得到未清理过的草坪了。

︎参考代码

如果小蓝在某个位置而他上、下、左、右中有一个位置的高度严格低于当前的高度小蓝就可以滑过去滑动距离为

如果小蓝在某个位置而他上、下、左、右中所有位置的高度都大于等于当前的高度小蓝的滑行就结束了。

输入格式

这道题实际上就是一道搜索问题本质上我们还是使用DFS进行求解我们可以从任意一个点开始搜索然后最后取最大值就是我们最后的结果。

这里我们使用DFS求解为了加快速度我们还是使用了记忆化搜索如果发现已经搜索过了就直接返回结果即可。

首先简单讲一讲DFS的思路吧我们会从当前x,y进行不断搜索然后发现下一个点符合条件在范围内且严格小于当前点的高度我们就继续搜索因为我们要取最长所以我们要取max不断取最优的结果最后都记录到我们的dp数组中

这样在下一次搜索的时候如果发现当前的dp数组的值已经被记录过了那我们就直接返回值即可就不需要那么多花里胡哨的操作其实这道题可能也叫树形的DFS有时候还是会出现的不过思路还是OK的就是类似于树形一样不断迭代dfs而已最后就是还要加上这个递归深度的代码这样保证自己不会出错

︎参考代码

range(n):a.append(list(map(int,input().split())))dp

[[-1]*m

这道题属于一个模板题就是需要知道这个ST表的模板接下来我来介绍一下

RMQ问题

Query即区间最值查询是指这样一个问题对于一个长度N的数组在多次询问中每次都以O(1)的时间得到区间[a,

Sparse

Table算法是一个非常有名的在线处理RMQ问题的算法它可以在O(nlogn)O(nlogn)O(nlogn)时间内进行预处理然后在O(1)O(1)O(1)时间内回答每个查询。

其思想就是保存以i为起点的某段数据的最小值。

预处理用动态规划DP解决。

思想接近于二路归并排序过程的分治思想。

设A[i]A[i]A[i]是要求区间最值的数列F[i,j]F[i,

j]F[i,j]表示从第iii个数起连续2j2^j2j个数中的最大值。

A数列为3

F[10]表示第1个数起长度为2^01的最大值其实就是3这个数。

F[1,1]

F[i,j]max(F[i,j−1],F[i2(j−1)][j−1])F[i,

max(F[i,

F[i,j]max(F[i,j−1],F[i2(j−1)][j−1])

怎么理解呢

其实就是求四个元素的前两个以及后两个的最大值。

在求F[3,2]的时候已经知道了F[3,

显然区间[i,i2j−1−1][i,i2^{j-1}-1][i,i2j−1−1]和[i2j−1,i2j−1][i2^{j−1},i2^j-1][i2j−1,i2j−1]一定覆盖了区间[i,i2j−1][i,i2^j-1][i,i2j−1]从图中也可以看出区间[i,i2j−1][i,i2^j-1][i,i2j−1]内的最大值就是区间[i,i2j−1−1][i,i2^{j-1}-1][i,i2j−1−1]和[i2j−1,i2j−1][i2^{j−1},i2^j-1][i2j−1,i2j−1]内的最大值中更大的一个所以就得到了上述的递推公式。

F[i,j]max(F[i][j−1],F[i2(j−1)][j−1])F[i,

max(F[i][j-1],

F[i,j]max(F[i][j−1],F[i2(j−1)][j−1])

代码如下

进行转化dp[i][j]max(dp[i][j-1],dp[i(1(j-1))][j-1])

状态转移方程查询区间

那么查询怎么做呢毕竟我们存放的都是2次幂个数的最小值。

假如查询的区间是奇数个或不是2次幂个数怎么弄

假如我们需要查询的区间为(i,j)(i,j)(i,j)那么我们需要找到小于这个闭区间(左边界取i右边界取j)的最大幂可以重复比如查询56789我们可以查询5678和6789)

log2(

所以总结下来先计算出一个满足2tr−l12t12^tr−l12^{t1}2tr−l12t1的t值即小于区间长度的2的最高次幂。

显然区间[l,l2t−1][l,l2^{t-1}][l,l2t−1]和[r−2t1,r][r-2^{t}1,r][r−2t1,r]一定覆盖了区间[l,r]如下图

F[i,

一定要用小于等于区间的最大幂是因为要能够两个F加在一起能够覆盖整个区间。

其实还有更简单的但是可能不能全过但是我们肯定能拿分就是直接穷举呗本身python也有min函数

︎参考代码

进行转化dp[i][j]min(dp[i][j-1],dp[i(1(j-1))][j-1])

状态转移方程self.dpdpdef

min(n,ik)print(st.query(l,r),end

int(input())

min(ik,n-1)print(min(a[l:r1]),end