曾任职于阿里巴巴,现就职于美图,专业搬砖100年~
暂时未有相关通用技术能力~
阿里云技能认证
详细说明点击打开hdu 3015 思路: 树状数组 分析: 1 题目给定n棵树的横坐标和高度,然后给定横坐标排序后的rank_f已及树的高度排序后的rank_s,规定两颗树的FAR为abs(rank_f[i] , rank_f[j]) , SHORT为min(rank_s[i] .
/dev 存放设备文件 /boot 存放内核与启动程序相关文件 /lib 存放系统库文件 /bin 存放二进制文...
点击打开poj 1990 思路: 树状数组 分析: 1 题目给定n头牛的听力v[i]. 现在规定两头你i和j如果要进行交流的话那么消耗的能量就是dis(i,j)*max(v[i].
1 复制文件和目录 1 使用cp复制文件或目录:cp 源文件(文件夹) 目标文件(文件夹) 2 常用的参数:-r 递归复制整个目录树 -rv显示详细的信息 1 复制文件到当前的目录下,比...
点击打开poj 3321 思路: 树状数组 分析: 1 题目给定一棵树,然后有n个树枝,每个树枝上面初始化有1个苹果,现在有m个操作 2 题目给定的是一棵树,我们应该考虑怎么把这棵树映射成一个数组,并且跟节点和儿子节点的编号是连续的。
Linux的文件系统结构 Linux文件系统为一个倒转的单根树状结构 文件系统的根为"/" 文件系统严格区分大小写 路径使用“/”来分割,在windows使用"\" 当前工作目录 ...
点击打开poj 2155 思路: 二维树状数组+区间更新,单点查询 分析: 点击打开查看论文 建议先看看这篇论文,比较好理解 1 题目给定两种操作,第一种是给定左上角和右下角的下标,把这个子矩形里面的0/1进行互换,第二种是问某个点的值 2 我们先看一维的情况 假设题目给定的是一个长度为n的一维数组 那么我们现在要把区间[i,j]里面的值进行0/1互换 首先我们先来看一个定理,假设一个数原先为0,那么它经过奇数次的变换为1,偶数次的变换为0。
点击打开SPOJ 1029 思路: 二维树状数组 分析: 1 简单的二维树状数组,注意因为数据量很大TLE了多次,之后把memset改成for循环A了 代码: #include #include #include #includ...
点击打开codeforces 思路: 贪心+快速幂 分析: 1 题目要求的是找到这个人的最小的分数 2 题目的数据非常大,很明显是有一个O(1)的算法也就是公式 3 我们考虑n个数分成连续的k个树有几段,设x = n/k , 那么我们就...
点击打开codeforce 336C 思路; 位运算 分析: 1 题目要求找到k个数,使得这k个数的&的结果能够被2^v整除,并且v的值应该要尽量的大 2 一个数能够被2^v整数,说明这个数的二进制的最右边的1后面刚好是v个0,比如20的...
点击打开sgu 180 思路: 树状数组+离散化 分析: 1 题目给定n个数,每个数最大为10^9 , 最小为0,求多少个匹配使得1
1 Shell(壳)是用户与操作系统底层(通常是内核)之间交互的中介程序,负责将用户指令、操作传递给操作系统底层 shell 分为两种 CUI : Command Line Interface Linux 里面的CUI指的是B...
点击打开HIT 1867 思路: 树状数组 分析: 1 题目要求的是给定一个区间求这个区间质数的个数 2 题目给定n条命令和每个店的初始的值,那么我们初始化的时候就要通过判断给定的初始值是否为质数来初始化 3 因为要求的是质数的个数,那...
点击打开HIT 2275 思路: 树状数组 分析: 1 题目要求的是总共的搭配方式,满足Ai < Aj > Ak.并且i j k不同 2 我们开两个树状数组,第一个在输入的时候就去更新。
点击打开hdu 2275 思路: multiset的应用 分析: 1 我们把所有的插入x全部插入到multiset 2 碰到删除的时候x的时候,我们就去判断 如果集合为空或者集合的第一个元素大于x,那么肯定是没有的删除的 否则...
STL里面迭代器就像指针一样,有了迭代器我们可以更加方便的进行访问集合里面的元素 下面分别对各个容器进行分析 1 list #include #include #include #include #incl...
点击打开poj 1985 思路: 两次bfs找到树的直径 分析: 1 题目给定一棵树,找树上两点最远距离 2 利用两次bfs就可以,第一次bfs从1开始求出到最远的点,然后从这个点再次bfs回来求出ans即可 代码: #inclu...
点击打开poj 2029 思路: 简单的二维树状数组 分析: 1 题目给定一个人h*w的矩阵,给定n个点表示该点上面有柿子树,求给定一个t*s的矩阵的最多的柿子树的个数 2 简单的二维树状数组,加入一个点的时候更新树状数组 3 题目的范...
点击打开hdu 4666 思路:n维空间计算最远的曼哈顿距离 分析: 1 这一题和poj2926很像,但是poj那题是静态的而这边则是动态的,对于静态的话我们知道只要去求出2^n状态下的最大值和最小值,然后求最大的差值即为ans 2 但是...
点击打开poj 2926 思路: n维空间计算最远的曼哈顿距离 分析: 1 题目给定n个5维的点,要求最远的曼哈顿距离 2 求最远曼哈顿距离,对于一个n维的空间,其中两点的曼哈顿距离为:|x1-x2|+|y1-y2|+.
点击打开链接poj 1195 思路: 二维树状数组 分析: 1 给定一个矩阵和三种操作 1 a b x表示把[a,b]值加上x,2 L B R T表示L
点击打开poj2299 思路: 离散化+树状数组 分析: 1 题目的意思就是要求逆序数对 2 题目的输入个数有500000的规模但是每个数的最大值为999999999,因此我们需要离散化这些数据 3 对于数据9 1 0 5 4我们离散化...
1 国外的论文点击打开链接 2 我的总结点击打开链接 任何能够造成树状数组下表为0的操作都会使得程序TLE,这是个很重要的地方! 第一题 poj 2299 Ultra-QuickSort 点击打开poj 2299 思路: 离...
点击打开hdu 1558 思路: 计算几何+并查集 分析: 1 有n个操作,最后求有几个集合或者说是连通分量 2 对于输入一条线段我们就去前面找能够和它相交的线段,利用并查集进行合并并且更新rank数组,rank[x]数组保存的是以x为跟...
点击打开hdu 3461 思路: 并查集+离散化+快速幂 分析: 1 题目给定长度为n的字符串,然后给定m个操作,询问最后的不同字符串的个数 2 考虑长度为n的时候,因为每个字符有26种情况('a'~'z'),所以有26^n。
点击打开hdu 2818 思路: 带权并查集 分析: 1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素 2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右...
点击打开3172 思路: 简单并查集 分析: 1 利用map对每个人进行编号,然后利用并查集即可 2 这一题有个地方就是输入case的时候要判断不等于EOF 代码: #include #include #include #incl...
点击打开hdu 2473 思路: 并查集 分析: 1 题目初始化给定n个不同的点,然后给定m个操作,有两种类型 m x y 表示x和y是同一种类型,s x表示把x从集合中单独提前出来 2 这一题和uva11987很像,我们可以在初始化的时...
点击打开hdu 3635 思路: 并查集 分析: 1 题目说有n个城市每一个城市有一个龙珠编号为i,现在有m行的输入包括两种的情况 T x y 把x所在的集合的所以龙珠转移到y集合上 Q x 询问x所在集合的龙珠的个数 2 我们利用rank[x]表示的是根节点为x的集合的元素的个数,但是现在我们发现求转移的次数不好求,刚开始我用的是一个vector数组来保存,比如v[x]表示以x为根节点的集合的元素,那么如果是把fx这个集合并到fy上的话,那么我们枚举v[fx]。
点击打开hdu 1198 思路: 并查集 分析: 1 题目给定11快小方形,然后给定一个n*m的描述求n*m矩阵内的连通分量的个数 2 首先我们应该解决怎么保存11块小方形,我们可以利用一个思维的分量来描述,比如A我们描述成{1,0,0,...
点击hdu 1856思路: 思路: 离散化+并查集 分析: 1 点数最多为10^7,但是边数最多10^5,所以我们必须采用离散化,然后利用带权并查集的思想,rank[x]表示的是以x为根节点的集合的元素个数 2 这一题主要注意的就是当...
点击打开链接zoj 3261 思路: 带权并查集 分析: 1 题目说的是有n个星球0~n-1,每个星球都有一个战斗值。n个星球之间有一些联系,并且n个星球之间会有互相伤害 2 根本没有思路的题,看了网上的思路才知道是逆向并查集。
点击打开链接poj 2912 思路: 带权并查集 分析: 1 有n个小孩玩游戏,里面有一个入是裁判,剩下的人分为三组。现在我们既不知道裁判是谁也不知道分组的情况。
点击打开hdu2199 思路: 二分 分析: 1 求题目给定的等式是否有[0,100]之间的解 2 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6是一个单调递增的函数,那么求解的话我们利用二分的思想 3 注意判断没有解的...
点击打开hdu 4647 思路: 贪心 1 若没有边权,则对点权从大到小排序即可 2 考虑边,将边权拆成两半加到它所关联的两个点的点权中即可。
点击打开hdu 4648 思路: 扫描 分析: 1 设这列数前i项和为s[i],则一段连续的数的和 a[i]+a[i+1]+...+a[j-1]+a[j]=s[j]-s[i-1],所以这段连续的数的和能被m整除的条件就是 (s[j]-s[i...
点击打开poj 1733 思路: 带权并查集 分析: 1 题目给定n个条件,要我们找到第一个不满足条件的编号 2 每一个条件给的是区间[l,r]的1的奇偶数,很明显[l,r]这个区间的1的个数可以由[0,r]-[0,l-1]得来 3 那...
点击打开链接poj 1456 思路: 贪心+并查集 分析: 1 题目的意思是给定n个物品的利润和出售的最后时间,求最大的利润 2 比较明显的贪心问题,按照利润排序,假设当前是第i个物品,那么利润为pi出售的时间为di,那么假设di还没有物品销售那么肯定先销售第i个物品,否则找di~1这些时间里面是否有没有销售物品 3 如果按照2的思路做法最坏的情况是O(n^2),但是数据比较弱可以过。
个人整理 并查集 【poj】 第一题 poj 1182 食物链 点击打开链接poj 1182 思路: 带权并查集 分析: 1 典型的带权并查集的题目 2 如果x和y是同类的关系认为是0,如果是x吃y那么关系认为是1,那么x和...
点击打开链接uva 12096 思路: STL模拟 分析: 1 题目给定5种操作,每次输出栈顶集合的元素的个数 2 利用stack和set来模拟,set保存集合的元素。
点击打开链接uva 12232 思路: 并查集的扩展应用 分析: 1 题目给定三种指令,I p v表示Xp = v, I p q v表示Xp^Xq = v, Q k Xp1 Xp2...Xpk求Xp1^Xp2^...^Xpk的值。
点击打开链接uva 11987 思路: 并查集 分析: 1 题目给定三种操作,符合并查集的模式 2 但是有一种操作和普通的并查集不同的是,2 p q要把p并到q的集合,那么这个时候p所在的集合就会发生变化,如果p刚好是它那个集合的跟节点那么这个时候就要重新调整这个集合 3 那么我们为了避免这种删除跟节点的情况出现,我们就把所有的i~n的节点的跟节点指向i+n,这样保证了删除的时候肯定不会是根节点。
点击打开链接uva 586 思路:递归模拟 分析: 1 题目是一道给定一段程序代码的球时间复杂度 2 根据题目的意思,我们可以利用栈和递归的方法,但是栈的方法比较不好写,所以我们利用递归的思路来写 3 当我们遇到LOOP的时候,我们就递...
点击打开链接uva 10273 思路: 暴力求解 分析: 1 题目要求没有吃掉的奶牛的个数已经最后一次吃掉奶牛的天数 2 没有其它的方法只能暴力,对于n头牛的n个周期求最小公倍数,然后在2个公倍数之内暴力求解 代码: #inclu...
点击打开链接uva 501 思路: vector模拟 分析: 1 题目的规模是n和m最大为30000,那么明显复杂度要为O(nlogn)级别才能过 2 由于枚举u数组需要n,所以剩下的是logn的时间,明显只有二分可以做到。
点击打开链接uva 540 思路: list+map模拟 分析: 1 题目的意思是有n个队伍,每个队伍的人数为m。 2 现在有三种操作,ENQUEUE x是插入x,如果队列里面已经有x这一队的成员那么直接插入到这一队的最后一个,否则插入到...
点击打开链接uva 305 思路: 数学+打表 分析: 1 传统的约瑟夫问题是给定n个人和m,每次数m次把当前这个人踢出局,问最后留下的一个人的编号 2 这一题是前k个人是好人,后面k个是坏人。
点击打开链接uva 10895 思路: STL的vector模拟 分析: 1 看懂题目之后,直接利用两个vector模拟即可 代码: #include #include #include #include #include using ...
点击打开链接uva 514 思路: 栈模拟 分析: 1 题目给定一个不变的入栈的顺序1~n,然后再给出一个序列问是否是一个满足条件的出栈顺序 2 每一个case后面输出空行,直接去模拟栈即可 代码: #include #include...
点击打开链接uva 11136 思路: STL 分析: 1 题目意思比较不好理解,理解了题目之后我们可以利用STL的multiset来做 2 每次找到最大和最小的值,然后求解即可 代码: #include #include #in...