1.python学习学习一些基本概念列表元素有序可重复有序 元素存入的先后顺序会被永久保留并且每个元素有固定下标索引可以按位置取值。下面是列表的一些基本用法字符串操作元组2.算法刷题刷新题:MC0569重金求死士异或规则如图分成k1*k2块 i,j相当于给矩阵标号 li,lj是每个矩阵的左上角的数代码MC0570数据量到1e4有简便思路 就是找到每一个数左边倒着第一个比他小的数和右边第一个比他大的数pre存左边 last存右边 但是要注意一定要加上pre[i]last[i] 因为当prev[i]3 last[i]为0不满足代码条件MC0402 括号序列注意只能交换相邻位置 思路就是找(左边的)的数量 如果)更多就需要第一个左括号移动到第一个右括号的位置 的数目就是(需要移动的距离交换次数MC0405可以发现规律 第一个永远取不到我们就从第二个开始 如果是正数就直接收走 后面的变成第二个 如果是负数就把第一个销毁第二个就变成第一个一直循环 其实就是以后面所有正数相加MC0406涵盖多个知识点1.最小公倍数不满足取模分配律不能边取模边求LCM2.快速幂写法(a^b mod MOD 二进制原理)a的b次方 为了防止溢出所以要用快速幂并取模3.不能用LCM 所以只能用质因数分解法多个数的最小公倍数 收集所有出现过的质因子每个质因子取最高次方全部相乘。所以要分解质因数 用map容器存储每个质因子出现的最高次数4.拓展求最大公因数(gcd)和最小公倍数(LCM)的方法lcma*b/gcd(a,b)求最大公因数 求最小公倍数整体代码如下MC0410 拯救圣莲池这道题使用排序分层批量计算法每一层每一层一批灵力值相同的花朵进行计算 到达下一个灵力值的花朵可能相等也可能不等代码如下MC0412 符文方阵矩阵可以不按照给的顺序乘 但是不能反着来 比如a1*a2!a2*a1代码实现deque容器的使用不能用三重循环 要优化一下MC0417 哨岗逆序对看题目n的范围很大但是a得范围很小 所以考虑用计数统计法 每一次输入一个数统计前面已经输入比它大的数的数量 加起来取模 cnt数组存储的是当前已经输入的数值的数量unordered_map是无序的 map是按照key升序的二维前缀和简单题MC0422 包含1的子串有五种解法 第一种暴力超时第二种 补集法 所有子串数目减去全由0组成的子串第三种 分块计数法 每一个1左边到前一个1下一个位置的字符串与右边到末尾的字符串组合杜绝重复第四种 线性dp法 类似于用dp[i]存储以i为结尾的至少包含一个1的子串数量第五种 滑动窗口双指针法 固定右端不断收缩左端这种方法可以统计至少大于k个1的子串数量MC0423 铺砖块用的砖块周长不能为4的倍数 所以砖块一定是一边奇数一边偶数 找规律 砖块的面积一定是偶数所以房间的面积一定不是奇数 否则不成立 这样我们就可以发现规律 房间面积一定要是偶数 所以房间的两条边不能都为奇数 从面积奇偶性来判断MC0424MC0426用Floyd算法建有向边 找是否能到达 开reach数组把每个单词的首字母和尾字母转换成数字更方便 并且只需要循环到26 记得每次都要清空数组双指针法MC04331.本题核心转化所有子区间排序交换次数总和 每一组「1 在前、0 在后」逆序对各自会被多少区间包含的次数之和2.单个逆序对((p,q))p是 1 的位置q是 0 的位置能被统计的区间数量 左端点可选数量 × 右端点可选数量3.previ 维护当前 0 左侧全部数字 1 的下标总和代表所有合法左端点总可选量4.n-i1 代表以当前 0 的位置 i为左边界、向右延伸的全部合法右端点可选数量5.二者相乘 当前 0 与左侧所有 1 构成的全部逆序对一共会被多少个子区间统计累加得到全局答案6.遇到数字1就把下标加入previMT2001 幸运的3每个数的各个位置数字和加起来是3的倍数就行 也就是说余数都为0的可以匹配 余数1和余数2的也可以匹配P1596 水坑计数DFS写法BFS写法 与DFS思路类似动态规划P1216 数字三角形逆推法 从下往上找最大 最上面的那一个一定是最大值从下向上找两个能连起来的数的最大值与自身相加 一步一步向上最终一定能汇总代码如下B3736 最长上升子序列简单dp板子P1439最长公共子序列以数据量较小为例 否则需要优化dp存的是前i,j个字符里的最长公共子序列的长度(注意不是子串)遍历两个序列当前数字相等就继承左上角值加一(dp[i-1][j-1]1)不等就取上方、左边的较大值(就是max(dp[i-1][j],dp[i][j-1])最终右下角存最长公共子序列长度。最长公共子串并改造上面题目输出ACC用dp[i][j]存储以i和j两个位置为结尾的最长公共子串长度状态转移图代码如下MC0571线性DP 开三个数组分别存储当前列全白、涂第一行、第二行的情况 dp存储对应的前i列方案总数最宽松情况是i-d0的时候 当前涂第一行前面的方案数就应该是不涂或者涂第二行 这样才能满足条件代码和一些解释如下复盘日志三中错题:主要是二进制的转换知识P1219八皇后二维前缀和p1149P1644 跳马问题判断好范围P3799用数组记录每个长度的数量 找到两个长度一样的 然后再根据这个长度找任意两根长度能组成这个长度的木棒 记得每次求余P1443 马的遍历BFS算法 使用dist数组记录每一位置的步数 注意要给初始位置vis为1MC0550必须要优化成如下代码形式才能过
