杂项练习笔记4(codeforces)(简单ver)

• 命名采用标准 [比赛简名] + [div.x] + [x题]
• CR: Codeforces Round
• ECR: Educational Codeforces Round

CR1012 d2 B

• 对这题我们发现，当某一个位置是1的时候，这个1必须到最上方或者最右方是连通的，我们只需要实现这个查询就可以了
  • 我们在读入数据的时候多开两个数组用于记录这个数与前一个数和上一个数的连通性，即
  • vx[i][j] += vx[i][j - 1] + vv[i][j];
  • vy[i][j] += vy[i - 1][j] + vv[i][j];
  • vv是输入数组
  • 则我们在查询的时候就可以查询这个数组该位置的值是否是i(j)来判断是不是到最右侧是连通的

---

CR1004 d2 B

通读题目发现我们需要将两个包内的数字一致，初始B包为空，我们可以进行如下操作

• 将A包的一个数移动到B包
• 在A包选择B包中有的数使该数 值+1

思路：

• 我们维护一个map，存下每个数出现的个数
• 从最大值开始沿整数遍历到最小值
• 对于遍历的每一个数i，我们设一个 ck 用于计算和保存需要多少 i - 1：
  • 检查 mp[i] - ck
    • 若其大于 0 ,表示该数足以填补前面所有需要的数，则将ck归零，mp[i]减去ck;
    • 然后计算mp[i] 能不能被二整除,不行的话则将 ck + 3
    • 若不大于零，则需要下一个数进行补充
      • 我们发现若要达到A，B袋子平衡态，则需要3个 k → k+1 和 1 个k+1才能达到
      • 若我们需要两个 k+1 ,则只需要多加一个 k 就行(即4个k)，因为本身已经处于平衡态，不需要额外的 k 保证平衡
    • 则新 ck 为 原ck - mp[i] - 1 + 3
• 遍历完成后检查 ck 是否大于0,大于零则说明不够形成平衡态，输出 No 即可

---

CR1007 d2 B

• 题目需求是让我们求一个长度为$n$的排列，这个排列前的$\{1,2,3,\cdots ,n\}$项的和都不能是平方数
  • 显然对一个长度为$n$的排列的和 $S=\frac{n(n+1)}{2}$ ，若该$S$为平分数，则长度为$n$的序列一定不能被构造出来
  • 我们考虑长度不为$n$的排列，先从1～n进行排列，若其中某下标$k$满足上面的平分构造，则我们交换 $a_k,a_{k+1}$
    • 而对于交换后是否一定满足其前缀和为平方数？我们可以这样理解，对于最小的两个平方数差为 4 - 1 = 3，而交换两个相邻数，前缀和+1，小于最小平方数之差。
• 输出构造完毕的排序即可

---

ECR176 d2 B

• 对长度为 $n$ 的数组 $A$ 有$k$次操作选择 $A$ 中的数，在根据这些数为原点任意扩散，我们需要知道选择的$k$个数和选择完毕扩散到的最后一个数的值的最大情况
  • 显然当 $k>1$ 时候，我们扩散到的最后一个数可以是选择后数组中的任意一个数，则我们只需要选择前$k+1$大的数做和即可
  • 当$k=1$时，我们注意到$A$序列两端中必有一端是最后被扩散的数，则我们只需要取除去两端外最大的数和两端中最大的数即可

---

CR1019 d2 B

• 贪心思路
  • 先在字符串加前缀”0”方便后续操作
  • 在字符串里寻找 “01” 与 “10” 并分别计数
  • 若不改变字符串，操作数为 n + cnt01 + cnt10
  • 当 “10” 数量与 “01” 数量之和小于2时候，直接计数即可
  • 否则看是否有字符串的数量大于 2 ，如果存在操作数就 -2，否则 -1

---

CR1005 d2 B

• 贪心 + 双指针
  • 我们需要寻找数组中最长的且数字只出现一次的子序列
  • 维护一个map用来保存数字出现几次
  • 在map为1的数下查找最长的子序列
  • 注意不要忘记当所有数字出现次数都大于2时候输出0

---

CR998 d3 D

• 贪心
  • 显然当数组已经排序时可以通过操作
  • 对每一次操作，都会将$\{a_i,a_{i+1}\}$变为$\{0,a_{i+1}-a_i\}$或$\{a_i-a_{i+1},0\}$,显然后者是不可取的
  • 因为构造出的第一个数是0，则我们若想一个非已经排序数字的开头开始按题目要求向后构造
    • 从第一个构造到最后一个，倘若可以形成非递减序列，则最后数组形式一定为$\{0,0,0,\cdots ,0,x\}$形式，则检查最后数组是否排序即可

---

CR997 d2 B

• 图与排序
  • 根据题目含义，我们可以知道，图中两个定点元素有边，则说明小的元素的下标值一定小于大的元素
  • 则根据这一点，我们可以先确定一个排序$[n,n-1,\cdots 2,1]$ 然后从第一个元素出发，如果发现该元素比其小的元素有边，说明这个元素下标应该比有边的元素大
    • 整个排序过程可以使用类似快速排序的思想完成
    • lambda = [&]( int a , int b ){ return (mp[a][b] == 1 ? a < b : a > b)};

---

ECR178 d2 D

• 这种题目属于典型的看了答案大彻大悟，不看答案一头雾水
  • 我们理解题目限制1,即我们操作后的元素和不能大于原数组和
  • 现在考虑一个理想数组的特性，一个大小为$n$的理想数组的和的最小状态应该是前$n$项质数组成的数组
  • 则我们只需要知道原数组和是质数数组前缀和的第几项就可以了
    • 但是直接做前缀可以有超时风险，我们可以先由大到小排序给定数组，在加和给定数组和质数数组，每一次加和的时候进行比较sumv >= sump ? ans = i + 1 :
    • 最终答案便是 n - ans

---