04-11 21:06 浙江大学 计算机类
关注
阿里云 研发 4.11 笔试
三道题
1. 给一个4X4的矩阵，矩阵有W和R两种元素，允许上下左右移动，问有多少种只经过R的最长的路径
太小了可以直接O(16!)搜索
2. 给一个长10^5的数组a，q次询问[l,r]区间内有多少位置满足 a_i>a_{i-1}, a_i>a_{i+1}
预处理前缀和，考虑一下边边上 O(n)
3. 问[l,r]区间内有多少数字满足其中1和2的出现次数不同，r在10^100数量级
应该有不少做法。转化为前缀差，即求[0,r]与[0,l]中满足要求数字的差。从大到小枚举每一位是什么，每次枚举时只枚举当前位，前面的位复制过来。举个例子：
123 -> 0xx,10x,11x, 120, 121, 122
单独处理123
枚举过后转化为O(logn)个有前缀但是对x部分只有位数限制的子问题，每个子问题中直接枚举1和2的个数，组合数算出所有可能的放法。每个子问题复杂度最多为O(logn^2)。实际复杂度大概在(logn^3)这个级别，但是常数巨大看上去马上就T。
1. 给一个4X4的矩阵，矩阵有W和R两种元素，允许上下左右移动，问有多少种只经过R的最长的路径
太小了可以直接O(16!)搜索
2. 给一个长10^5的数组a，q次询问[l,r]区间内有多少位置满足 a_i>a_{i-1}, a_i>a_{i+1}
预处理前缀和，考虑一下边边上 O(n)
3. 问[l,r]区间内有多少数字满足其中1和2的出现次数不同，r在10^100数量级
应该有不少做法。转化为前缀差，即求[0,r]与[0,l]中满足要求数字的差。从大到小枚举每一位是什么，每次枚举时只枚举当前位，前面的位复制过来。举个例子：
123 -> 0xx,10x,11x, 120, 121, 122
单独处理123
枚举过后转化为O(logn)个有前缀但是对x部分只有位数限制的子问题，每个子问题中直接枚举1和2的个数，组合数算出所有可能的放法。每个子问题复杂度最多为O(logn^2)。实际复杂度大概在(logn^3)这个级别，但是常数巨大看上去马上就T。
全部评论
JZlove
四川大学 计算机类
第三题数位DP模板题，没接触过不好想
分享
相关推荐
阿里云一面83人在聊 点赞 评论 收藏
转发
点赞 评论 收藏
转发
04-23 18:54
门头沟学院 计算机类 点赞 评论 收藏
转发
04-19 19:29
门头沟学院 计算机类 点赞 评论 收藏
转发