Panda2134's Blog

Not only coding

[NOIP2011]观光公交

链接：Luogu-P1315 这个题目是在某模拟赛中看到的……并没有做过，当时认为是DP，没有注意到加速器会影响等车的时间，认为只影响坐车的时间。想到了差分。考试结束之前20分钟才发现不满足无后效性，于是完挂爆0。分析 Why Greedy? DP的状态难以设计，而且无法转移是序列问题，也没有明显的元素间关系最小化旅行的时间，是最优化问题最优化 $ \Righta...

Posted by panda_2134 on October 19, 2017

烹调方案

链接：Luogu-P1417 思路看上去是一个01背包，不过价值随着时间的推移而改变，怎么办？先考虑2个物品的情况，即进行基于交换的贪心。时间足够的时候，到底是先取物品1再取物品2，还是先取物品2再取物品1。如果考虑清楚了2个物品的情况，就可以进行排序，再利用动态规划得解。实际上，如果设当前处在时刻$t_0$，两个物品的各个参数（见题）分别为$a_1,b_1,c_1$...

Posted by panda_2134 on August 20, 2017

[ZJOI2007]棋盘制作

链接：Luogu-P1169 题意在一个$N \times M$的矩阵内，找出最大的、像国际象棋棋盘一样黑白交错的正方形和矩形。思路看到第一问，显然可以用二维平面DP完成：考虑设计状态$f(i,j,k)$：以$(i,j)$为右下角的最大正方形。k=1表示在这个正方形中$(i,j)$为黑，反之$(i,j)$为白。因为要求黑白交错，所以把黑白也加入状态。于是可以转移：...

Posted by panda_2134 on August 20, 2017

悬线法学习笔记

定义概念有效子矩形：内部不含有任何障碍点的矩形。极大有效子矩形：一个有效子矩形，如果不存在一个比它更大而且包含它的有效子矩形，就称它为极大有效子矩形。最大有效子矩形：整个矩形中面积最大的有效子矩形。约定使用$S$表示障碍点的数量，整个矩形的大小为$N \times M$。定理1：极大化思想所有的极大有效子矩形中，一定包含着最大有效子矩形。证明：如果一...

Posted by panda_2134 on August 19, 2017

创意吃鱼法

链接：Luogu-P1736 题目大意有一个$n \times m$的矩阵，要在里面寻找一个尽可能大的正方形，使得这个正方形某条对角线上都是1，其他地方都是0。求这个正方形对角线长。思路注意到求的是正方形，所以是裸的二维平面DP。对此类问题，画出图像，定义状态为以某个位置为右下角的最大合法正方形；再把“障碍方格”绕着可能影响转移的位置移动即可找出转移。如本题，先考虑主对角线的情况...

Posted by panda_2134 on August 19, 2017

多米诺骨牌

链接：Luogu-P1282 审题一个骨牌转与不转，改变了两行之间的差值。要求用最少的旋转次数，达到最小差值。分析可以看出这是个背包：到底是把上下差值还是旋转次数作体积呢？旋转与否建立了不同差值之间的联系，所以直接以差值为体积即可。定义$f(i)$为上面一行和减去下面一行和的值为$i$的时候还需要的最小旋转次数。则有：$f(i)=\min\{f(i+a),f(i-a)+1\}$...

Posted by panda_2134 on August 18, 2017

[NOIP2016]愤怒的小鸟

题目链接： LYOJ:愤怒的南小鸟 Luogu:愤怒的小鸟题目较长，请在OJ上查看目录目录 0.题记 1.审题 2.思路状压动规处理抛物线情况1 情况2 陷阱和处理 3.代码 0.题记还记得去年...

Posted by panda_2134 on August 17, 2017

占坑

题解占坑列表： ***棋盘制作 ***烹调方案 ***垃圾陷阱过河（不会）消防局的设立（不会）有线电视网单调队列dp And more…

Posted by panda_2134 on August 14, 2017

[USACO]低价购买

链接：Luogu-P1108 这个题刚看到的时候我是懵逼的……着实被题解惊艳到了，完全想不到还有这么优美的解法。这些解法来自各位dalao的题解，整理如下。目录目录审题解法1 修改状态进行优化考虑多解实现解法2 思路实现 ...

Posted by panda_2134 on July 31, 2017

[USACO]家的范围

链接： Luogu-P2733 题意在正方形的区域内，有一些点有标记，求出边长大于等于2的，内部没有标记的每种不同正方形个数。正方形可以重叠。分析不同正方形的个数？我们知道DP题目的常用方法是“看题说话”。我们可以根据题目信息直接定义状态吗？确定这个区域内的某一个正方形的两个量，分别是右下角（或者左上角等）的位置$(x,y)$，以及它的边长。但是，以两者中的任意一个定义...

Posted by panda_2134 on July 25, 2017