Thinking or Construction

Posted on Edited on Views:
  1. Duplicates 题意：给定 \(n \times n\) 的网格，其中每格数都属于 \([1,n]\) ，求最小的修改次数使得这个网格的每行以及每列都包含至少两个相同的数，并输出修改方案。
    2024.3.2 解： 我们将不符合要求的行和列画上直线，易观察到，当两个直线有交点时，将这个交点随便改成一个数（不是自己）就可以消除掉这两条直线，因此首先随便改完所有交点。当没有交点时，假设此时只有某些列不符合要求（行同理），我们遍历这些列i，随便选中一行0，如果这一行的所有数都相同，设为 \(a\) ，那么在需要修改的列的地方，统一改成另一个相同的数，设now != a 即 grid[0][i] = now，若这一行有两个不同的数，设为 \(a\) 和 \(b\) ，则将需要修改的grid[0][i]的 \(a\) 改成 \(b\)，\(b\) 改成 \(a\)，如果这个数即不等 \(a\) 且不等于 \(b\) ，那么随便改成 \(a\) 或者 \(b\) 都行
  2. Bit Counting Sequence 题意：设 \(p(x)\) 表示 \(x\) 的二进制表示中 \(1\) 的个数，给定数组 \(A\)，求 \(x\) ，使得 \(\{p(x), p(x+1), p(x+2), \dots , p(x+n-1)\}\) 与数组 \(A\) 相等，若无解输出 \(-1\)
    2024.3.2 解： 设 \(mn = \min_{i = 1}^{n-1}(a[i] - a[i-1])\)，则 \(mn\) 对应的 \(id\) 为 \(i-1\)，则与 \(a[id]\) 对应的数的二进制表示中，最低位必然有连续 \(1 - mn\) 个 \(1\)，在满足这个条件下，向连续\(1 - mn\) 个 \(1\) 前补一个 \(0\)，然后再补若干个 \(1\) 使得该数一共有 \(a[id]\) 个 \(1\) ，然后以此数 \(= ans\) 为基准，\(start = ans - id\)，从 \(start\) 开始依次与 \(a\) 数组的各个数比较 ( \(cnt(start+i)\) --算\(1\) 的个数 )，若全部相等则找到 \(x = start\)，否则输出 \(-1\) 。特判：若 \(a\) 数组里有 \(0\)，则 \(0\) 只能出现在第一个位置
  3. Find B 题意：给定正整数数组 \(a\) ，判断是否存在正整数数组 \(b\) 使得 \(\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i\) 且 \(a_i \neq b_i\)，一共有 \(q\) 次查询，每次查询为判断数组 \(a\) 的某个范围 \([l,r]\) 是否可以找到对应的数组 \(b\)
    2024.3.10 解：
    如果 \(a_i\) 是 \(1\)，那么 \(b_i\) 取 \(2\)，否则，\(b_i\) 取 \(1\)
    这样就能做到 \(\sum b\) 尽量小，如果 \(\sum b \le \sum a\)，那么肯定是可以通过一些骚操作满足条件的，否则再怎么样也不行
  4. 太阳之华 题意：有一块 \(n\times m\) 的方格区域，每个格子的颜色是红色或者蓝色，红方先手，可以选择一片红色的连通块，然后将与这个连通块有接触的蓝色方块染成红色，蓝方同理，若所有方格的颜色都被染成红色则红方胜利，都为蓝色则蓝方胜利，否则平局，给定初始局面，问最终胜负结果。
    2024.3.23 解： 如果红方一开始不能一步就胜利，那么就不会胜利，否则红方胜利，如果一开始不存在红色方块则蓝方胜利，否则平局
  5. Triangle Construction 题意：给定一个 \(N\) 正多边形，和一个数组 \(A\)，其中 \(A_i\) 表示第 \(i\) 条边上有 \(i\) 个点（将线段平均分成了 \(A_i + 1\) 段），求所有点能构成的不相交的非退化三角形的最大个数（注意三角形不能共用顶点）
    2024.3.26 解： 设 \(m = \max_{i = 1}^n(m, A_i),\ s = \sum_{i = 1}^n A_i\)，我们想象一下 \(m\) 相比于其他点的总和为无穷大时，显然可以构造出，以 \(m\) 所在边为底边，其他边上的点为顶点的三角形，且此构造的三角形个数是最多的，即当 \((s-m)\times 2 >= m\) 时，答案是 \(s - m\)，否则答案是 \(\lfloor {s / 3 }\rfloor\)，（当 \(m = 1\) 时，我们总是可以选择三条边上的点进行构造，当 \(m >= 2\) 时，可以用边 \(P\) 的最右边的两个点，和边 \(P + 1\) 的最左边的一个点来构造
  6. Bessie and MEX 题意：给定数组 \(a\)，请构造数组 \(p\)，使得 \(a_i = MEX(p_1, p_2, \dots, p_i) - p_i\)
    2024.3.31 解： 数据保证有解，当 \(a_i = 0\) 时，说明 \(MEX(p_1, p_2, \dots, p_i) - p_i = 0\)，即 \(MEX(p_1, p_2, \dots, p_i) = p_i\)，显然这是不可能存在的，\(p_i\) 既然存在于 \(MEX\) 当中，\(MEX\) 就不可能是 \(p_i\)
    当 \(a_i < 0\) 时，说明 \(MEX(p_1, p_2, \dots, p_i) < p_i\)，即添加 \(p_i\) 这个数没有对 \(MEX\) 产生影响，所以 \(a_i = MEX(p_1, p_2, \dots, p_{i - 1}) - p_i\) ，即 \(p_i = MEX(p_1, p_2, \dots, p_{i - 1}) - a_i\)
    当 \(a_i > 0\) 时，说明 \(MEX(p_1, p_2, \dots, p_i) > p_i\)，说明添加了 \(p_i\) 之后，使得 \(MEX\) 的值增大了，则 \(p_i = MEX(p_1, p_2, \dots, p_{i - 1})\)，又因为 \(a_i = MEX(p_1, p_2, \dots, p_i) - p_i = MEX(p_1, p_2, \dots, p_i) - MEX(p_1, p_2, \dots, p_{i - 1})\)，则 新的 \(MEX_i = a_i + MEX_{i-1}\)
  7. Buying Jewels 题意：请设置不超过 \(60\) 个摊位上物品的价钱，每个摊位上的物品价格相同且有无限个，使得用 \(n\) 枚硬币恰好可以购买到 \(k\) 件物品，或者告知这是不可能的，请注意，购买时会从第一个摊位开始购买到无法再买一件物品为止时再去第二个摊位，直到最后一个摊位
    2024.4.7 解： 若 \(n < k\)，则无解，因为连最低价格 \(1\) 也不能买到 \(k\) 件物品
    若 \(n = k\)，则必有解，我们只需要让第一个摊位的价格为 \(1\) 即可
    若 \(n > k\)，则第一个摊位的价格 \(p_1\ge 2\)，假设 \(n = p_1\times q + r\)，其中 \(q \ge 1, 0\le r < p_1\)，显然我们最多可以买到 \(q + r\) 个物品（在第一个摊位买到了 \(q\) 个，在其他摊位买到了 \(r\) 个），又因为
    \((p_1 - 2)(q - 1) \ge 0 \\ \Rightarrow p_1q - p_1 - 2q + 2 \ge 0 \\ \Rightarrow (\because p_1q = n - r) \therefore n-r - 2q \ge p_ 1 - 2 \\ \Rightarrow(\because r < p_1 \iff p_1 \ge r + 1) \therefore n - r - 2q \ge r - 1 \\ \Rightarrow 2(q + r) \le n + 1\)
    由于我们最多购买 \(q+r\) 件物品，所以 \(k \le q + r\) 所以 \(2k \le n + 1\)，所以若 \(2k > n + 1\) 则无解，否则我们令在第一个摊位买 \(1\) 个物品，在第二个摊位买 \(k - 1\) 个物品，即当令 \(p_2 = 1\) 时，\(n - p_1 = k - 1\)，所以 \(p_1 = n - k + 1\)，此时证：\(2p_1= 2n - 2k + 2 > n\) 即证 \(n - 2k + 2 > 0\)，又因为 \(n \ge 2k - 1\) 所以 \(n - 2k + 2 \ge 2k - 1 - 2k + 2 = 1 > 0\)，证毕