fisty-CSDN博客

原创【数位DP】专题

所谓数位DP就是基于考虑数字的每一位来转移的DP。　　　　例如求比456小的数，可以这么考虑，　　　　　　　　4 5 6　　　　　　　 4　 5 (0~6)　　　　　　　　4 (0~4) (0~9)　　　　　　　　(0~3)(0~9) (0~9)

2015-06-11 23:11:56 2344

原创 2015蓝桥杯B组：生命之树（树形DP）

在 X 森林里，上帝创建了生命之树。他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a, v1, v2, …, vk, b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。在这个前提下，上帝要使得 S 中的点所对应的整

2015-04-12 21:23:27 1642

原创 A*启发式搜索

A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分，就在于它的一个估值函数的设计上：f(n)=g(n)+h(n) 其中f(n)是每个可能试探点的估值，它有两部分组成：一部分为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的

2015-02-15 11:56:20 1661

原创树状数组与分治法求逆序数

树状数组：可以把数一个个插入到树状数组中，每插入一个数，统计比他小的数的个数，对应的逆序为 j- sum( a[j] )，其中 j 为当前已经插入的数的个数， sum( a[j] ）为比 a[j] 小的数的个数，j- sum( a[j] ) 即比 a[j] 大的个数，即逆序的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。例如比如输入一个9 1 0 5 4

2014-12-03 21:38:05 526

系统Ubuntu 18.04 LTSpython 版本 Anaconda python3.6采用conda install opencv后，调用opencv的函数时，出现错误：cv2.error: OpenCV(3.4.1) /opt/conda/conda-bld/opencv-suite_1530789967746/work/modules/highgui/src/window.cpp:...

2019-05-27 09:11:33 529

原创【leetcode206】206. Reverse Linked List 反转链表

Reverse a singly linked list.Example:Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL迭代版/** * Definition for singly-linked list. * struct ListNode { * ...

2018-08-02 17:31:45 191

原创【leetcode148 Sort List】链表归并排序,空间复杂度o(logn)

Sort a linked list in O(n log n) time Example 1:Input: 4->2->1->3 Output: 1->2->3->4Example 2:Input: -1->5->3->4->0 Output: -1->0->3->4->5 解析: 先递归

2018-07-23 17:56:40 302

原创 C++ cv::Mat转unity Texture2D

解决的c++项目里的图片需要传输到unity做显示，返回的是cv::Mat 的data和宽高，原始图像是三通道RGB图 C++:cv::Mat _currentFrame;void GetRawImageBytes(unsigned char* data, int width, int height){ //Resize Mat to match the array passe...

2018-07-16 12:27:15 1633 5

原创 c++ typename和class的区别

相信学习C++的人对class这个关键字都非常明白，class用于定义类，在模板引入c++后，最初定义模板的方法为： template……在这里class关键字表明T是一个类型，后来为了避免class在这两个地方的使用可能给人带来混淆，所以引入了typename这个关键字，它的作用同class一样表明后面的符号为一个类型，这样在定义模板的时候就可以使用下面的方式了：template……...

2018-06-29 11:49:50 234

原创【leetcode】111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.Note: A leaf is a node with no childre...

2018-05-19 17:04:23 194

原创【leetcode】 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the in...

2018-05-15 16:35:07 183

原创【leetcode】 64. Minimum Path Sum 动态规划

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at a...

2018-05-04 17:42:41 371

原创【leetcode 】 57 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).You may assume that the intervals were initially sorted according to their start times.Examp...

2018-05-02 14:43:24 172

原创【leetcode】No.56. Merge Intervals 区间合并题解

Given a collection of intervals, merge all overlapping intervals.Example 1:Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap...

2018-04-26 17:05:24 210

原创【leetcode】55. Jump Game 动态规划解法

55. Jump GameGiven an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your maximum jump length at that position.Determ...

2018-04-19 16:34:32 1088 1

原创 lightoj 1145 Dice (I) (DP)

1145 - Dice (I) PDF (English)StatisticsForumTime Limit: 2 second(s)Memory Limit: 32 MBYou have N dices; each of them has K facesnumbered from1 t

2015-10-11 23:01:09 2051 1

原创 1418 - Trees on My Island ( Peake's theorem ）

1418 - Trees on My Island PDF (English)StatisticsForumTime Limit: 5 second(s)Memory Limit: 32 MBI have bought an island where I want to plant tree

2015-10-11 22:50:35 1790

原创用后缀数组求两个字符串的最长公共子串

对于两个字符串，不好直接运用后缀数组，所以我们可以把两个子串串中间用一个在字符串中不会出现的字符连接起来，比如'$‘,计算后缀数组，检查后缀数组中所有相邻后缀。分属于两个字符串的后缀的lcp的最大值就是答案。因为字符串的任何一个子串都是这个字符串某个后缀的前缀。求A和B 的最长公共子串等价于求A得后缀和B的后缀的最长公共前缀。/******************************

2015-08-30 17:28:33 3082 1

原创 SPOJ DISUBSTR Distinct Substrings (后缀数组)

题意：给定一个字符串，求不相同的子串个数.每一个子串一定是某个后缀的前缀。对于一个字符串的后缀，一共可以产生n - sa[i] + 1个子串。但是其中有height[i]个和前面是相同的.所以对于每一个后缀S[sa[i]].贡献的子串个数是n - sa[i] + 1 - height[i];累加后便是答案./*****************************************

2015-08-30 16:39:17 1119

原创 POJ 3261 Milk Patterns （后缀数组）

题意：求可重叠k次的最长重复子串.思路：和这题类似，http://blog.csdn.net/u013008291/article/details/48105673先二分答案，判断是否有长度为s的可重叠k次的重复子串，之后将后缀分成若干组。要判断有没有一组的后缀个数大与等于k，有则抬高二分答案的上界。/******************************************

2015-08-30 16:24:42 1205

原创 POJ 1743 Musical Theme (后缀数组)

思路：先二分答案，判断是否存在两个长度为k的子串是相同的，且不重叠。之后把排好序的后缀按照后缀之间的height值都不小于k分为若干组。例如当字符串为“aabaaaab”时，k = 2，后缀分成了如下4组:可以看出，有希望成为最小公共前缀不小于k的两个后缀一定在同一组。然后对于每组后缀，只需判断每个后缀的sa值的最大值和最小值之差是否大于等于k。如果有一组满足则存在。/********

2015-08-30 16:18:16 1220

原创 poj2406 Power Strings(KMP)

定理：假设S的长度为n，则S存在循环子串，当且仅当，n可以被n - next[len]整除，最短循环子串为S[n - next[n]]例子证明：设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[n]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6= q3q4q5q6q7q8，即有q1q2＝

2015-08-29 10:09:21 1077

原创 HDU 4686(矩阵快速幂)

An Arc of Dream is a curve defined by following function:where a 0 = A0 a i = a i-1*AX+AY b 0 = B0 b i = b i-1*BX+BY What is the value of AoD(N) modulo 1,000,000,007? Input

2015-08-27 13:40:37 1170

原创 HDU4687 (一般图匹配)

A new season of Touhou M-1 Grand Prix is approaching. Girls in Gensokyo cannot wait for participating it. Before the registration, they have to decide which combination they are going to compete as. E

2015-08-27 13:34:33 1274

原创 lightoj 1068 - Investigation (数位DP)

要求[l, r] 区间内有多少数符合两个条件：1）数可以整除k2）这个数的所有位之和可以整除k思路 : 数位dp其中一个参数存所有数位相加模k的值,另一个参数存这个当前数模k的值.当k > 90时，因为所有位之和最大为90，所以不存在整除k的值,直接输出0./*********************************************** * Author: f

2015-08-27 13:04:03 1213

原创 light oj 1057 Collecting Gold(状态压缩dp)

思路：假设黄金数量一共有k个，给这些黄金编号为0 ~ k-1并且把他们的位置都存起来。起点编号为k那么定义dp[s][i] : 当前已经采集的黄金集合为s, 并且现在处于编号为k的位置对于将要采集的黄金编号 j ,有如下转移方程d[s | (1 初始点为dp[0][k] = 0;终点也为dp[0][k]，是经典的TSP问题./**********************

2015-08-25 09:34:51 1252

原创 lightoj 1050 - Marbles （概率DP）

思路：定义dp[i][j] 为袋子中有i个红球和j个红球时获胜的概率那么根据题意我只可以任意拿而对手只拿蓝球。那么dp[i][j] = （拿到红球的概率） * dp[i-1][j-1] + (拿到蓝球的概率) * dp[i][j-2];边界：当红球没有时，获胜的概率为1注意点：T比较大，需要把所有数据预处理出来直接查询，否则超时/***********************

2015-08-23 15:19:20 1223

原创 lightoj 1047 Neighbor House(Dp)

思路：定义dp[i][j] 为粉刷第i个房子用的颜色jdp[i][j] = min(dp[i-1][(j+1)%3] , dp[i-1][(j+2) % 3]);一共有三种颜色{0, 1, 2}，任取一种颜色{j}，那么和颜色j不同的颜色就为{(j + 1) % 3 , (j + 2) % 3};/********************************************

2015-08-23 14:50:23 1422

原创 lightoj 1044 Palindrome Partitioning(dp)

题意:给定字符串S，问可以划分的最小回文串数量思路：定义dp[i]为以i开头的字符串中回文串的最小划分数.dp[i] = min(dp[j] + 1 | i 边界,dp[i] = n-i+1./*********************************************** * Author: fisty * Created Time: 2015-08-22 09

2015-08-23 14:45:00 1151

原创 poj 3581 Sequence(后缀数组)

思路：对于第一段序列，因为第一个数最大所以最小的序列等于反串之后的字典序最小子串。用后缀数组可求。之后在剩下的子串中，想分割出两个子串使得反转之后字典序最小，可以这样考虑:先把剩下的字符串进行反转复制两次，样例中去掉第一段序列后剩下的子串为{2， 3， 4}，处理完为：{4， 3 ， 2， 4 ，3， 2},可以发现{2， 4， 3}这个子串符合题目要求，而且{2}和{4. 3} 正好

2015-08-22 23:28:07 1135

原创 hdu5289 Assignment --2015多校训练赛(一)

题意：给定一串数字，里面存在多少个区间[l, r] 使得里面的最大值与最小值之差小于k。思路:用RMQ预处理出所有区间的最大值与最小值之差。之后枚举左端点L, 二分处理差值小于k的最左边端点R，把所有的R-L+1加上就是答案。/*********************************************** * Author: fisty * Cr

2015-08-21 21:03:17 414

原创 lightoj 1037 - Agent 47 （状压DP）

题意：你现在需要消灭n个敌人，n个敌人的血量已知，你的普通攻击力为1，但是如果你杀死敌人i可以用它的武器去杀死其他敌人，p[i][j] 表示用敌人i的武器射杀敌人j会减p[i][j]滴血.问你最少可以攻击多少次可以将敌人杀死。思路:定义集合s为死亡敌人的集合。dp[s] 为让集合为s的人死亡最小需要的攻击次数。如果现在想要消灭敌人i 并且敌人i不属于s那么dp[s | (1

2015-08-20 15:36:21 757

原创 lightoj 1036 - A Refining Company （dp）

题意:在一个m x n的地图里有金矿和银矿，当你在某个点（x, y）时，你可以建造一个只能向西或者向北挖取矿石的履带车，金矿石只能被向北移动的履带车挖取，银矿石只能被向西移动的履带车挖取，并且履带车不能交叉。给出你每个地点的金矿和银矿的数量为你用履带车挖取的最大矿石数量是多少.（履带车会一直走到边界）思路:当你位于（x, y）时，你只有两个操作：1）建立一个向北运输的履带车，挖一路

2015-08-20 10:22:02 1024

原创 lightoj1033 - Generating Palindromes （LCS）

题意：给你一个字符串，至少需要添加多少字符可以使得它变成一个回文串.思路 :设串S的反串为S‘那么strlen(S) - LCS(S, S')就是本问题的答案.如：S（原串） A b 3 b dS1（倒序串） d b 3 b ALCS b 3 b 所以，有3个字符已经配对，不用添加

2015-08-20 10:05:54 557

原创 hiho一下第56周高斯消元

小Ho：小Hi：小Ho，你还吃呢。想好了么?小Ho：肿抢着呢(正想着呢)......我记得这个问题上课有提到过，应该是一元一次方程组吧。我们把每一件商品的价格看作是x[1]..x[n]，第i个组合中第j件商品数量记为a[i][j]，其价格记作y[i]，则可以列出方程式：a[1][1] * x[1] + a[1][2] * x[2] + ... + a[1][n] * x[n] =

2015-08-19 13:27:57 457

原创 lightoj 1032 - Fast Bit Calculations （数位DP）

记忆花搜索：dp[len][num][last] : 现在处理第len位，前面有num个11，并且最后一位为last。/*********************************************** * Author: fisty * Created Time: 2015-08-18 20:18:09 * File Name : 1032.cpp *********

2015-08-18 20:46:05 470

原创 poj 2135 Farm Tour(最小费用流)

思路：求往返不能经过同一条道路两次，参观路线最小的最小值.可以转话为边的流量为1，总流量为2的最小费用流约束:1111 /*********************************************** * Author: fisty * Created Time: 2015-08-17 16:09:15 * File Name : poj213

2015-08-18 15:30:05 358

原创 poj 3469 Dual Core CPU (最小割最大流)

思路:考虑把N个模块按照在哪个核上执行分成两个集合记核A上执行的模块集合为S，而在核B上执行的模块集合为T。考虑以模块为顶点，并且还有额外的源点s和汇点t的图。我们也记图的s-t割所对应的包含s的顶点集合为S，包含t的集合为T。此时的总花费为sigma(Ai) + sigma(Bi) + Sigma(wi).所以我们想通过合适的建边使得花费的总和等于割的容量的话，那么求最小费用只求

2015-08-18 15:24:34 385

原创 poj 3281 Dining (网络流)

思路：因为需要同时给一头牛分配所喜欢的食物和饮料，所以我们需要把食物和饮料对应的两个匹配通过下面的方法联合起来进行求解。把食物对应的牛和饮料对应的牛拆成两个顶点，之间连一条流量为1的边，就保证的一头牛不会被分配多组食物和饮料。图的顶点中除了食物和牛，牛和饮料之外还应该有一个源点s和一个汇点t在s和所有食物，t和所有饮料之间连一条边边的方向为s -> 食物 -> 牛 -> 牛 -> 饮料

2015-08-18 15:08:38 355

原创 poj 3041 Aeteroids （二分图最大匹配）

题解: 本题中的所有顶点可以分成水平方向和竖直方向的攻击选择两类，每颗小行星所对应的边都分别与一个水平方向和一个竖直方向的顶点相连，所以是一个二分图，本题正好是求得二分图的最大匹配。在图论中，图中两两不含公共顶点的边的集合M称为匹配，儿元素最多的M称为最大匹配。/*********************************************** * Author: fisty

2015-08-18 12:08:47 387

系统程序员成长计划

深入季节计算机系统（第二版）

空空如也