Rewinner

分类

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章（共136篇）

扩展kmp(转载)

原文：https://blog.csdn.net/dyx404514/article/details/41831947 拓展kmp是对KMP算法的扩展，它解决如下问题：定义母串S，和字串T，设S的长度为n，T的长度为m，求T与S的每一个后缀的最长公共前缀，也就是说，设extend数组,exte...

2019-01-19

0 415

数位DP 求满足条件的和

这是一个板子：求数位DP中满足一些条件的数的和方法：如果我们求满足条件的数的个数只需要开一个数组就行。如果我们求满足条件的数的和，则需要开一个数组结构体 node 里面有两个元素，一个是cnt，一个是sum。 cnt就是记录满足条件的数量，sum就是记录满足条件的数字和。...

2019-01-11

0 582

HDU1074：Doing Homework(状缩DP)

题意：有n门课，每门课有截止时间和完成所需的时间，如果超过规定时间完成，每超过一天就会扣1分，问怎样安排做作业的顺序才能使得所扣的分最小（相同答案输出字典序较小小的答案）思路：用二进制压缩状态，比如110，表示第二门和第三门课程完成，第一门课程没有完成。我们的dp[i]意思是在i这个状态下能够扣...

2019-01-09

0 610

POJ 1185 炮兵阵地状压DP

解题方法：第一个巧妙之处：第一步先预处理炮车能够放置的位置（其实只有几十种），如果暴力枚举的话，时间空间都不够的。第二个巧妙之处：将地图的每一行状压成一个数，山地位置为1，平原为0。为什么这么状压？我们预处理的炮车放置情况，能放炮车的地方为1，不能放置炮车的地方为0，假如炮车放置情况...

2019-01-09

0 524

Mondriaan's Dream POJ - 2411 状压（有注释）

状压的方法参考博客：https://blog.csdn.net/hopeztm/article/details/7841917?utm_source=tuicool&utm_medium=referral 大佬的博客思想很好但是时间复杂度很高。我利用大佬状压的思想写的DFS记忆化，跑了...

2019-01-07

0 476

B number 数位DP

题意很简单就是要你寻找数字含有13字串并且能够被13整除的数。我自己的写法和大佬的做法都不一样，时间也比他们的慢很多，跑了（200+ms）。大佬的博客：https://blog.csdn.net/libin56842/article/details/10026063 大佬的DP是三维，而...

2019-01-07

0 474

西北大学第四届程序设计竞赛新生赛 J 八意永琳的药房

这道题看了大佬的代码，发现思路居然这么奇妙。合并两个数组。我的想法：暴力时间复杂发O（n^2），绝对T。大佬的想法：bitset 时间复杂度 O（n）。 Orz Orz Orz 。 bitset可以很好的记录状态， ///#include<bits/stdc++.h...

2019-01-04

0 530

HDU 2157 矩阵快速幂

在打牛客的时候碰到一道类似的题，我以为是图论题，结果看了题解，居然是一道矩阵快速幂的经典题。哪个地方会直接用到矩阵快速幂，对，就是图论中求对应两个点长度为n的路径数，这是矩阵乘法在图论中的经典应用，其实就是用到了矩阵乘法的特殊性，因为矩阵乘法有三重循环，最里面的一层循环就是在枚举一个点k，i -...

2019-01-04

0 522

长沙理工大学2018年新生赛 I 一个字符串游戏

题意解析：题中所说的不同字符数指的是：对于相同下标index，如果字符相同则数量+1，否则+0。官方题解：代码： ///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unor...

2019-01-03

0 490

Gym 101889F — Fundraising 树状数组+离散化+带权上升子序列

题意:给你一些人，每个人有两个特性和一个价值，如果两个人的特性完全相等则可以合并，否则必须一个人的两个特性必须严格大于另一个人才能合并，问：最终可以的到的最大价值。解题思路：看到别人的博客里面有带权上升子序列，让我想起了最长上升子序列 nlogn 的解法：在数组下标 1—i中最长上升子序...

2019-01-02

0 477