水原_
水原_
全部文章
分类
ACM(13)
题解(28)
归档
标签
去牛客网
登录
/
注册
Mizuhara
Eternal Dream
全部文章
(共41篇)
P2629 好消息,坏消息
主思想就是对每个,判断是否可行。 (1): 对于每个,首先判断是否满足。 考虑到可以递推,将从到循环, 用表示的最小值 () 则易得 那么得到了,只需判断是否不小于即可。 (2): 后半部分对于的判断则更加简单。 预处理, 其中 那么只要判断是否不小于即 可。 总复杂度 #include<i...
2020-01-02
0
443
P3916 图的遍历
基本的想法就是对于每个点来一次bfs,求出它所能到达的点中最大的。这样是。 对于某个点,如果点能到达它,那么比小的点都不必再搜。 于是可以想到一个优化:反向建边,点能到达点即代表点能到达点。 基于上面的想法,只要从大往小搜,已经访问过的点不搜,即可保证答案的合法性。 (这是因为若之前访问过了,那么以...
2020-01-02
0
447
P2123 皇后游戏
写一下这题的反省。 首先选相邻的两个比较是不用说的。 我自己的想法居然是分类讨论。 果然是被数学思想毒害了。 要注意的有两点: 等价于(至少本题如此) 都是基本操作的说,但就是没想到。。 最后要注意的就是要把放到中以配平成使其消掉。 (本来就不是给别人看的所以自己懂就好) #include<...
2020-01-02
0
567
堆的基本操作
求第k大的数: 建一个大根堆,一个小根堆,并保证小根堆的最小值不小于大根堆的最大值。 然后维护两个堆,使大根堆的元素个数保持个就好了。 另外,可以以的复杂度移动。 求一堆数中最小的k个: 将这堆数划分成几条链, 每条链都是一个单独的小根堆。 然后建另外一个小根堆,里面存所有小根堆的当前堆顶即可。
2020-01-02
0
320
P2054 [AHOI2005]洗牌
开始只想到暴力。。 反推公式就好了。。 后来再仔细看看这个公式,若从推到, 发现 那么设答案为,则 那么逆元求就好了。
2020-01-02
0
343
P2561 [AHOI2002]黑白瓷砖
大致思路就是将图案分为一个个环套在一起, 然后用图来观察关系,再用容斥原理dp即可。 #include<iostream> #include<memory.h> #include<algorithm> #define maxlon 100 using namesp...
2020-01-02
0
415
P2536 [AHOI2005]病毒检测
记模板串为s2,待测串为s1。 对于s2首尾,若没有,直接一位位匹配直到有即可。 再考虑s2串为的情况。其中是的某个片度。 我们将依次从s1的合法位置开始向后匹配。(合法位置初始为0) 用匹配到的第一个位置来更新合法位置。 至于为什么不用s1后面的位置,这是因为用后面的一定不会比用前面的更...
2020-01-02
0
556
P2258 子矩阵
本题如果想纯的话。。简直难以名状。 解决方法就是不要只想着,放宽一点复杂度, 想想能不能通过少量的枚举来使更加好写。 这一题,就是枚举行或者列,复杂度,可以接受。 那么行确定了,列的就十分好想了。 #include<iostream> #include<memory.h> ...
2020-01-02
0
515
P1311 选择客栈
开始想用分治,找到中间的一个小于的客栈,然后用到它的两边的客栈的贡献就可以用前缀和轻易算出。然后递归处理左右。 后来发现没有这个必要,从左向右扫一遍就好了。 每次找到当前第一个小于的客栈,这样它前面的客栈与他自己的贡献便可以处理。 预处理,主过程. #include<iostream> ...
2020-01-02
0
356
P1240 诸侯安置
首先是一步本鶸想了很久也没有想到的操作。。。 因为将整行/列平移并不影响诸侯间的限制关系, 且题目又说了镜面和旋转的情况属于不同的方案, 那我们就可以把图案平移成我们想要的样子了。 那我们希望图案是什么样子?既然是dp, 我们当然希望能够得到没有后效性的图案。 也就是楼下dalao的图案。 因为每一...
2020-01-02
0
476
首页
上一页
1
2
3
4
5
下一页
末页