CF1692H型号的设备有哪些特点？

本文共计463个文字，预计阅读时间需要2分钟。

div4未打，感觉我做的题时很难冲出来，最终面前还有+（7）+题。思路：考虑转化题意，即求得一段区间内不等于+（k）+的数的出现次数，减少+（k）+的出现次数，最小化+（k）+的出现次数。

div4没打，感觉我的做法做赛时很难冲出来，毕竟前面还有 \(7\) 题。

思路：

考虑转化题意，即求得一段区间使得不等于 \(k\) 的数的出现次数减去 \(k\) 的出现次数最小化。

显然如果 \(k\) 是选中的数，答案区间 \(l\) 和 \(r\) 必然有 \(a_l=a_r=k\)。

那么考虑枚举 \(k\) 并记录每个数出现的位置，即 \(g_{i,j}\) 表示 \(i\) 第 \(j\) 次在原数组 \(g_{i,j}\) 这一位置出现。

那么对每一个 \(k\) 枚举右端点，显然只有 \(n\) 种。

利用 \(g\) 数组对每一种 \(k\) 的右端点 \(r\) 找最优的左端点 \(l\)，那么就是对于 \(l<r\) 求 \(g_{k,r}-g_{k,l}+1-2\times(r-l+1)\) 的最小值；

解释一下：其中的 \(g_{k,r}-g_{k,l}+1-(r-l+1)\) 是求得这段区间内除以 \(2\) 的次数，再减去一次 \(r-l+1\) 就求得了最终要除多少次。