hackerchef - 博客园

2025年9月

洛谷题单指南-状态压缩动态规划-P2473 [SCOI2008] 奖励关

摘要：原题链接：https://www.luogu.com.cn/problem/P2473 题意解读：有n中宝物，每个宝物有得分，有能不能吃的条件（之前吃过哪几种宝物才能吃当前宝物），抛k次，求最高得分的期望。解题思路：如果做过https://chuna2.787528.xyz/hackerchef/p 阅读全文

posted @ 2025-09-01 16:02 hackerchef 阅读(23) 评论(0) 推荐(0)

2025年8月

洛谷题单指南-状态压缩动态规划-P2761 软件补丁问题

摘要：原题链接：https://www.luogu.com.cn/problem/P2761 题意解读：有n个bug，m个补丁，每个补丁运行有时间代价，每个补丁运行有特定的条件，可以修复bug引入bug，求修复所有bug所用的最小代价。解题思路：设所有bug的状态为(1 << n) - 1，最终要达成阅读全文

posted @ 2025-08-29 15:43 hackerchef 阅读(43) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P5369 [PKUSC2018] 最大前缀和

摘要：原题链接：https://www.luogu.com.cn/problem/P5369 题意解读：求n个数所有排列的最大前缀和之和，求期望要除以n！，此题简化后不需要除以n！。解题思路： 1、暴力思路枚举n个数的全排列，针对每个排列求一遍前缀和，取最大值，加总，复杂度n*n!，n最大20，爆了。阅读全文

posted @ 2025-08-28 11:11 hackerchef 阅读(24) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-CF1209E2 Rotate Columns (hard version)

摘要：原题链接：https://www.luogu.com.cn/problem/CF1209E2 题意解读：n*m的数字矩阵，每列可以任意滚动，求每行最大数之和的最大值。解题思路： 1、初步分析由于一共只取n个数，显然这n个数尽可能大，虽然列数m比较大，但是实际用到的，必然是列最大值排名靠前的哪些列阅读全文

posted @ 2025-08-27 11:43 hackerchef 阅读(18) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-AT_agc012_e [AGC012E] Camel and Oases

摘要：原题链接：https://www.luogu.com.cn/problem/AT_agc012_e 题意解读：坐标轴上有n个点，有一个初始跳跃值V，支持两种操作：1、V不为0时，从一点跳跃到任意一点，V=V/2； 2、从一个点可以走到相邻点，前提是两点间距离<=V，求从每个点出发是否可以遍历其他所有阅读全文

posted @ 2025-08-25 14:18 hackerchef 阅读(22) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P4045 [JSOI2009] 密码

摘要：原题链接：https://www.luogu.com.cn/problem/P4045 题意解读：n个单词拼接成长度为l的字符串，相接处相同的前后缀可以叠在一起，问一共能拼出的字符串数量。解题思路：要解决这道题，首先要了解AC自动机，先来解决这道题：https://www.luogu.com.c 阅读全文

posted @ 2025-08-20 11:18 hackerchef 阅读(28) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P2831 [NOIP 2016 提高组] 愤怒的小鸟

摘要：原题链接：https://www.luogu.com.cn/problem/P2831 题意解读：求覆盖平面上所有点的最少的曲线数，曲线形如y=ax2+bx 解题思路： 1、两点确定一条曲线由于曲线方程为：y=ax2+bx，可以判断两点确定一条曲线设两点为(x1,y1)，(x2,y2)，则有 y 阅读全文

posted @ 2025-08-06 17:37 hackerchef 阅读(41) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P2704 [NOI2001] 炮兵阵地

摘要：原题链接：https://www.luogu.com.cn/problem/P2704 题意解读：一个炮兵部队可以覆盖横向纵向两行的位置，给定n*m区域，可以部署炮兵为P，不能部署炮兵为H，求不互相攻击的情况下最多可以部署多少炮兵部队。解题思路：通过对一行是否部署炮兵部署，可以使用二进制整数来压阅读全文

posted @ 2025-08-05 11:25 hackerchef 阅读(45) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P1879 [USACO06NOV] Corn Fields G

摘要：原题链接：https://www.luogu.com.cn/problem/P1879 题意解读：在m*n的区域种玉米，能种的是1不能种的是0，要求玉米不能种在相邻格子，求一共有多少种法，模100000000。解题思路：用状态压缩来表示一行玉米的种植情况，二进制中1表示种了，0表示没种。对于一阅读全文

posted @ 2025-08-04 15:36 hackerchef 阅读(18) 评论(0) 推荐(0)

洛谷题单指南-状态压缩动态规划-P1441 砝码称重

摘要：原题链接：https://www.luogu.com.cn/problem/P1441 题意解读：n个砝码去掉m个能称出的重量数。解题思路： 1、暴力法用二进制整数1~2^n - 1表示选取砝码的状态，取0的个数是m的状态表示去掉m个，然后针对剩下的砝码通过dfs枚举出所有可能的重量，每种状态求阅读全文

posted @ 2025-08-04 12:06 hackerchef 阅读(44) 评论(0) 推荐(0)

公告