您当前的位置:首页 > 热点资讯 > 正文

复盘｜第337场周赛

时间：2023-03-19 21:52:33 来源：哔哩哔哩

【资料图】

偶位数

【模拟】按题意模拟（注意是从右到左算）。

【二进制模拟】题中是从低到高枚举，&1就是取最低位。不断取最低位，然后右移，直到等于0为止，这样可以取到每个比特位（^=1是1-0转换，可以避免写ans[i%2]）。

检查骑士巡视方案

【DFS】按题意搜索。

【模拟】按题意模拟（注意判断起点是否是0,0）。预处理，把每个数的坐标用pos数组存下来。

美丽子集的数目

【回溯】在枚举"78.子集"的基础上加个判断。在选择x=nums的时候，如果之前选过x-k或x+k，则不能选，否则可以选。代码实现时，用哈希表或数组来记录选过的数，从而O(1)判断x-k和x+k是否选过。

【DP】前置知识：乘法原理和同余[如果(x-y) mod k = 0则称x和y对模k同余，记作x≡y(mod k)]，如果两个数模k不同余则无法相差k，所以可以按照模的结果分组，每一组用哈希表/有序集合统计元素及其出现次数。每一组按照key从小到大排序后（设这些key组成了数组g），相邻的key如果相差k，那么不能同时选。设g的大小为m。考虑最大的数g[m-1]：如果不选g[m-1]，问题变成一个m-1个数的子问题。如果选g[m-1]:有2^c-1种方案，这里c为g[m-1]的出现次数；如果g[m-1]-g[m-2]=k，那么g[m-2]绝对不能选，问题变成一个m-2个数的子问题。如果g[m-1]-g[m-2]!=k，那么g[m-2]可选可不选，问题变成一个m-1个数的子问题。定义f[表示考虑前i个ky的方案数，可得转移方程：如果g[i]-g[i-1]=k，那么f[i]=f[i-1]+f[i-2]·(2^c_i-1)。如果g[i]-g[i-1]!=k，那么f[i]=f[i-1]·2^c_i。

执行操作后的最大 MEX

【贪心】前置知识：同余[x≡y(mod m)相当于x mod m + m = y mod m]。由于同一个数可以操作任意次，所以每个x=nums[i]都可以通过操作变成y，满足x≡y(mod m)。枚举mex，从0开始看有没有对0模m同余的数，有则把整个数通过操作变成0，否则答案是0，以此类推1,2……,n用一个哈希表统计(nums[i] mod m + m) mod m的个数。

标签：

复盘｜第337场周赛

偶位数

最新文章推荐

资讯中心

热点资讯