- 博客(35)
- 收藏
- 关注
RSS订阅原创 二进制Trie树 + XOR LeetCode 421、1707、1803
LeetCode421. Maximum XOR of Two Numbers in an ArrayGiven an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.1 <= nums.length <= 2 * 1040 <= nums[i] <= 231 - 1题解将数组元素看做一个31位的二进制串，则可以使用二进制Trie树保存数
2021-03-27 16:06:52
239
原创 priority_queue 自定义Comp类
priority_queue定义template 。。。其中container表示底层容器，默认为vector。而comp则表示比较类，默认为仿函式less。priority_queue是一种配接器。priority_queue默认为最大堆。如何实现自定义comp类想要实现自定义comp类，得先知道priority_queue是如何使用comp的。我们从push函数入手，priority_queue的push操作是借助push_heap实现的。__push_heap源码关键部分while其逻
2021-03-25 15:52:47
593
1
原创 Trie树 LeetCode208. Implement Trie (Prefix Tree)
Trie树Trie树Trie树Trie树是一种字典树，它可以用来保存单词，查找单词。
2021-02-16 23:30:19
103
原创 双边滤波(bilateral filter)
双边滤波这是一种边缘感知的去噪滤波。公式I(p)=1Wp∑q∈SGσs(∥p−q∥)Gσr(∥Ip−Iq∥)IqI(p) = \frac{1}{W_p}\sum_{q \in S}G_{\sigma_s}(\parallel p-q \parallel)G_{\sigma_r}(\parallel I_p-I_q \parallel)I_qI(p)=Wp1q∈S∑Gσs(∥p−q∥)Gσr(∥Ip−Iq∥)Iq...
2021-02-05 12:03:41
1041
1
原创 二分查找求最值 CodeForces-1169C. Increasing by Modulo
二分查找(binary search)用于在有序序列中查找有两种用法。一是查找一个符合条件的元素。二是查找符合条件的最小(大)元素。一. 查找符合条件的元素[b, e] => 1. 查找成功, 直接返回mid。=>2. [b, mid-1]或[mid+1, e].// 当前位置取值int value(int cur) {}// 查找符合条件的元素int bina...
2020-05-05 20:44:16
330
原创 整数的素数幂分解
整数的素数幂分解算数基本定理如何求一个整数的素数幂分解代码欧拉函数算数基本定理一个整数可以唯一的表示成素数的乘积。如何求一个整数的素数幂分解对一个整数的素数幂分解，是用试除法依次判断所有小于n\sqrt nn的素数是否是它的因子，如果是，则记录这个素数及对应的幂次；并且将该素因子除干净，并且更新n。找到一个小于等于n\sqrt nn的素因子。(若找不到且n>1，则n是素数)。...
2019-05-30 10:01:10
2654
原创 二进制优化DP Hdu1059-Diving
多重背包的复杂度为O(n * m * k)，其中n为背包总容量，m为物品种类数，k为一种物品的数量。实际上等价于01背包。二进制优化，是将一种物品的数量分解成1, 2, 4, 8, …, 2x, k-2x+1+1份并组成新的物品，注意除了最后一个数，其他数都是2的幂次。此时选择任意数量的该原物品，都可以等价表示成选择分解后的某几个新物品。选择新物品的任意组合，都可以表示成选择一定数量的原物品。 ...
2019-05-20 10:47:33
213
原创 状态压缩DP Csu2169-排列
题意给一个长度为 n 的序列 p1, p2, …, pn 和 m 个二元组 (a1, b1),(a2, b2),…,(am, bm). 排列数列 p，使得 ∑i=1m∣pai−pbi∣\sum_{i = 1}^m |p_{a_i} - p_{b_i}|∑i=1m∣pai−pbi∣ 最小。求最小值。分析按序放置元素，状态表示位置是否为空。Bitcnt(status)表示此时该选择的元...
2019-05-20 10:43:50
218
原创 期望DP HDU4418-Time travel
一般情况下，期望DP逆向推。期望DP中，若当前状态的下一状态可能往前走也可能往后走，则使用解方程的思想，将状态设为变量，将状态转移方程转化为变量方程，构造矩阵。通过高斯消元求解。题意...
2019-05-12 18:35:11
222
原创 期望DP POJ2096-Collecting Bugs
题意n种bug，s个子程序。每天随机找一个bug，允许重复。求每种bug都找到，每个程序都找到bug的期望天数分析这是一个期望DP，对于期望DP通常是逆向推。即用dp值表示从当前状态到达终止状态的期望值，然后由终止状态推导至初始状态。这里我们可以以已找到bug种类数量和已完成子程序数量作为状态，dp值表示从当前状态到达终止状态的期望天数。对于一个状态(i，j)，i表示已找到的bug种类数...
2019-04-22 21:56:25
171
原创 数位DP codeforces55(D)-Beautiful numbers
数位DP：用来统计区间内符合条件的数的个数，通常区间范围很大，并且条件通常与数的组成有关。解题关键：对前缀的抽象分类。须符合两个条件。对于一个数anan-1……a2a1a0, 可以将前缀anan-1…ak+1归类于状态(sta,k), 使得具有相同状态的前缀的解一致。 可以求解，在状态(sta,k)下，dkdk-1…d1d0中符合条件的数字的个数。实现方法是记忆化搜索。dp[k][...
2019-04-03 22:24:16
291
原创 状态压缩DP UVa10817-Headmaster's Headache
状态压缩是指使用计算机二进制位来存储状态，一般用法是将二进制串当做一个集合，bit位代表集合中的元素，bit位取值表示元素是否在集合中。n位二进制串可以描述2^n种集合(状态)，因此对于n的取值是相当严格的。状态压缩DP中需要使用各种位运算来描述状态转换。所以需要对位运算的使用有一定的了解，下面是一些巧妙的运用。把一个数字x最靠右的第一个1去掉 : x = x & (x-1) 判断数...
2019-04-01 11:37:40
3188
原创 树状DP UVa1218-Perfect Service
树状DP就是在树上的DP，指当前节点的解可以通过子孙节点的解求出，即状态转移方程是由子孙节点推出当前节点的。使用遍历方法：由于树的一个特性，即任意两个节点之间只有一条路径，因此深搜时每个点只会访问一次，所以我们通常使用深搜来遍历，这时复杂度只有O(n)。在推出状态转移方程后，深搜大致过程如下(具体更新节点信息的位置视情况而定)：void dfs(int v, int fa){ ...
2019-04-01 01:39:55
111
原创 CodeForces-617E 前缀异或和+莫队算法
问题描述：E. XOR and Favorite NumberBob has a favorite numberkandaiof lengthn. Now he asks you to answermqueries. Each query is given by a pairliandriand asks you to count the number of pair...
2019-03-18 23:34:43
187
原创 python学习第15周：sklearn
Question:1datasets.make_classification是一个智能生成数据集的函数from sklearn import datasetsdataset = datasets.make_classification(n_samples=1000, n_features=10,n_informative=2, n_redundant=2, n_r...
2018-06-20 01:58:34
219
原创 python学习第14周：Anscombe's quartet
about Anscombe's quartet1973年，统计学家F.J. Anscombe构造出了四组奇特的数据。它告诉人们，在分析数据之前，描绘数据所对应的图像有多么的重要。这四组数据中，x值的平均数都是9.0，y值的平均数都是7.5；x值的方差都是10.0，y值的方差都是3.75；它们的相关度都是0.816，线性回归线都是y=3+0.5x。单从这些统计数字上看来，四组数据所反映出的实际...
2018-06-12 23:16:59
2047
2
原创 python学习第13周：scipy
10.1题目 题解import numpyfrom scipy.linalg import lstsq#10.1 least squarem = 20n = 10A = numpy.random.normal(size=(m, n))b = numpy.random.normal(size = m)x, residues, rank, s = lstsq(A, b)pr...
2018-06-05 12:31:42
215
2
原创 python学习第12周： Python matplotlib
11.1题目题解import matplotlib.pyplot as pltimport numpyimport mathdef func(x): y1 = numpy.sin(x-2) y2 = math.e ** (-x*x) return y1**2 * y2x = numpy.linspace(0, 2， 1000)y = ...
2018-05-29 18:03:22
305
原创 python学习第11周：python numpy
Problem：Generate matrices A, with random Gaussian entries, B, a Toeplitz matrix, where A 2 Rn×m and B 2 Rm×m,for n = 200, m = 500首先是初始化过程：import numpyimport timefrom scipy.linalg import t...
2018-05-22 00:43:45
289
原创 python学习第9周：LeetCode 120. Triangle题解
#120题目来源：https://leetcode.com/problems/triangle题目分析：Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given ...
2018-05-11 00:52:48
116
原创 python学习第8周（3）： LeetCode 11. Container With Most Water
题目：Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find...
2018-04-29 23:28:08
97
原创 python学习第8周（2）： LeetCode.63. Unique Paths II 题解
这是一题动态规划的题目。若一个格子可达，则到达这个格子的路径数等于到达其上一个格子的路径数与到达其左格子的路径数的和；否则到达这个格子的路径数为0.题目：A robot is located at the top-left corner of amxngrid (marked 'Start' in the diagram below).The robot can onl...
2018-04-29 19:15:07
151
原创 python学习第8周（1）：LeetCode45. Jump Game II题解
题目：Given 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.Your go...
2018-04-28 11:35:56
230
原创 python学习第6周
#11-1city_functions.pydef city_country(city, country): return (city + ", " + country).title()test_cities.pyimport unittestfrom city_functions.py import city_countryclass CitysTestCase(u...
2018-04-15 15:31:00
109
原创 python学习第5周（2）
#10-1with open(r'learning_python.txt') as file_object:#linefor line in file_object:print(line.rstrip())with open(r'learning_python.txt') as file_object:#filecontents = file_object.read()print(...
2018-04-05 00:59:14
95
原创 python学习第5周（1）
#9-3class User():def __init__(self, first_name, last_name, sex, country):self.first_name = first_nameself.last_name = last_nameself.sex = sexself.country = countrydef describe_user(self):messa...
2018-04-04 23:22:47
149
原创 python学习第4周（2）
#8-1def display_message():print("I learn function in this chapter.")display_message()#8-5def describe_city(city_name, country = "China"):print(city_name + " is in " + country)describe_city("Gua...
2018-04-01 23:20:49
109
原创 python学习第4周（1）
#7-2num = input("how many people for dinner:")num = int(num)if num > 8 :print("there is no available table.\n")#7-3num = input("please input a numble:");if int(num) % 10 == 0 :print("it is ...
2018-03-28 20:09:33
113
原创 python学习第3周（2）
#6-2favorite_num = {"LiHua": 1,"Ben": 2,"Lili": 3,"Estin": 8,"Kimi": 6}for name, num in favorite_num.items():print(name + "'s favorite numble is " + str(num))#6-5rivers_inf = {"nile": "egyp...
2018-03-21 23:36:42
133
原创 python学习第3周（1）
#5-2str1 = "String"str2 = "string"print(str1 == str2)print(str1 != str2)print(str1.lower() == str2.lower())print(str1.lower() != str2.lower())print(4 == 5)print(4 != 5)print(4 > 5)print(4...
2018-03-21 22:59:20
121
原创 python学习第2周（2）
#4-2animals = ["dog", "cat", "pig"]for animal in animals :print("A " + animal + " would make a great pet")print("Any of the animals would make a great pet!")#4-3for value in range(1, 21):print(...
2018-03-15 16:17:50
108
原创 python学习第2周（1）
#python课后作业#3-1,2names = ["Wuzy", "Xul", "Xusw"]for name in names:print(name + ", How are you.")#3-3vehicles = ["car", "bike", "motorbike"]for vehicle in vehicles:print("I would like to own a ...
2018-03-13 19:44:32
255
原创 python学习第1周（2）
#python课后作业#2-3name = "alice"print("Hello " + name.title() + ", it's cold today.")#2-7name = "\n\tEinstein \n"print(name)print(name.lstrip())print(name.strip())print(name.rstrip())#2-8print...
2018-03-10 20:00:12
105
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人