Deep欠揍AI，正式出世！ 链接我就放在这了，大家自行体会。 Deep欠揍AI（R2.1.5） Deep欠揍AI（R2.1.6） Deep欠揍AI（R2.1.7） Deep欠揍AI（R2.1.8） Deep欠揍AI（R2.1.9） Deep欠揍AI（R2.2.1）

？

签。 天啊 tilingtilingtiling 升绿了，天啊我的黄怎么没变少？！（又降回来了） 破案了，P17250 签到 从灰变黄了（应该是这样） P17242 [IOI 2026] 方块游戏 / tiling 这个和某个游戏很像，就是有 2∗22*22∗2 的方块，每个方块都由 黑/白 组成，其中每个方块必有一个白，但不一定只有一个，给出一个 2n∗2m2n*2m2n∗2m 的棋盘，我们要使把所有的方块放完后棋盘内任意位置都不出现 2∗22*22∗2 的黑色。 构造题，看到的时候先乱搞拿了大概 50pts50pts50pts 左右（因为洛谷的评测机是捆绑测试的），后面发现不是把每个白放在同个方位就行，因为不能转。 看了 一位巨佬的题解 后得到了思路，我们把每个方块的白色都朝着没填的地方放，对于每个 2∗22*22∗2 的黑，只有 222 种可能出现。 情况1： 它由两个方块的 上下/左右 两黑拼成，就是 黑黑 ———— 黑黑 由于上面白色是靠近中心的，下面的白色是靠近中心的，那么这四个里面必出一个白，不成立。 情况2： 它由四个方块的不同角拼成，就是这样 黑|黑 ———— 黑|黑 但由于我们都是把白色的放在靠近中心的地方的，那么左上的方块的右下角必然是白，其余同理，这样这四个里面也必出一白，不成立。 时间复杂度 O(N2M2)O(N^2 M^2)O(N2M2) ，能过。

不对，谁告诉你ACGO有GESP这个来源了 ？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

自2025年7月13日@阿帽AAA在U27111. 轻轻松松拿满分(原名张老师真帅)点下第一个提交并弹出未通过以来，本党派一直以压低张老师真帅的正确率为目标付诸行动，今天是开战的第400天，错误中央在这里向所有参加过战争的战友们致以崇高的问候。

目录[1] 持续更新中。 现在是线段树。 可以在评论区提出改进建议，比如格式之类。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图论 最短路 堆优化 dij[2] 未优化 dij[3] SPFA[4] Floyd[5] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树论 树的直径[6] LCA[7] 树上差分[8] 换根DP[9] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 生成树 最小生成树[10] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 动态规划 背包 01背包[11] 完全背包[12] 多重背包[13] 分组背包[14] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 序列DP 最长上升子序列[15] 最长公共子序列[16] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 字符串 字符串哈希[17] 最长回文子串[18] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PMT及其应用 最长公共前后缀[19] KMP[20] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 数据结构 ST表[21] 树状数组[22] 并查集[23] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Trie 字典树[24] 最大异或值对[25] 最长异或路径[26] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 线段树 单点修改区间查询最值[27] 区间修改+区间查询求和 线段树[28] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 目录 ↩︎ 2. 堆优化 dij ↩︎ 3. 未优化 dij ↩︎ 4. SPFA ↩︎ 5. Floyd ↩︎ 6. 树的直径 ↩︎ 7. LCA（倍增实现） ↩︎ 8. 树上差分 ↩︎ 9. 换根DP ↩︎ 10. 最小生成树 ↩︎ 11. 01背包 ↩︎ 12. 完全背包 ↩︎ 13. 多重背包 ↩︎ 14. 分组背包 ↩︎ 15. 最长上升子序列 ↩︎ 16. 最长公共子序列 ↩︎ 17. 字符串哈希 ↩︎ 18. 最长回文子串 ↩︎ 19. 最长公共前后缀 ↩︎ 20. KMP ↩︎ 21. ST表 ↩︎ 22. 树状数组 ↩︎ 23. 并查集 ↩︎ 24. 字典树 ↩︎ 25. 最大异或值对 ↩︎ 26. 最长异或路径 ↩︎ 27. 单点修改+区间查询最值 线段树 ↩︎ 28. 区间修改+区间查询求和 线段树 ↩︎

考试题解 考试题解链接 1. STACK 栈 特点： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. QUEUE 队列 特点： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. DEQUE 双端队列 单调队列最常用： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. PRIORITY_QUEUE 优先队列 默认是大根堆： 小根堆： 此时： 最简口诀： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ PTA-LITTLE BIRD 琪露诺 暴力DP 单调队列DP优化 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 单调队列笔记 1. 作用 求长度为 kkk 的滑动窗口中的最小值或最大值。 当前窗口： [i−k+1,i][i-k+1,i][i−k+1,i] ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 核心思想 deque 中存下标。 求最小值时，维护： 所以： 就是当前窗口最小值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 三步操作 窗口形成后： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 为什么队尾可以删除 假设队尾是 5，当前来了 3： 3： * 比 5 小； * 比 5 更晚离开窗口。 所以以后 5 不可能成为最小值，可以直接删除。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 5. 完整代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 6. 求最大值 最小值： 最大值改成： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 7. 复杂度 每个元素最多入队、出队一次。 时间复杂度： O(n)O(n)O(n) 空间复杂度： O(k)O(k)O(k) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 8. 口诀 最小值：维护单调递增。 最大值：维护单调递减。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 单调栈学习笔记 一、什么是单调栈 单调栈本质还是一个普通的 stack，只不过我们通过不断弹栈，使栈中的元素保持单调。 常见两种： 单调栈最常解决的问题： * 左边第一个比我大的元素 * 左边第一个比我小的元素 * 右边第一个比我大的元素 * 右边第一个比我小的元素 * 柱状图最大矩形 * 统计某个数作为区间最大值、最小值的贡献 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、核心理解 不要死记“维护单调性”。 可以理解成： > 栈里面存的都是“还没有找到答案的人”。 例如要求： > 右边第一个比自己大的元素。 当前来了一个新元素 a[i]。 如果： 说明当前元素就是栈顶元素一直等待的答案。 所以： 继续看新的栈顶。 直到栈顶不比当前元素小，再把当前元素入栈等待自己的答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、右边第一个比我大的元素 例如： 答案： 所以： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 模拟过程 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、为什么栈是单调的 还是求： > 右边第一个比我大的元素。 代码： 所有比当前 a[i] 小的元素都会被弹掉。 所以最后留下来的栈顶一定满足： 然后再把 i 放进去。 因此栈中的值自然形成： 也就是一个单调递减栈。 所以： > 不是为了单调而单调，而是“已经找到答案的人被弹掉”，剩下的人自然形成了单调性。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、四种经典模板 1. 右边第一个更大 从左往右扫： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 右边第一个更小 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 左边第一个更大 当前元素把比自己小的全部弹掉。 弹完以后，栈顶就是左边第一个更大的元素。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 左边第一个更小 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、怎么判断扫描方向 可以简单记： 求右边的答案 通常： 当前元素帮助前面的元素得到答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 求左边的答案 通常： 先弹掉不合法元素，然后直接看： 就是左边最近满足条件的位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、为什么是 O(N)O(N)O(N) 虽然代码里面有： 看起来像 O(n2)O(n^2)O(n2)。 但是每一个元素： 例如： 元素 1 被弹掉以后，就永远不会重新进入栈。 所以所有 while 加起来最多弹 nnn 次。 因此总时间复杂度： O(n)O(n)O(n) 空间复杂度： O(n)O(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 八、经典应用：发射站 如果一个发射站的能量，会被左右两边最近且比它高的发射站接收。 当前处理第 i 个位置： 被弹出的元素： > 当前 i 就是它右边第一个比它高的位置。 弹完以后： 此时栈顶： > 就是 i 左边第一个比它高的位置。 模板： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 九、区间最大值贡献 很多题会求： > 所有子区间最大值之和。 对于每个 a[i]，找到： 那么以 a[i] 作为最大值的区间数量： (i−L)×(R−i)(i-L)\times(R-i)(i−L)×(R−i) 贡献就是： 最小值同理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十、相等元素的注意事项 如果数组中可能有相等元素： 左右两边都使用严格比较，可能导致同一个区间被重复统计。 做贡献题时通常需要： 例如最大值： 最小值： 这样可以保证每个区间只归属于一个位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十一、单调栈核心口诀 再记一句： > 栈里留下的是还没有找到答案的人。 这就是单调栈最核心的思想。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十二、常见错误 1. 栈里建议存下标 推荐： 存位置，比较时： 这样既能得到值，也能得到下标。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 注意严格和非严格 在有重复元素时区别很大。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 不存在时答案通常为 000 全局数组默认： 所以没有找到答案的元素可以不用额外处理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. WHILE 不是 IF 必须： 因为一个当前元素可能同时解决很多前面的元素。 例如： 当前 6 可以一次弹： 所以一定是 while。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 单调栈主要解决： > 某个元素左边或右边，第一个比它大 / 小的位置。 最重要的理解： 当前元素出现后： 每个元素最多入栈、出栈一次，因此时间复杂度为 O(n)O(n)O(n)。 平衡数组 单调栈 发射站

离散化 哈希随机函数 归并排序 拓扑排序 树状数组 ST表

随机at @八级大狂风 @AC君 @得去搞点吃的 @.҈̊̔柠.҈̊̔̇̊͐七 表面积和体积 时间限制：1000ms 内存限制：128MB 输入三个整数a、b、c表示长方体的长宽高，输出长方体的表面积和体积,结果之间用空格隔开。 长方体的表面积 =（长×宽+长×高+宽×高）× 2； 长方体的体积 = 长×宽×高 输入格式 三个整数，a、b、c（0≤a,b,c≤10310^3103) 输出格式 两个数字，第一个表示长方体的表面积，第二个表示长方体的体积 样例组 输入#1 3 4 5 输出#1 94 60 提示说明 答 这是送分题 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 消息数量 时间限制：1000ms 内存限制：128MB 某聊天软件的消息数量显示遵循以下规则： 当消息数量 ≤ 99 时，显示实际数字（如 "42"） 当消息数量 > 99 时，统一显示为 "99+" 现给定一个正整数 n 表示消息数量，请编写程序输出该聊天软件应显示的内容。 数据范围 1≤n≤10000 输入格式 输入一个整数 n 占一行。 输出格式 输出一个数字或者 "99+"占一行，表示答案。 样例组 输入#1 42 输出#1 42 输入#2 10000 输出#2 99+ 提示说明 样例一解释： 因为 42 没有超过 99，所以直接显示具体数量，所以答案是 99。 样例二解释： 因为 10000 超过 99，所以直接显示"99+"，所以答案是 99+。 答 不不不不不不不不不不，这是显而易见的 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 石板问题（中等版） 时间限制：1000ms 内存限制：128MB ccj 正在回家的路上，需要跨过一段由 n 个石板组成的小道。 你每一步可以选择跨越 1 块石板,或者 2 块石板,或者 3 块石板。 ccj 回家闲着没事准备计算一下：从起点第 1 块石板出发，有多少种不同的方式可以恰好走到第 n 块石板上？ 输入格式 输入一行一个整数 n，表示小道的石板数量。 输出格式 输出一个整数，表示恰好走到第 n 块石板的方案数。 样例组 输入#1 1 输出#1 1 输入#2 2 输出#2 1 输入#3 5 输出#3 7 输入#4 6 输出#4 13 提示说明 【样例 1 解释】 你原先就在石板 1 ,总共 1 种方法到达, 就是原地不动。 【样例 2 解释】 可以从石板 1 跨越 1 块石板走到石板 2 ,总共 1 种方法到达。 数据范围 测试点 n 特殊性质 1−10 1≤n≤25 无 答 前缀和 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ [CSP-J 2025] 拼数 / number 时间限制：1000ms 内存限制：512MB 小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 s，其中 s 仅包含小写英文字母及数字，且包含至少一个 1∼9 中的数字。小 X 希望小 R 使用 s 中的任意多个数字，按任意顺序拼成一个正整数。注意：小 R 可以选择 s 中相同的数字，但每个数字只能使用一次。例如，若 s 为 1a01b，则小 R 可以同时选择第 1,3,4 个字符，分别为 1,0,1，拼成正整数 101 或 110；但小 R 不能拼成正整数 111，因为 s 仅包含两个数字 1。小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。 输入格式 输入的第一行包含一个字符串 s，表示小 X 给小 R 的字符串。 输出格式 输出一行一个正整数，表示小 R 能拼成的正整数的最大值。 样例组 输入#1 复制 5 输出#1 复制 5 输入#2 复制 290es1q0 输出#2 复制 92100 提示说明 大数据下载链接 number.zip 【样例 2 解释】 s 包含数字 2,9,0,1,0。可以证明，小 R 拼成的正整数的最大值为 92100。 【样例 3】 见选手目录下的 number/number3.in 与 number/number3.ans。该样例满足测试点 9∼11 的约束条件。 【样例 4】 见选手目录下的 number/number4.in 与 number/number4.ans。该样例满足测试点 20 的约束条件。 【数据范围】 设 ∣s∣ 为字符串 s 的长度。对于所有测试数据，保证： 1≤∣s∣≤10610^6106 s 仅包含小写英文字母及数字，且包含至少一个 1∼9 中的数字。 特殊性质 A: s 仅包含数字。 特殊性质 B: s 仅包含不超过 1000个数字。 答 暴力枚举 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 魔法石补给（考试版） 时间限制：1000ms 内存限制：128MB 小码君正在准备一场魔法试炼。他有一个容量为 M 的魔法背包，商店里有 n 种魔法石。 第 i 种魔法石每块占用容量 wiw_iwi , ，每块可以提供能量值 viv_ivi ,，并且可以购买任意多块。 请问在背包容量不超过 M 的情况下，最多可以获得多少能量值。 输入格式 第一行两个整数 n,M。 接下来 n 行，每行两个整数 wiw_iwi , viv_ivi ,。 输出格式 输出一行一个整数，表示最大能量值。 样例组 输入#1 复制 3 10 2 6 3 10 5 15 输出#1 复制 32 提示说明 样例解释 选择 2 块容量为 2 的魔法石，获得 12 点能量；选择 2 块容量为 3 的魔法石，获得 20 点能量。 总容量为 2×2+3×2=10，总能量为 32。 数据范围 答 原题 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 沙漠商队补给（easy） 时间限制：1000ms 内存限制：128MB 一支商队准备穿越沙漠。 商队的车队最多可以承载重量不超过 M 的补给。 现在仓库里有 n 种补给品，第 i 种补给品： 每件重量为 wiw_iwi ； 每件价值为 viv_ivi ； 最多有cic_ici 件。 商队可以选择若干件补给品装车，但每种补给品不能超过对应数量上限，且总重量不能超过 M。 请你求出商队最多能够带走的补给总价值。 输入格式 第一行两个整数 n,M，分别表示补给品种类数和车队最大承重。 接下来 n 行，每行三个整数 wiw_iwi ,viv_ivi ,cic_ici ，表示第 i 种补给品的重量、价值和数量上限。 输出格式 输出一行一个整数，表示能够获得的最大总价值。 样例组 输入#1 复制 4 10 2 6 4 3 10 2 4 13 2 5 16 1 输出#1 复制 33 提示说明 样例解释 一种最优方案为： 选择第 2 种补给品 2 件，总重量为 3×2=6，总价值为 10×2=20； 选择第 3 种补给品 1 件，总重量为 4×1=4，总价值为 13×1=13。 总重量为 6+4=10，总价值为 20+13=33。 所以答案为 33。 数据范围与子任务表 对于所有数据，保证： 1≤n≤300 1≤M≤5000 1≤wiw_iwi ≤M 1≤viv_ivi ≤10610^6106 1≤cic_ici ≤10910^9109 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小码君买饮料 II 时间限制：1000ms 内存限制：128MB 小码君来到一家商店购买饮料。 商店里一共有 n 种饮料。 第 i 种饮料： 每瓶价格为 cic_ici 元； 每瓶容量为lil_ili 毫升； 可以购买任意多瓶。 小码君今天很渴，希望购买的饮料总容量不少于 L 毫升。 请你帮小码君计算，在满足总容量不少于 L 的前提下，最少需要花多少钱。 输入格式 第一行两个整数 n,L，表示饮料种类数和需要达到的最低总容量。 接下来 n 行，每行两个整数 cic_ici ,lil_ili ，表示第 i 种饮料的价格和容量。 输出格式 输出一行一个整数，表示最少花费。 样例组 输入#1 3 100 6 50 10 80 15 120 输出#1 12 提示说明 样例解释 可以买 2 瓶第 1 种饮料。 总容量为： 50+50=100 总花费为： 6+6=12 虽然也可以买 1 瓶第 3 种饮料，容量为 120，但花费为 15，不是最优。 所以答案为 12。 数据范围与子任务表 对于所有数据，保证： 1≤n≤200 1≤L≤20000 1≤cic_ici ,lil_ili ≤10610^6106 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 遗迹补给路线 时间限制：1000ms 内存限制：128MB 探险队进入一座遗迹，遗迹可以看成一个 H×W 的地图。 地图中： @ 表示起点； 表示墙壁； . 表示空地； 大写字母 A 到 Z 表示补给箱类型。 探险队可以从 @ 出发，每次向上、下、左、右四个方向移动一格。 探险队不能走出地图，也不能穿过墙壁。 只有从起点可以到达的补给箱才能被带走。 现在有 T 种补给箱，第 i 种补给箱对应字母为第 i 个大写字母。 也就是说： 第 1 种补给箱对应 A； 第 2 种补给箱对应 B； 第 3 种补给箱对应 C； 依此类推。 每个第 i 种补给箱重量为 wiw_iwi ，价值为 viv_ivi 。 探险队有一个容量为 M 的背包。 如果地图上有多个同类型补给箱，探险队最多可以带走这些可达补给箱中的若干个。 每个补给箱最多只能被带走一次。 请问探险队在背包容量不超过 M 的情况下，最多可以获得多少价值。 注意： @ 只表示起点，不作为补给箱统计。 输入格式 第一行四个整数 H,W,T,M。 接下来 H 行，每行一个长度为 W 的字符串，表示地图。 接下来 T 行，每行两个整数 wiw_iwi ，viv_ivi 表示第 i 种补给箱的重量和价值。 第 1 种补给箱对应 A，第 2 种补给箱对应 B，以此类推。 输出格式 输出一行一个整数，表示最大价值。 样例组 输入#1 复制 4 5 3 10 @.A.. ##.#. ..B#. .C... 3 8 4 10 2 5 输出#1 复制 23 提示说明 样例解释 从起点能够到达地图中的 A、B、C。 三种补给箱各有一个可达。 背包容量为 10。 选择 A、B、C，总重量为： 3+4+2=9 总价值为： 8+10+5=23 所以答案为 23。 数据范围与子任务表 对于所有数据，保证： 1≤H,W≤500 1≤T≤26 1≤M≤20000 1≤wiw_iwi ,cic_ici ≤10510^5105 地图中恰好有一个 @。 地图中出现的补给箱字符只会是 A 到第 T 个大写字母。

给团队的人看。 注意到可以dp，但是无论从哪里开始都无法使起点受到更新。 那我做两次不就行了？ 因为第二次时的距离更长，肯定不会覆盖此前的结果，所以无妨。

建议几月份考GESP

print(int(input())//int(input()))

U138701.零昼回声：双相树谱 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

只要你是的TLE第一帝国（原TLE兵团）的成员，都可以在这里进行文明讨论

描述 “风雨浸衣骨更硬，野菜充饥志越坚。” 红军长征过草地时，补给极其困难。每位战士身上的干粮（N）是走出草地的关键。 假设行军非常艰苦，消耗量随着体力的下降每天都在增加： 第 1 天行军消耗 1 份干粮； 第 2 天行军消耗 2 份干粮； 第 3 天行军消耗 3 份干粮； 以此类推，第 i 天需要消耗 i 份干粮。 每天清晨，战士会检查袋子里的剩余干粮。如果剩余量足够支付当天的消耗（即 N≥i），则继续坚持行军；如果不够，则意味着弹尽粮绝，必须等待救援。 输入一个整数 N，请计算战士靠这些干粮最多能完整行军多少天。 输入描述 一个整数 N（初始干粮总数）。 输出描述 一个整数（完整行军的天数）。 天数 当日需求 剩余物资判断 操作结果 剩余物资 ‌第 1 天‌ 1 份 7≥1，足够 消耗 1 份 6 份 ‌第 2 天‌ 2 份 6≥2，足够 消耗 2 份 4 份 ‌第 3 天‌ 3 份 4≥3，足够 消耗 3 份 1 份 ‌第 4 天‌ 4 份 1<4，不足 ‌无法坚持‌ - ‌结论‌：只能坚持 ‌3‌ 天。 数据范围 1≤N≤10 答案(不唯一):

“我这是……在哪？”我不会C++睁开眼睛。 虽然还是在阳陂湖，但是周围没有教室，没有电脑。 天空中只有无数个：0、1、0、1、1、0…… 突然，一个机械声音响起： 【欢迎进入——程序大陆。】 【想要离开这里，请集齐10枚C++核心碎片。】 学生们看向张老师： “老师，你这么帅，你会C++，你快想办法啊！” 我不会C++沉默了三秒： “有没有一种可能……” “我的名字就叫——我不会C++。” “别急，我先看一眼课件” 【……😓😓😓】 【系统检测到全员菜鸟，自动开启新手任务。】 第一枚碎片被锁在一道机关后： (101101)₂ = (?)₁₀ 紧接着，第二道机关亮起： &　|　^　<<　>> 神秘声音再次出现： “计算机的世界里，没有魔法。” “只有——0和1。” 【待技能解锁：进制转换】 【待技能解锁：位运算】 【为了逃出这里，请开始---第一枚C核心碎片争夺战！】 获得第一枚C核心碎片后， “我不会C++”带着冒险小队继续前进，他们预备去投奔“我超爱写C++”。 突然—— 整个程序大陆变成了一张巨大的方格地图！ 天空中，一个黑影缓缓出现。【警告！检测到未知BOSS！】 ？？？：“居然有人拿到了第一枚碎片……” “记住我的名字。” “我是大魔王——Y。” 话音刚落，无数怪物出现在方格之中。 我不会C++：“完了！这么多格子，怎么一个个处理？” 系统突然亮起：【技能解锁：二维数组】 用行和列，记录整个地图！ 但想检查地图中的每一个位置，还需要——【技能解锁：循环嵌套】 外层走每一行，内层走每一列！ 大魔王Y冷笑： “桀桀桀，那就让我看看，你们有多厉害。” “写不出来就是承认，我不会C++全世界倒数第一帅！” 【第二枚C++核心碎片争夺战——开始！】 XM02班级冒险小队继续前进，一面巨大的魔镜挡住了道路。 我不会C++走到镜子前，整理了一下头发： “魔镜魔镜，我美不美，谁是世界上最美的人？” 魔镜沉默三秒：“最美的是宇宙无敌美少女，然后是我超爱写C++，然后是呼呼老师，然后是$$##¥¥” 我不会C++：“？？？你是不是答非所问？” 此时梓宁和王荀异口同声：“张老师，魔镜🪞甚至没把你排进去。” 【我不会C++受到暴击：9999】 突然，大魔王Y的声音从空中传来： “想要第三枚碎片？先把我的排行榜恢复！” 魔镜瞬间出现了一堆混乱的数据： 8　3　7　1　6　2…… 我不会C++：“一个一个试，总能找到正确答案吧？” 【技能解锁：枚举】 不知道答案在哪里？那就把可能的情况一个个尝试！ 可排行榜还是乱的。 “既然有排名……” “那就把它们按照规则重新排列！” 【技能解锁：基础排序】 比较、交换，让混乱的数据重新变得有序！ 随着最后一个数字回到正确位置——【第三枚C++核心碎片获得！】 魔镜忽然再次亮起： “友情提示……” “刚才那个问题，我没有答错。” 我不会C++：“？” 远处，大魔王Y默默关掉了魔镜。 “……差点暴露了。” 【大魔王Y身份线索 +1】 离开魔镜后，冒险小队来到了一座高塔。 塔门上写着： 【请将100000份数据排序后，方可进入。】 我不会C++：“简单！我们昨天刚学会基础排序，一个一个比较！” 系统冷冷地弹出提示：【预计完成时间：等到大魔王Y退休。】 我不会C++：“……有没有快一点的？” 突然，一本新的技能书从天而降：【高级技能解锁：sort排序】 不再需要自己反复比较、交换， 只需要告诉它：排谁？从哪里排到哪里？ 剩下的，交给 sort！ 数据飞速恢复顺序，高塔大门轰然打开。 【第四枚C++核心碎片获得！】 然而碎片背后，刻着一个熟悉的字母：Y 大魔王Y的声音再次响起：“排序越来越快了……” “可如果下一次要排序的，不只是一个数字呢？” 【大魔王Y的考验即将升级……】 ACGO_无能狂怒ACGO_无能狂怒ACGO_无能狂怒 进入高塔后，众人发现了一座巨大的档案库。 每份档案里都有： 姓名、年龄、战斗力、积分…… 我不会C++：“这么多数据，我要开四个数组分别存？” 系统：【可以。】 【但是看起来很笨。】 我不会C++：“你礼貌吗？” 这时，第五枚碎片亮起。 【新技能解锁：结构体 struct】 一个冒险者的信息， 不必拆得到处都是。 可以把属于同一个人的数据，打包在一起！ 可大魔王Y又留下了一项任务： “按照积分从高到低，重新排列所有冒险者。” 我不会C++：“等等，昨天的 sort 不是只能排数字吗？” 系统：【技能升级：结构体排序】 结构体 + 自定义比较规则 + sort！ 想按成绩排，就按成绩。 成绩相同想按编号排，就再增加规则。 很快，冒险者排行榜重新生成。 【第五枚C++核心碎片获得！】 但排行榜第一名的位置…… 没有姓名。 只有一个代号： Y　　积分：99999999 我不会C++：“不是，他哪来这么多分？？？” 远处传来大魔王Y的笑声： “想超过我？” “那就继续学下去吧。”

#include <bits/stdc++.h> using namespace std; int n; int a[10]; //记录每次抽的编号 bool vis[10]; //记录每个小球有没有被抽过 //如vis[3]如果是true 就表示3被抽过了 //dfs(k)表示在抽第k个小球 void dfs(int k) { //正在抽第n+1个小球，前n个小球已经抽完 if (k == n + 1) { //输出前n个小球抽的情况 for (int i = 1; i <= n; i ++ ) { cout << a[i] << " "; } cout << endl; return ; } } int main() { cin >> n; dfs(1); //从第一个小球开始抽 return 0; }

本篇关于单调队列&单调栈 单调栈 单调队列

本文不包含所有类型DP,仅包含我所学 若二维DP超空间,将第一维改成2,每个包含I的地方整体(打括号)&1计算 01背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 01背包求方案数 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 完全背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 多重背包 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 跳跃DP(LIS) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 区间DP 二进制枚举 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 状态压缩DP 这个比较难,我简单喵两句 状态压缩dp,基于二进制枚举实现,它本质其实是模拟简化了全排列DFS枚举,解决非连续的问题, 比如最小异或值问题: 解法:记已排列CNT个数,通过全排列数组B,用全排列的最后一个结果与数组A的第CNT位进行异或 比如吃奶酪问题: 解法:记吃了第I个奶酪时二进制状态第I位为1,枚举为0的地方,同时开二维记录上一个奶酪位置 它们的共同点是通过枚举二进制状态的每一位,第i位为1表示第i个数被选过

@AC君 这个题目的测试数据输出什么都没有，严重怀疑有人擅自修改测试数据。