水原_

题解

ACM(13)

/ 注册

全部文章 / 题解（共28篇）

P2123 皇后游戏

写一下这题的反省。首先选相邻的两个比较是不用说的。我自己的想法居然是分类讨论。果然是被数学思想毒害了。要注意的有两点: 等价于（至少本题如此）都是基本操作的说，但就是没想到。。最后要注意的就是要把放到中以配平成使其消掉。（本来就不是给别人看的所以自己懂就好） #include<...

2020-01-02

0 665

P2054 [AHOI2005]洗牌

开始只想到暴力。。反推公式就好了。。后来再仔细看看这个公式，若从推到，发现那么设答案为,则那么逆元求就好了。

2020-01-02

0 428

P2561 [AHOI2002]黑白瓷砖

大致思路就是将图案分为一个个环套在一起，然后用图来观察关系，再用容斥原理dp即可。 #include<iostream> #include<memory.h> #include<algorithm> #define maxlon 100 using namesp...

2020-01-02

0 500

P2536 [AHOI2005]病毒检测

记模板串为s2,待测串为s1。对于s2首尾，若没有，直接一位位匹配直到有即可。再考虑s2串为的情况。其中是的某个片度。我们将依次从s1的合法位置开始向后匹配。（合法位置初始为0）用匹配到的第一个位置来更新合法位置。至于为什么不用s1后面的位置，这是因为用后面的一定不会比用前面的更...

2020-01-02

0 738

P2258 子矩阵

本题如果想纯的话。。简直难以名状。解决方法就是不要只想着，放宽一点复杂度，想想能不能通过少量的枚举来使更加好写。这一题，就是枚举行或者列，复杂度,可以接受。那么行确定了，列的就十分好想了。 #include<iostream> #include<memory.h> ...

2020-01-02

0 595

P1311 选择客栈

开始想用分治，找到中间的一个小于的客栈，然后用到它的两边的客栈的贡献就可以用前缀和轻易算出。然后递归处理左右。后来发现没有这个必要，从左向右扫一遍就好了。每次找到当前第一个小于的客栈，这样它前面的客栈与他自己的贡献便可以处理。预处理,主过程. #include<iostream> ...

2020-01-02

0 452

P1240 诸侯安置

首先是一步本鶸想了很久也没有想到的操作。。。因为将整行/列平移并不影响诸侯间的限制关系，且题目又说了镜面和旋转的情况属于不同的方案，那我们就可以把图案平移成我们想要的样子了。那我们希望图案是什么样子？既然是dp, 我们当然希望能够得到没有后效性的图案。也就是楼下dalao的图案。因为每一...

2020-01-02

0 560

P1966 火柴排队

本题即求即由排序不等式知正序和最大，故只需求将a,b序列变成正序的最小步数。首先对a操作或对b操作是没有区别的，因为我们只关系a,b中元素的对应关系。所以我们不妨只对b操作。因只关心大小，不妨将a,b分别离散化。然后将a一一映射成1-n，只需求将b序列变成1,2,3...n的最小步数。...

2020-01-02

0 672