错题补题解1

由于蓝桥杯国赛已经打完 下半年区域赛没有名额 所以已经是正式退役了 下半学期准备开始备战考研了 但是并不想完全停下算法刷题 所以会保持每天一题的刷题量维持手感(网瘾大)然后会记录一些做错了且需要看题解并且学到一点点东西的题目 自己写一遍题解 写了十个题就会发一篇题解

洛谷

动态规划入门专题

动态规划问题通常要先想清楚5个要素：

1.状态定义：这个dp设计的定义是什么 为什么这么设计

2.状态转移方程：从哪里转移过来

3.初始化：为什么dp[0]可以设为1或者设为0 这些边界是怎么想到的

4.遍历的顺序怎么确定 为什么这么定

5.最终答案在哪

P2842 纸币问题 1

这里我们要求出最少使用的纸币张数

所以我们的dp的状态定义就是：到达当前金额时 最少的纸币张数

状态转移方程就是从dp[j-num[i]]转移过来 找出最小的dp[j]且我们要找最少的纸币张数 所以转移方程dp[j]=min(dp[j-num[i]]+1,dp[j])

因为我们要取最小值 所以dp中的所有元素初始化都为INT_MAX

因为当金额数为0的时候 我们能用0张纸币构造出 所以dp[0]=0

由于我们是可以反复选择一个金额 所以是完全背包 完全背包金额应该从小到大枚举 这样才能保证被重复使用

dp的答案就是dp[w]

P1802 5 倍经验日

从题目中可以看到我们要选择不同的别人然后使得经验最大化 很容易想到01背包 但是状态该怎么定义呢

我们一开始将lose win和count都存到一个数组中 由于有多组数据 所以是二维数组 其中内部的数组是固长为3

我一开始定义的是for循环j到num[i][2] 然后dp[j]=max(dp[j]+num[i][0],dp[j-num[i][2]+num[i][1]) 然后提交也是直接WA了

后来我发现这段代码的弊端 我的for循环从j到num[i][2] 但是当我药水不够直接输 我还是有经验可以拿的 但是我的代码没有考虑到这一点 所以改进之后for循环从j到0 然后在里面写判断语句单独判断即可

Codeforces

构造题专题

P1909B. Make Almost Equal With Mod

题意很简单 就是给数组中的每个元素都模上同一个值使得恰好有两个相同的余数 首先我们很好想到根据两个不同的余数分成两个块 既然分块且仅有两个 那么很好想到奇偶性的问题 当奇数时模2等于1 偶数时模2等于0 这样就可以实现目标了

重点是当数组中全是奇数或偶数的时候该怎么办 一开始我将奇数和偶数全排列出来 一边是1 3 5 7 9 偶数是2 4 6 8 10 我发现都用4来模也可以区分出各个余数 但是做完发现不对 如果数组中全是4的倍数模4也就是全0 这不是想要的结果

我们知道当a%k=x时 a%2k=x或x+k(因为a%k=x意味着a可以写成t*k+x 当t为偶数则为x t为奇数则为k+x) 通过这个性质我们可以构造出我们想要的只有两个余数的结果 然后我们怎么找我们的k呢

其实我们只需要依次尝试 k=2²、2³,…,2的57次方即可 因为当a%k=x时 a%2k只可能出现还是全部为一个余数或者出现第二个余数的可能 不会出现第三种余数 所以就按这个顺序找下去一定能找到我们想要的k

可能这样说还是不太直观 题解中有一个很直观的图：

将数组中的元素都转换成二进制 当k=2时 我们其实只考虑二进制的最后一位 所有元素在这一位上都为1 所以模2都是相同的 此时我使k变为k² 在二进制里便是往前进一步 此时用元素模4只考虑二进制的最后两位 但由于我们先前已知最后一位相同 所以实际上只需要看倒数第二位 这一位上全为0 所以所有元素模4的余数还是都相等的 继续往前进 以此类推 当k=16时 5个元素中的倒数第四位有所不同 余数的结果变成了两位 所以找到k=16 由于我们只考虑每一位的变化 每一位只有0和1两种选择 所以我们能保证当余数数量发生变化时 一定是变成两个而不是直接跳到三个及以上

1433D - Districts Connection

这道题的思路很好想 我们将不一样的团伙连在一起 然后将相同的团伙连在不一样的团伙上面 主要是代码实现的问题

一开始用了各种各样奇奇怪怪的数据结构 结果看了题解发现只需要一颗树结构即可(甚至只是用一点思想)我们将第一个元素设为根节点 在后面如果有与他不一样的元素就将它成为根节点的子节点 遍历完一遍之后只存在与根节点相同的元素了 然后我们将剩下的元素插到任意一个子节点上即可 由于一共n个元素且是树形结构 所以边的个数一定是n-1满足题意

1339B. Sorted Adjacent Differences

这道题一开始做的感觉很奇怪 很明显的看出需要用差值来排序 但是如果排完序后按照差值来排序了 位置发生了改变 差值排序被破坏了 如果预处理每一个元素与其他元素的差值 存在一个二维数组中 那么时间复杂度就是On² 时间复杂度又超了

百思不得其解之下看了一眼题解 发现居然有如此惊为天人的构造方法

这是一个排序完后的数组 我们可以发现通过这种摇摆的方式差值一定是单调不递减的 满足题目的要求 所以遇到这类需要排序的题最好还是画个图 直观一些或许就有想法了

1497B. M-arrays

这题思路很好想到 要相邻的两个数之和能被m整除 也就是其和模上m等于0 所以也就是这两个元素分别模上m的和要等于m，自然很好想到将头尾两个一一对应，也就是把a%m==1的和a%m==m-1的放一组以此类推，要注意当m是偶数时，a%m=m/2的元素是单独一组的，以及当a%m==0时，也是单独一组的，然后就是统计其余组的个数了

作者错误的点在于统计个数的情况，只考虑了两个相应元素个数的差值问题，但是没有考虑如果当x和y都等于0时，是直接跳过的，而不是加入个数中，直接吃了一发WA😢

1635C. Differential Sorting

这道题是贪心的思路 但是作者一开始贪心思路错了 想着只需要从左向右移动看后面连着的两个元素然后更新即可，但是发现前面的还是可以继续更新来满足升序的状态的

这道题的正确思路应该是看最后两个元素是否是升序，如果为降序一定是-1 因为最后两个元素没法修改 在最后两个元素为升序的情况下我们考虑两种情况 一种是a[n]>=0 另一种是a[n]<0 因为最后两个元素是固定的 所以前面所有元素都可以写成a[n-1]-a[n]的形式 如果a[n]>=0那么a[n-1]-a[n]就一定小于a[n-1]这样将前面所有元素都修改就能达到不降序的方案了 如果a[n]<0则会导致a[n-1]-a[n]>0这样就不行 也会有人会问 我一定需要用最后两个元素来修改吗 不能用前面其他元素修改吗 注意到如果a[n]<0 那么想达成非递减的数组 也就意味着前面的所有元素都至少要求小于0 所以对于任意一个i如果大于i+1的情况 a[i+1]-i+1后面的任意元素都大于a[i+1]所以无法将a[i]改写成比a[i+1]小的元素

1455B. Jumps

这道题第一眼感觉很简单 我只需要不停的跳 直到跳到第一个大于x的点 然后再减去当前点减去x的操作数即可(操作2)

但是后来发现当x等于4时 我的操作数可以是3而不是5(0-1+2+3) 被逼无奈下只好去阅读题解

题解的思路很有意思 首先如果我们一直走第一步这是一个等差数列大家都知道 当我们走到第一个大于x的元素num的时候 假设最后一步为k 那么这个元素的前一个元素为num-k

我们可以知道num-k<x<=num 如果num正好在x上那么很好 这几步跳跃的就是最佳答案 如果num>x呢 我们将前面的任意一个操作修改 都会使最终答案减少2~k+1的操作(比如我将第一步+1修改成-1 总距离就-2了 如果我将第二步+2修改成-1 总距离就-3了)这样一来我们是可以按照以原来的操作数将最终答案无痛修改成x的 可能有人问为什么k+1就行 不会超过这个上限吗 由于我们知道num-k是小于x的 所以num小于x+k 因此不会超过上限 只要num比x大2及以上 那么我们就可以无痛修改成x 如果num只比x大1 那么是需要增加一次修改的

1335D. Anti-Sudoku

第一次做这种题有点懵圈了 左看右看找不出什么规律 看了题解恍然大悟(算法题实在太好玩了)

首先我们知道对于数独来说 每一个元素一定是不同行不同列不同块的 且有9个元素 我们这里拿1举例 每一行都仅有1个1 每一列都仅有1个1 每一个块中都仅有1个1 那么我们直接将另一个元素转换成1即可 因为对于其他元素来说也是这个性质 每一行每一列每一个块中仅有一个元素 所以就将其转化成1 这样每一行每一列每一个块中就有两个1了 且操作次数不超过9

1521B. Nastia and a Good Array

这道题我的思路是将相邻的两个判断最大公约数是否为1 如果不是 就将较小的元素改为比它大的质数 并且标记这个质数已经被使用过 如果是就下一个 当下一个相邻的两个元素的最大公约数也不为1 那么继续将较小的元素改为比它大且未被标记过的质数 这样做就要用到欧拉筛 并且欧拉筛的的参数是2×10的九次方 这样就超上限了 这样就得用到打表的技巧来提前存储质数数组 这样过于麻烦 在询问ai知晓我的思路没有问题 这么写是可以ac之后就直接看题解找更优方法了(如果按照原来的思路写感觉代码至少得写一小时...)

题解的思路非常清奇 首先gcd(a,b)=1必然意味着这两个元素互质 我一开始的思路是将其中一个元素改成质数 这样会要求欧拉筛 代码实现较为复杂 但是相邻的元素互质并不一定需要有一个数为质数 当两个元素是相邻的元素即可(也就是k和k+1) 根据这个性质我们可以将整个数组替换为一个连续的数组 但是从哪里作为起点呢 题目中写道：

也就是说两个元素中 小的元素的状态会更加稳定 我们可以以一个小的元素作为min的值 将较大的元素修改 根据这样的思路 我们找出数组中最小的元素 以它为起点向两边扩散 使相邻元素都是数值相邻的元素 依次递增

1381A1. Prefix Flip (Easy Version)

这道题非常的有意思 作者在刚开始做的时候也是完全没思路 想着从右往左会更稳定一些 但是数组在前缀操作之后会发生反转 这样就不具有稳定性了 难以贪心 迫不得已下点开题解(实际题解第一遍也没读懂)

首先我们进行前缀的操作记为函数flip(i) 当我们进行一次操作时 会将前缀整体翻转再反转 这里有一个很有意思的点就是如果翻转再翻转 就变回原数组 反转再反转也会变回原数组 所以当我们调用两次flip(i)时 前i个元素实际上是不会改变的

那么这样有什么意义呢

意义就在于当我第一次进行flip时 我可以将前缀操作中的最后一个元素调到第一个元素的位置上 对其进行单独的前缀操作 也就是翻转操作 这样对于这个元素来说 调用了三次flip 那么实际上它是能达到翻转的效果的

举一个例子

比如这样两个数组 第一个数组a1 a2 a3 a4 第二个数组a1 a2 a3 a4非(学过数字逻辑的都知道啥意思 就是如果a4是0 a4非就是1 反之亦然)当我们第一次调用flip时候 第一个数组变为了 a4非 a3非 a2非 a1非 此时我们调用flip(1) 仅修改第一个元素(a4非变为a4)然后我们再调用一次flip(i)这样就能使两个数组相等了 通过这个性质就可以在最多3n的情况下修改a数组为b数组