题目：[[2024.11.7 题目]] ## 云淡风轻 有 $n$ 个数，第 $i$ 个数为 $a_i$，现需要进行若干次操作，每次操作选定 $[l,r]$ 与整数 $x$，使 $\forall i\in[l,r]$ $a_i\gets 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$； - **排名**：$/$； - **情况**：一般； - **总结**：太垃圾了一道正解都不会。