算法
算法
Ranye123
这个作者很懒,什么都没留下…
展开
-
【算法】dfs转dp的通用方式
说实话,dp一学就会,一做就懵的一个很重要的原因就是所谓递推不总是一件合乎思维的事。爬楼梯的题我们想象说dp[i]是爬后i级楼梯的种数,这样递推公式,数据结构,划分方法纷纷水到渠成,那像这样的题呢?原创 2024-08-19 10:47:10 · 440 阅读 · 0 评论 -
几种最短路径算法的实质
dijkstra是一个“加点”的过程,floyd是一个“选线”的过程原创 2024-07-18 20:26:18 · 625 阅读 · 0 评论 -
【算法心得】Integer is also a constraint
【代码】【算法心得】Integer is also a constraint。原创 2023-11-27 18:54:44 · 173 阅读 · 0 评论 -
【算法心得】When data range not large, try Bucket sort
【代码】【算法心得】When data range not large, try Bucket sort。原创 2023-11-24 14:23:32 · 221 阅读 · 0 评论 -
【算法随记】C(n,m)不越界但A(n,m)越界;C(n,1)+C(n,3)+C(n,5)...等二项式定理;“memset”: 找不到标识符
这题要模1e9+7,但是只有加减乘能模,除法模不了。所以这个A(n,m)要存原值,原值也太大了,爆 long long。先算A(n,m)里有多少个2 3 5 7,再减去(n-m)!中2 3 5 7的个数,最后把剩下的乘起来。费马小定理:若M是质数,且B、M互质,那么B^(M-1) mod M = 1。要是能不要除法,全是乘法就好了。M自己就是质数,当然与B互质。原创 2023-08-23 21:05:35 · 389 阅读 · 0 评论 -
【算法心得】minus instead of add
From now on I will try to write blog in English, there may be a lot of grammar issue in these articles, but I think I am only a learner, it is a part of study.原创 2023-11-20 17:44:19 · 138 阅读 · 0 评论 -
【算法心得】位运算
每次计算s的值时,其实是先计算每个数位上1的个数,若有奇数个1,则该位上的结果为1,偶数个为0,这是这次推论出的一个结论,不过对于这题来说用不到。所以对于任意一组个数为偶数的序列,如果它是x x x x x x这样的构造,那它最后异或出来的结果肯定是0。我们将前N-1个数变成s,那前N-1个数的新异或值是0,算上最后一个数,假设为a,整体N个元素的新s值为a。对于元素偶数个的序列,直接将从头到尾变成s,这样算出来的新s就肯定是0,再从头到尾变成0,就完成了。0^0=0,所以多少个0相互异或都是0。原创 2023-09-05 15:22:53 · 82 阅读 · 0 评论 -
【算法笔记】二维的哈希与迭代转换;Runtime Error 的解决思路
15*2e6=3e7,这个放栈内存上肯定爆掉,我用的vector,放堆内存不知道,估计也很极限,所以就给改成了每次用到的时候现算。最后回家路上走着走着才想起来,把小块放在左上角的那步,就是迭代的初始情况,我没有加判断,比方说小块的大小比大块的还大,那第一步的时候是会越界的。查了一下,也有可能是比方说数组开太大了,爆内存了,比如 int A[1e8],肯定会 RE(栈内存里,堆内存不会)RE 的原因一般是越界了,访问不存在的内存这样的,不过打出来所有访存的index,发现没有一个越界了。原创 2023-08-31 15:03:44 · 433 阅读 · 0 评论 -
C++加快输入输出
ios::sync_with_stdio(0);cin.tie(0);原创 2023-08-27 21:57:19 · 213 阅读 · 0 评论 -
【算法随记】在计算过程中模的情况
先模再加再模和直接加再模一样。先模再减再模和直接减再模一样。先模再乘再模和直接乘再模一样。原创 2023-08-22 13:04:16 · 212 阅读 · 0 评论 -
【算法心得】下标会变不好用线段树,那就通过线段树反向求下标
如果线段树里存的是某区间某元素的数量(每一个节点是一个数组),那么让这个数组tree[x]中空出tree[x][0]来作为tree[x][1]~tree[x][N]的和,这样找到区间字符数量为l_origin是可行的,r_origin同理。1e5,只能O(nlogn)了呀,我想过用链表维护这个string,这样删了之后下标是真下标,然后把同样的字符链接起来,删的时候好找,但是这样还是没办法判断下标,要是判断下标是不是在 [l,r],就得一格一格走链表,那一趟就O(n)了😵。原创 2023-08-22 13:02:19 · 71 阅读 · 0 评论 -
【算法随记】二进制数的后缀相同不代表它们是倍数关系
打出来看是01101111001111001(倒序),我的输出是6(110),感觉没问题呀,正好是最后面的三位。只有xxxxx10是10的倍数,xxxxx1是1的倍数,这是美好的巧合(奇偶性),推广不了的。110xxxxxx不是110的倍数,xxxxxx110也不是。就像7xxx未必是7的倍数,xxxx7也未必是7的倍数。第三个点是81142,wa了。原创 2023-08-21 18:13:57 · 76 阅读 · 0 评论 -
【算法心得】js string改其中的某位要substring;replace+正则;Set;Set 转 Array; Map
【代码】【算法心得】js string改其中的某位要substring;replace+正则;Set;Set 转 Array;Map。原创 2023-08-04 11:11:09 · 122 阅读 · 0 评论 -
【算法心得】C++map用不着map.find(arr[j])!=map.end();js的map是map不是哈希;编译器选GNU
我自己都没想到调了一个半小时,要是之前肯定老早就放弃了,觉得评测机sb,不是我的问题,但是吧今天是组团练算法第一天,不好意思。后来真的没有招了,找了一个写的逻辑差不多的,为了跟他写的差不多我自己的优化都舍弃了,最后基本是写的一样一样的,还是TLE。不过吧在第10个点WA了,这个很快查出来了,把ans换成long long 就好了。后来发现跟人家唯一不同的是编译器选的不一样,我选的Clang++,人家是GNU。把最开始的那次,没跟着优化的代码拿过去跑,也可以AC,满意了。看了人家写的,还加了。原创 2023-08-03 20:51:37 · 336 阅读 · 0 评论 -
C++输出inf
1000 0000 0000 0000 0000 0000 0000 0000(31个0)我打表快速幂的时候,正好就32没打。最后1/0,可不是无限大么。第一次遇到输出inf😮。原创 2023-07-24 11:41:59 · 356 阅读 · 0 评论 -
LRU 算法,但 get 和 put 必须 O(1),用哈希表
看到题解有人用list,list的话是链式结构,插入O(1),删除O(1),查询O(n),刚开始我想,删除不用找到对应的那个么?其实是不用的,如果是自己实现的话。线性的数据结构也可以吧,如果可以构造出一个队列,从前往后放入;如果满了,把最前面的那个踢出去;我自己写这题的时候负优化,想着可以在队列中存一些脏数据,等到用到的时候再判断这个数据脏不脏。但其实,这个判断也是要时间的,不如直接维护真实数据。这个node是一个指针,这个指针是unordered_map给的,而不是迭代list找到的,那就O(1)原创 2023-07-18 14:58:27 · 236 阅读 · 0 评论 -
O(1) 查询某小块的问题
这个题用优先队列就慢了,每次调整要logn,总的nlogn要想O(n)需要预处理有两种预处理方法。原创 2023-07-17 15:50:58 · 91 阅读 · 0 评论 -
质数打表模板
埃氏筛法的缺陷:一个合数可能被筛多次,如 12 被 2 筛了一次(2*6)、被 3 也筛了一次(3*4)数组记录数是否被筛选过,从而以达到不重复的目的。原创 2022-11-10 20:49:48 · 75 阅读 · 0 评论 -
什么是自动机
字典树就是最典型的自动机,abc 是可以接受的,a$bc 就不能接受。给一串字符序列,判定是否可以接受,就是自动机。原创 2022-09-21 18:06:45 · 542 阅读 · 0 评论 -
2-SAT
SAT:satisfiability,可满足性2-SAT 是说约束条件在两两元素之间一个比较典型的 2-sat 问题是聚会问题,每家夫妻二人必须去一个,给定一组关系,某两人关系不好不能同时出席,作为主办方能否请恰好 n 个人列席。原创 2022-09-21 17:54:51 · 317 阅读 · 0 评论 -
曼哈顿距离和切比雪夫距离的转换
假设有两个点A(x1,y1),B(x2,y2)曼哈顿距离 =∣x1−x2∣+∣y1−y2∣切比雪夫距离 =max(∣x1−x2∣,∣y1−y2∣)一个是折线的距离,一个是 x,y 方向上更大的那个距离,这二者有什么关系呢?原创 2022-09-03 19:38:43 · 572 阅读 · 0 评论 -
离线算法 vs 在线算法
在实际做题的过程中,有些题要求每次查询必须立刻输出结果,有些题是允许先把增删查改的整个序列先给出,最后再回答也不迟,后者可以使用离线算法,前者就与离线算法无缘了。常常拿来举例的是选择排序,每次选择最小的那一个放在前面,要是算法开始了,又加进来个新数据,就乱套了。在线算法与之相反,比如插入排序,新加进来一个没啥问题,再插入进去就行了。离线算法是说在算法开始之前,数据定死,不能在执行了的时候又增删数据。原创 2022-09-03 18:48:23 · 960 阅读 · 0 评论 -
离散化模板
如果直接使用 map 去存,每次插入都是一次树型的调整,虽然大致是 nlogn,但是肯定要大一点的。对于只在初始化阶段建表,后期不再改动的情况,是挺浪费的。假设需要存储一些键值对,它们的 key 分别为{1, 8, -10, 499, 231, 76, 21747483647}——一组无序且边界极大的数。lower_bound()是纯二分,logn,所以说这个也是 nlogn,比 map 快的 nlogn。使用时很方便,比如要找 key=499 对应的数据,只需要。这个时候使用离散化是更好的方法。原创 2022-09-03 14:00:06 · 88 阅读 · 0 评论 -
2019/3/3 单源最短路径 狄克斯特拉算法
Mike and Shortcuts图有n个点,终点为1,i到j点距离为|i-j|,对于某一个点i,存在一个特殊点ai使它到特殊点ai距离为1(单向),求各个点到点1的最短路径。inputThe first line:点的个数nThe second line contains n integers a1, a2, …, an:特殊点(1 ≤ n ≤ 200 000)outputIn ...原创 2019-03-04 06:52:48 · 172 阅读 · 0 评论 -
2019/3/2 STL初步
STL栈 stackstack<int> p; //创建一个名为p的栈p.push(x);p.pop();p.size();p.top();队列 queuequeue<int> q;q.push(x);q.pop();q.size();q.front();q.back();优先级队列 priority_queuepriority_queue...原创 2019-03-02 17:32:11 · 147 阅读 · 0 评论 -
map遍历及其有序性
遍历是有序的原创 2022-07-06 08:52:40 · 488 阅读 · 0 评论 -
c++ char[]转string
直接转原创 2022-07-06 08:43:15 · 447 阅读 · 0 评论