- 博客(20)
- 收藏
- 关注
RSS订阅原创 安卓等待子线程~
找了一天可算找到解决方法 了 - -，吃了没系统学过安卓的亏，博客第一次更新acm以外的内容public class MainActivity extends Activity { private Handler uiHandler = new Handler(){ // 覆写这个方法，接收并处理消息。 @Override public ...
2019-05-28 15:11:35
430
原创 P1308 统计单词数
很不熟悉字符串处理，我的acm之旅也是跪在了字符串上，这次比赛碰巧字符串的题这么多。。。无所谓了，已经退役了，专心考研，刷题只是惯性和兴趣，刷刷简单的题开心开心就好～这道题是一道水题，但是如果能对c++的自带函数比较熟悉写起来会简单的多，可能效率也会比较好首先要把两个字符串都转换成小写。其次把特殊情况平凡化。看题目中单词的定义，单独的出现才能算单词，单独的出现就是要么这个...
2019-05-11 19:22:52
247
原创 洛谷p1047树状数组
看到有树状数组的解法就以为是用区间更新区间查询做的，结果怎么都想不到怎么样来实现树最多割一次。看了一下别人的题解，才顿悟：不是题目有区间更新区间查询就必须维护一个区间更区间查的树状数组。。这道题应该用区间更单点查的树状数组。太不灵活了需要注意的有两点吧1，树状数组的最低下标只能是1，不能是0，这道题的区间范围是从0开始，所以要整体的把区间向后移动一位，把1当0，1当22，用差分...
2019-05-08 23:23:51
286
2
原创 poj3666 dp + 离散化
题目大意：农夫约翰想修一条尽量平缓的路，路的每一段海拔是A_i，修理后是B_i，花费|A_i – B_i|，求最小花费。 最小花费有可能是单调非降，也有可能是单调非增，因为题目数据比较水，只求单调非降就可以 第一步定义dp数组意义，dp[i][j]表示前i段路，最大值为j的cost，那么很自然的得到递推式dp[i][j] = min( dp[i-1][ k ] ( ...
2019-02-09 17:50:05
192
原创 poj3181 完全背包三维转二维优化 + 滚动数组 + 高精度数处理
好久没写博客，感觉写题还是用博客总结效果好一点。以后会坚持写下去的题意：给你两个整数 N和K，让求利用1到k这些数（每个数的数量不限），拼成N有多少种方案。 显而易见这是一个完全背包问题。我们将dp[i][j]定义如下：由前i个数拼成j有多少种方案。对于每一种i和j的不同取值，有dp[i][j](前i个数拼成j的方案数) = dp[i-1][j](第i种数一个也不用的方案数） ...
2019-02-07 16:38:15
255
原创 用欧几里得扩展求不定方程的一组整数解
用欧几里德扩展求解不定方程的整数解： 上回说到辗转相除法也就是欧几里德算法：链接https://blog.csdn.net/qq_39652552/article/details/84073880其中有个重要的性质 gcd（a，b） = gcd（ b，a%b）我们利用其性质做一下扩展，就可以用它做不定方程的求解。引理：存在x，y 使得 ax + by = gcd（a，b）...
2018-11-16 22:53:34
515
原创 辗转相除法（求最大公约数）
朴素的求最大公约数方法是 对于所要求最大公约数的a，b，枚举从 min（a，b） 到 1的数，看看那个数满足 a % x && b% x == 0辗转相除法对其起到了极大的优化，它的核心依据是 a和b的最大公约数是也是 b和a%b 的最大公约数下面我们来证明一下假设 ：a和b的最大公约数是r。那么a可以整除r，b也可以整除r。因为a % b = a - k * b，...
2018-11-14 21:09:15
1814
原创 快速幂运算和快速幂取模运算
如果我们要求一个数x的n次幂，朴素的想法是让n个x相乘。对与n很大的情况，会造成一定的时间浪费。这里讲解一下o（nlogn)的快速幂解法我们考察a^11 次方。我们将它的幂用二进制形式表示（11转化为二进制是1011）也就是a^1011。我们将它再做一步转换。二进制数字转化成对应1相加的形式得到：a^1011 = a^(1000 + 10 + 1) = a^1000 * a^10 ...
2018-11-14 20:09:13
1115
原创 o（n）时间判断素数的欧拉筛法
筛选素数，埃氏筛法虽然时间复杂度可以到达o（logn）的时间复杂度 ，但是仍有优化的空间，因为像6会被2筛出来一次，3筛出来一次，重复筛选，想要进一步提高就是解决这些重复筛选的情况。一个合数，可以由两个数相乘得到，同样的，也可以表示成为一个最小素因子和另一个数相乘。对于每个合数，只有唯一确定的最小素因子。所以，如果每个合数都由它的最小素因子来筛选出来。那么就不会有埃氏筛法的重复现象。上代码...
2018-11-14 18:03:37
792
原创 贪心算法——任务安排
给定一台有m个储存空间的单进程机器;现有n个 请求:第i个请求计算时需要占用R[i]个空间，计算完成后，储存计算结果需要占用O[i]个空间(其中O[i]<R[i])。问如何安排这n个请求的顺序，使得所有请求都能完成。如:m=14，n=2，R[1,2]=[10,8]，O[1,2]=[5,6]。可以先运行第一个任务，计算时占用10个空间，计算完成后占用5个空间，剩余9个空间执行第二个...
2018-10-24 20:26:53
3368
翻译 用O（nlogn）求特定的最长公共子序列
时间限制：1 sec空间限制：256 MB问题描述给定两个 1 到 n 的排列 A,B （即长度为 n 的序列，其中 [1,n] 之间的所有数都出现了恰好一次）。求它们的最长公共子序列长度。输入格式第一行一个整数 n ，意义见题目描述。第二行 n 个用空格隔开的正整数 A[1],⋯,A[n]，描述排列 A。第三行 n 个用空格隔开的正整数 B[1],⋯,B[n]，描述排...
2018-10-16 20:28:00
901
原创 背包问题拓展（前缀背包后缀背包）
描述n个物品，每个物品有一个体积v和价值w。现在你要回答，把一个物品丢弃后，剩下的物品装进一个大小为V的背包里能得到的最大价值是多少。输入输入的第一行包含一个正整数n（n ≤ 5000）。接下来n行，每行包含两个正整数v和w（v,w ≤ 5000），分别表示一个物品的体积和价值。接下来一行包含一个正整数q（q ≤ 5000）,表示询问个数。接下来q行，每行包含两个正整数V和...
2018-10-10 16:54:06
910
原创 单调栈应用POJ3250 + 单调序列
参考:https://blog.csdn.net/zuzhiang/article/details/78134247单调栈，顾名思义，是栈内元素保持一定单调性（单调递增或单调递减或是其他性质）的栈。我们假如有这样一个问题(poj3250):给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。如果用朴素的解法就会是双层for循环遍历,时间复杂度达到O(n^2),利用单调...
2018-09-25 21:16:59
240
原创 匈牙利算法（最小点覆盖）poj3041
题目意思是一次可以毁掉一行或者一列，要求至少毁多少次才能将图上的x都消灭掉。简单的解释一下最小点覆盖：在图中用最少的点，覆盖图中所有的边将每一行或者列想象成点，每个x想象成一条边，于是此题很自然的转换成为了最小点覆盖问题。而二分图的最小点覆盖数 = 二分图的最大匹配。于是就用匈牙利算法求这个图的最大匹配就好啦。用人和座位分别表示二分图的x集和y集，于是匈牙利算法大概每一趟过程可...
2018-09-18 21:18:34
615
原创 算法题目：大转盘
问题描述邓老师有一个大转盘，被平分成了 2^n 份。邓老师还有一个长度为 2^n 的数组 a（下标从 0 开始），其中的每个元素都是 0 或 1。于是邓老师就可以选择大转盘上的一个位置，将 a[0] 填入其中，然后按顺时针顺序依次将 a[1],a[2],…,a[2^n-1] 填入。对于大转盘上的一个指定位置，邓老师可以从它开始，取出顺时针方向的 n 个位置，并将它们按原顺序拼接起来，得...
2018-08-28 20:00:21
964
原创 nyoj 44 子串和【最大子串和】
题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=44常见的做法有：枚举区间、动态规划等。昨天突然想到了一个O（n）的算法，拿来分享给诸位我们从后向前看这串数字 5 6 -2 3 -5 发现倒数第一位就是负数（-5），毫无疑问，这个负数肯定不在我的最大子串和里，因为我们舍去它并不会影响我们链接其它有价值的数，所以我们将它抛弃...
2018-08-27 17:26:37
521
1
原创 在O（n）时间内求众数
求众数的定义：在一个序列中，超过一半的数，就是这个序列中的众数如序列 5 4 1 1 1，这里1 1 1就是其中的众数。如果我们用map的话，将序列中的每个元素放入map里需要大概O（nlogN）的时间复杂度，虽然也不错，但效率并非最高。做到O（n）时间的话就需要动动脑子了～当然，我们要求一个数列的众数，这个数列首先要存在众数。我们这个算法的前提条件是这个数列确实有众数存在。为...
2018-08-26 19:03:16
1270
5
原创 快速寻找第k大元素
一个好的算法往往是在朴素的想法上进行加工改造，我们要求数组中的第k大元素，往往最先想到的想法是先进行降序排序，可以很快的达到答案。但排序在序列元素很多时，无疑是一个浩大的工程。要至少耗费O（logn）的时间复杂度，如果想在线性时间O（n）就想做到求解应该怎么做呢？我们先思考排序为什么可以解决该问题：如果我们随便选定一个元素，假想的认为它就是我们要找的第k大元素，我们最终要考察，证明的是这个...
2018-08-25 11:15:59
3674
1
原创 重编码 ---huffman编码练习
问题描述有一篇文章，文章包含 n 种单词，单词的编号从 1 至 n，第 i 种单词的出现次数为 w[i]。现在，我们要用一个 2 进制串（即只包含 0 或 1 的串） s[i] 来替换第 i 种单词，使其满足如下要求：对于任意的 1≤i,j≤n（i≤j），都有 s[i] 不是 s[j] 的前缀。（这个要求是为了避免二义性）你的任务是对每个单词选择合适的 s[i]，使得替换后的文章总长度...
2018-08-13 21:43:42
268
原创 散列表的原理和应用
本来以为，散列表就是map，今天做了道题看答案的时候，才发现我原来搞错了，于是简单的学习了一下散列表的原理和简单实现，发博客分享一下～我们知道，数组的动态操作（删除、插入）是非常耗时的，链表的静态操作（查找）也是颇为麻烦的。在既涉及静态操作，又涉及动态操作的场合，这两种基本的数据结构就非常乏力了。如何达到平衡呢？我们想象一个场景，在一个特殊的学校里，一开始并没有班级的概念，几千名学...
2018-08-13 16:52:06
1805
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人