Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"hhc0716","updateTime":1697190051000,"title":"20231013 模拟赛题解+总结","dislikeCnt":0,"content":"# A 线索(clue)\n\n水题。\n\n暴力判断即可。\n\n# B 灯塔(light)\n\n## 形式化题意\n\n你有一个 $M \\times N$ 的矩阵。\n\n现在,对于每一个 $1 \\le i \\le M$,作如下操作:\n\n- 选择连续的 $K$ 列,然后将这一行和下一行(如果有的话)的这 $K$ 列打上标记。\n\n最后求出被打上标记的数的和的最大值。\n\n## 思路\n\n### XB-10(B-40)\n\n\t对于 $10\\%$ 的数据,满足 $K \u003d N$。\n\t\n这意味着,我们能够将所有数都打上标记(事实上,在 $2K \\ge N$ 的时候,我们只会舍弃第一行 $N - K$ 个数,而且这些数是第一行的前后缀(这不废话吗))。\n\n于是直接所有数加在一起,喜提 $40$ 分(事实上十个点有四个都是这样的点)!\n\n### B-60\n\n\n好了好了,回归正题。\n\n这个题意,一看就很 dp。\n\n于是就可以掏出 dp 的吉祥六宝:\n\n状态:\n\n$(i, j, sum)$ 表示刚刚选择了 $\\lbrack j, j + K - 1 \\rbrack$ 这些列,并且正在考虑第 $i$ 行。\n\n因此,$j \\in \\lbrack 1, N - K + 1]$。\n\n转移:\n\n$(i, j, sum) \\rightarrow (i + 1, k, sum\u0027)$。\n\n初始状态:\n\n$(0, 0, 0)$。\n\n这也是唯一一个 $j$ 为 $0$ 的合法状态。\n\n目标状态:\n\n$(N, j, sum)$。\n\n拓扑序:\n\n$i$ 从小到大。\n\n附带属性:\n\n- 最大化 $sum$。\n\n然后加前缀和个优化,就可以开开心心的写出 $60$ 分了。\n\n### B-100\n\n和 B-60 很像,只是加了一个几行的前缀后缀优化。\n\nAC。\n\n# C\n\n## 形式化题意\n\n你有 $N$ 个二元组 $(L_i, D_i)$ 组成了一个环。\n\n每次你可以选择一个二元组(设它是第 $i$ 个),然后删掉这个二元组及其后面的 $L_i - 1$ 个二元组。删完之后,你获得 $D_i$ 个金币。\n\n最大化你最后(也就是无法删除二元组的时候)所拥有的金币。\n\n## 思路\n\n### C-30\n\n全排列搜索删的顺序即可。\n\n### C-50\n\n在正式讲 C-50 之前,需要证明一个关键命题:\n\n你可以按某种顺序选择 $(i_1, i_2, \\dots, i_K)$ 并删除它们当且仅当 $\\sum \\limits_{j \u003d 1}^K L_{i_j} \\le N$。\n\n证法如下:\n\n考虑数学归纳法。\n\n先定义两个在原来的环中编号分别为 $i, j$ 的二元组的距离为 $\\lvert i - j \\rvert$。\n\n接下来定义 $S_j$ 表示 $i_j$ 到 $i_{j + 1}$(如果 $j \u003d N$,则为 $i_1$)的距离。\n\n我们已知 $\\sum \\limits_{j \u003d 1}^K S_j \u003d N,\\sum \\limits_{j \u003d 1}^K L_{i_j} \\le N$。\n\n首先只有一张卡牌时显然成立(直接删即可)。\n\n然后对于选了 $K$ 张卡牌的情况:\n\n$$\n\\because \\sum \\limits_{j \u003d 1}^K S_j \u003d N,\\sum \\limits_{j \u003d 1}^K L_{i_j} \\le N,\n$$\n\n$$\n\\therefore \\exists j, S_j \\ge L_{i_j}.\n$$\n\n此时可以将这个 $j$ 删去,于是变成了 $K - 1$ 张卡牌的情况。\n\n而且我们惊奇的发现:\n\n$$\n\\sum \\limits_{l}^{l \\ne j \\land 1 \\le l \\le K} S_l \u003d N - L_j, \\sum \\limits_{l}^{l \\ne j \\land 1 \\le l \\le K} L_{i_j} \\le N - L_j.\n$$\n\n也就是说,删除完这个卡牌的情况,还可以用相同的方式继续删,直到只剩一张卡牌。\n\n$\\text{QED}$\n\n于是,在完成证明之后,就可以写一个 $O(2^N)$ 的暴搜了!\n\n### C-100\n\n在上面那个关键命题被证明成立后,剩下的就是模板了。\n\nAC。\n\n# D\n\n## 思路\n\n### D-50\n\n直接模拟即可。\n\n### D-100\n\n其实可以先模拟一轮,然后再一轮一轮模拟(记得处理方向)。\n\n$O(N + T)$。\n\n### D-100\u0027\n\n使用了倍增的思想,ST 表的架构。\n\n可以倍增预处理,然后二进制分解并处理增量。\n\n是个周期题都可以这么做。\n\n$O(N + \\log T)$。\n\n### D-100\u0027\u0027\n\n其实可以先模拟四遍。\n\n四遍过后,机器人的方向一定会回到刚开始的方向。\n\n于是将四遍四遍的部分整个提出来,在模拟剩下的部分。\n\n$O(N)$。\n\n# 总结\n\nA 水题。\n\nB 一道标准的绿题 dp,考基础 dp,也考优化,是一道好题。\n\nC 一个模板背包加上一点数学。\n\nD 典型的找规律题目。\n\n# 彩蛋\n\n最后一句话,我说的,被加密了(我不会告诉你是用什么加密的)。\n\nVlZaU1RsSXhhRmhUTVVWelNVVjBXRk14WTNOSlJYQlZURU5DV0Zkc1RsbFJhMlJVVVZOM1oxWXhUa2hTUms1RFNWRTlQUT09\n\n[原题面](http://192.168.10.251/d/campb2023/file/325/problem.pdf)","threadId":172870,"likeCnt":0,"createTime":1697183746000,"isWorkbook":false,"viewCnt":119,"openness":2,"fav":false,"id":4183,"trustable":false}