Misaka's Blog

前言 非常有趣的一道双指针好题，前前后后思考了好几天并写了一天半，终于实现了题解大佬的线性做法，做完这道题也让我对双指针以及函数单调性有了更深的理解。目前已经在所有 oj 上都 AC 了，正确性应该是没有问题的。这篇做题笔记思路与该大佬的题解基本一致，在细节方面有一些补充。 思路 这道题的切入点就是观察最终序列的翻转方式。 性质 1 观察可得性质 1： 最终序列被翻转的卡片一定是一段前缀和一段后缀。 证明 1 由于给出的 aaa 是升序的，所以翻转中间的卡片要么对最小值和最大值无影响（因为中间的 aia_iai​ 一定 ≥a1\geq a_1≥a1​，≤an\leq a_n≤an​），要么会使最小值更小/使最大值更大，而我们要求的是最小极差，所以翻转中间的卡片没有意义。 思考怎么用这个性质去解题。 设已经翻转了长度为 lll 的一段前缀和长度为 rrr 的一段后缀，可以定义如下变量： lmaxl=max⁡{bi}(1≤i≤l)lmax_l=\max\{b_i\}(1\leq i\leq l)lmaxl​=max{bi​}(1≤i≤l)； lminl=min⁡(min⁡{bi ...

题意 有 NNN 个球，每一个球有一个颜色 CiC_iCi​ 和价值 ViV_iVi​，现在要删除其中的 KKK 个球，使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。 数据范围 1≤K<N≤2×1051\leq K < N \leq 2\times 10^51≤K<N≤2×105 K≤500K \leq 500K≤500 思路 考虑 dp。 设计状态 fi,jf_{i,j}fi,j​ 代表不删除第 iii 个球，在前面删除 jjj 个球时最大的价值总和。 则 fi,jf_{i,j}fi,j​ 一定由前面的第 kkk 个球删除 (k,i)(k,i)(k,i) 之间的全部 i−k−1i-k-1i−k−1 个球转移而来，状态转移方程为 fi,j=max⁡{fk,j−(i−k−1)}(j≤K,i−j−1≤k<i,ci≠ck)+vif_{i,j}=\max\{f_{k,j-(i-k-1)}\}(j\leq K,i-j-1\leq k<i,c_i≠c_k)+v_ifi,j​=max{fk,j−(i−k−1)​}(j≤K,i−j−1≤k<i ...

前言 更可爱的阅读体验 思路 前置芝士：CF1764G1 的解法。 考虑在 G1 的基础上进行一个小小的优化。 G1 的最大询问次数是 3log⁡n3\log n3logn，其瓶颈在于当 nnn 为偶数时，我们需要预先额外花费 log⁡n\log nlogn 的时间去找到 nnn 的位置，从而消除后续询问里 nnn 的影响，因为这时 nnn 与 111 一样都具有除以 222 向下取整的结果唯一的性质。 而 G2 把最大询问次数限制到了 252525 次，所以我们需要找一种更高效的辨别 nnn 和 111 的方式来代替预先询问。 当我们对 [1,k][1,k][1,k] 和 [k+1,n][k+1,n][k+1,n] 两个区间进行询问时，除了 111 和 nnn 之外，两个区间里无法配对数字的数量一定是相等的，那我们可以分类讨论 111 和 nnn 的位置： 当 111 和 nnn 在同一个区间里时，这个区间里未配对的数字个数会比另一边大 222，于是继续处理这个区间就好。 当 111 和 nnn 分居在两个区间里时，两个区间里未配对的数字个数相等，我们只需要对其中一个区间进行一次 ...

思路 赛时没想出来贪心，于是写了爆搜但一直 WA，赛后发现是 dfs 函数忘记回溯了。 时间复杂度看起来是假的，但是跑得很快，推测是一堆卡牌里面能够进行匹配的数量实际上并没有那么多，实测最慢的点才 15ms，提交记录：link 爆搜的方法就是先用 (2n)2(2n)^2(2n)2 的时间预处理每两张牌是否能够匹配（匹配条件即两张牌中有且只有一张能赢过对方），然后再从第一张牌开始搜：对于每一张牌枚举和它匹配的另一张牌，标记之后接着搜下一张，搜不到就回溯继续搜，终止条件就是搜到第 2n2n2n 张牌时 return 1 以及无解时 return 0。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667constexpr int N = 40;char trump;int n;struct card{ char suit;int rank; inline void ...

题意 有编号为 000 到 N−1N-1N−1 的 NNN 个盒子。最初，盒子 iii 里有 AiA_iAi​ 个球。 高桥君将按顺序对 i=1,2,…,Mi=1,2,\ldots,Mi=1,2,…,M 执行以下操作： 将一个变量 CCC 设置为 000。 从盒子 BiB_iBi​ 中取出所有球并拿在手里。 当手里至少还有一个球时，重复以下过程： 将 CCC 的值增加 111。 将手里的一个球放入盒子 (Bi+C) mod N(B_i+C) \bmod N(Bi​+C)modN 中。 在完成所有操作后，确定每个盒子中的球数。 思路 题面中的操作可以被转化为以下步骤： 把位置 iii 的值归零； 将整个序列的值增加 ⌊AiN⌋\lfloor\frac{A_i}{N}\rfloor⌊NAi​​⌋； 将 (i,min⁡(i+Aimod  N,N)](i,\min(i+A_i\mod N,N)](i,min(i+Ai​modN,N)] 的值增加 111； 如果 i+Aimod  N>Ni+A_i\mod N>Ni+Ai​modN>N，再将 [1,i+Aimod  N− ...

题意 有一个包含 NNN 个关卡的游戏。起初，只有第 111 个关卡可以游玩。 在每个可以被游玩的关卡 iii 中，你可以进行以下两种操作： 花费 AiA_iAi​ 的时间通关，并解锁关卡 i+1i+1i+1。 花费 BiB_iBi​ 的时间通关，并解锁关卡 XiX_iXi​。 输出解锁关卡 NNN 所需的最短时间。 思路 看到这种题首先想到的当然是 dp，但对于这道题来说 dp 的转移顺序并不好确定，于是交了一发记忆化搜索却 WA 了。 这种情况下我们可以考虑建图，把关卡编号看成点，解锁关卡花费的时间看成边，然后我们就只需要对每个点 iii 到点 i+1i+1i+1 连一条长度为 AiA_iAi​ 的边，到点 XiX_iXi​ 连一条长度为 BiB_iBi​ 的边，直接以点 111 为起点跑最短路即可，最终到点 NNN 的距离就是答案。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263co ...

前言 感觉这次难度完全没有去年 12 月的铜组高，那个时候刚学三个月看到那几个题直接爆零，这次直接在研学路上用手机 ak 了。。 T1 - Majority Opinion 题意 给定一个长度为 NNN 的序列 hhh，每次操作可以选择一个 hhh 的连续子串，并且将其中的元素全部修改成子串中出现次数最多且超过其长度一半的元素，输出在经过若干次操作后，可以让哪些元素 hih_ihi​ 成为序列中唯一一种元素。 思路 看到 NNN 的数据范围是 2×1052\times 10^52×105，我们首先思考 O(N)\mathcal O(N)O(N) 的算法。 很容易想到，序列 hhh 中存在三个元素，其中有两个相同的 hih_ihi​（即序列中存在两个距离相隔不超过一个元素的 hih_ihi​） 是 hih_ihi​ 满足题面要求的充分条件，因为我们可以先把这三个元素全部修改为 hih_ihi​，然后就可以一点点将 hih_ihi​ 扩展到整个 hhh 序列里。 以下是充要条件的证明： 做法证明 假设 hhh 中距离相隔最短的两个 hih_ihi​ 之间间隔为两个元素或以上。 那么一个包 ...

题意 给定一个长度为 NNN 的序列 AAA 和整数 DDD，求出序列 AAA 中满足任意两个相邻元素之差的绝对值都不小于 DDD 的子串的最大长度。 数据范围 1≤N≤5×1051\leq N \leq 5\times10^51≤N≤5×105 0≤D≤5×1050\leq D \leq 5\times10^50≤D≤5×105 1≤Ai≤5×1051\leq A_i \leq 5\times10^51≤Ai​≤5×105 所有输入数据都是整数。 思路 显然是一道 dp 题。 状态设计&转移 用 fif_ifi​ 代表以 aia_iai​ 为结尾的 AAA 的满足要求的子串中的最大长度，则我们只要找一个符合要求的 jjj 并把以 aja_jaj​ 为结尾的最长子串接在 aia_iai​ 之前即可，于是可以得到以下状态转移方程： fi=max⁡{fj}+1 (j<i,∣ai−aj∣≤D)f_i=\max\{f_j\}+1 \ (j<i,|a_i-a_j|\leq D)fi​=max{fj​}+1 (j<i,∣ai​−aj​∣≤D) 但从 111 到 ...

前言 场上刚开始还天真的以为是个爆搜或者奇怪的背包，浪费了好久。。 思路 看到这个题我们首先想到的一定是暴力 dfs 枚举做菜品 a 还是菜品 b，但复杂度为 O(2ans)\mathcal O(2^{ans})O(2ans)，显然无法通过本题。于是我们来思考一下贪心做法。 实际上，这道题的题意可以简化成 nnn 个不等式，设我们最后做了 xxx 道菜品 a，yyy 道菜品 b，就可以表示成如下形式： a1x+b1y≤q2,a2x+b2y≤q2,⋯ ,anx+bny≤qna_1x+b_1y\leq q_2,a_2x+b_2y\leq q_2,\cdots,a_nx+b_ny\leq q_na1​x+b1​y≤q2​,a2​x+b2​y≤q2​,⋯,an​x+bn​y≤qn​ 并且注意到题意里 a,b,qa,b,qa,b,q 的取值范围都不超过 10610^6106，于是我们可以考虑枚举当前的 xxx 或 yyy（这里选择枚举 yyy），对不等式做变形，得到如下式子： x≤⌊qi−biyiai⌋(1≤i≤n,biyi≤qi)x\leq \lfloor \frac{q_i-b_iy ...