2024.11.7 模拟赛

题目：2024.11.7 题目

云淡风轻

有 $n$ 个数，第 $i$ 个数为 $a_i$，现需要进行若干次操作，每次操作选定 $[l,r]$ 与整数 $x$，使 $\forall i\in [l,r]$ $a_i\leftarrow a_i+x$。求让 $a_i$ 均变成 $0$ 所需要的最小操作数量。

---

采用很明显错误的骗分做法。不难发现 $3$ 个样例有 $2$ 个的答案都是不同 $a_i$ 的数量，因此突发奇想尝试了一番，采用 set 进行去重，然后直接 size 获取长度并输出即可。时间复杂度 $\mathcal{O}(n{\log }_{2}n)$，没想到最后竟然骗到了 $60$ 分，数据真水。

浅吟低唱

有长度为 $n$ 的正整数序列 $A$，每个数都不超过 $10^9$，令 $B_i=j_{\min }$ 满足 $i\le j\le n$ 且 $1\sim n$ 与 $i\sim j$ 的下标在 $A$ 中对应的元素所组成的去重集合是否相等，没有满足条件的 $j$ 即令 $j_{\min }=n+1$。现给出 $B$，求是否存在 $A$，若存在构造任意一种方案。

---

采取骗分解法。对于 $B_i=n+1$，很明显这是不可能的，直接输出无解。对于 $B_i=i$，这说明 $A$ 中每一个元素都是一样的，因此可以输出 $n$ 个 $1$。剩下的数据我们就直接通过 dfs 来搜出数组 $A$ 的每一种可能（每一个元素都是 $1\sim n$，很明显值域大了对答案没有影响），由于 dfs 时间复杂度 $\mathcal{O}(n^n)$，还需要 $\mathcal{O}(n)$ 的判断，因此总时间复杂度 $\mathcal{O}(n^n\times n)$。配上前面的骗分思路，可以成功获得 $25$ 分的嚎成绩。

知行合一

有 $n$ 个篮球，第 $i$ 个篮球的颜色为 $c_i$，质量为 $m_i$，可以进行若干次操作，每次操作对任意存在的球使其质量增大 $1$，并花费 $w$ 的钱。当 $m_i\ge k$，你需要再下一次操作之前将第 $i$ 个篮球卖出，获得 $p_{m_i}$ 的钱，保证 $p_i-p_{i-1}<w$，不保证 $p$ 单调不降。卖掉一个篮球之后，旁边两个篮球就会变为相邻，若这两个篮球颜色相等，则它们会合成一个篮球，质量为原先的两个篮球的质量和。合成的新的篮球可能需要立马卖掉。求卖掉所有篮球之后最多能够净赚的钱数。

---

赛时想到了区间 dp，但是不会做，骗分都没有想出来，代码都没有提交，文件都没有创建，$0$ 分。

处世不惊

有 $n$ 个结点的数，第 $i$ 条边双向连接 $x$ 与 $y$。现在有一颗棋子在结点 $r$，会有两个人进行以下游戏：第一个人先手，将棋子沿着两个人之前没有走过的恰好 $a$ 条边移动；棋子第二个人后手，沿着 $0\sim b$ 条任意边移动。游戏反复进行，知道第一个人没有任何一种方案能够移动，此时棋子的结点编号就是答案。第一个人希望答案尽可能大，第二个人希望答案尽可能小，两个人都会采取最优的策略，求最后的答案。

---

没有想到正解，因此仍然使用骗分解法。对于链且 $r=1$ 的情况，先将 $r+a>n$ 的特殊情况判掉，然后不难发现第一个人肯定会往后跳 $a$ 步，此时第二个人为了让答案变小会往前跳 $b$ 步，接着第一个人就跳不了了，因此答案为 $\max (r+a-b,1)$。对于其它情况直接输出 $1$。成功获得 $16$ 分。

总结

• 总分：$60+25+0+16=101$；
• 排名：$/$；
• 情况：一般；
• 总结：太垃圾了一道正解都不会。